Gibt es einen optimalen Algorithmus, um den längsten kürzesten Pfad in einem Netzwerk zu finden?

13

Ich habe eine große Anzahl linearer Netzwerke und möchte die beiden Enden jedes Netzwerks finden, die entlang des Netzwerks am weitesten voneinander entfernt sind (in der Abbildung unten wären es D bis K). Die Brute-Force-Lösung für dieses Problem besteht darin, den kürzesten Pfad entlang des Netzwerks für jedes Ursprungspaar zu berechnen. Ich habe jedoch Hunderte von Netzwerken mit Tausenden von Enden. Daher ist die Berechnung jedes möglichen Pfads recht schwierig.

Gibt es eine optimale Methode, um dies zu berechnen, ohne die Brute Force einzusetzen? Kann ich einige Punkte aufgrund einiger cleverer Regeln ausschließen?

Wie finde ich den roten Weg effizient?

EDIT: Ich habe eine Illustration des längsten von @Alex Tereshenkov erwähnten Pfades hinzugefügt, um meine Frage zu klären. Der schwarze Pfad ist das Ergebnis des Algorithmus für den längsten Pfad (längster Pfad ohne Wiederholung von Scheitelpunkten). Stellen Sie sich in meinem Fall vor, Sie betreten das Netzwerk von einem beliebigen Buchstaben aus und müssen so schnell wie möglich zu einem anderen Buchstaben fahren. Welche beiden Buchstaben sind am schwierigsten zu verbinden? Bildbeschreibung hier eingeben

radouxju
quelle
verrückte Farbe skillz!
Adam

Antworten:

6

Ich denke, Sie suchen möglicherweise nach dem Diagrammdurchmesser Ihres Netzwerks. Es gibt einige Fragen zum Stack-Austausch, die dieses Thema betreffen, z.

Die meisten Algorithmen schlagen vor, zuerst die "kürzesten Wege aller Paare" zu berechnen und den längsten davon auszuwählen, aber ich fand einen Blog-Beitrag von Koushik Narayanan , der einen alternativen Ansatz vorschlägt, der optimaler sein könnte (ich habe nicht geprüft), welcher iteriert über jeden Scheitelpunkt und findet das am weitesten entfernte Paar:

Wir können den Pfad von einem Scheitelpunkt V1 so berechnen, dass er der kürzeste Pfad zwischen V1 und einem der Scheitelpunkte ist und länger als der kürzeste Pfad zwischen einem beliebigen anderen Scheitelpunkt. In diesem Beitrag finden Sie einen Algorithmus. Dann können wir durch jeden Scheitelpunkt iterieren und den längsten Pfad mit jedem Scheitelpunkt als Wurzel finden. Sobald wir die Liste aller längsten kürzesten Pfade haben, können wir denjenigen mit dem Maximalwert finden und zurückgeben.

mkadunc
quelle
danke, der diagrammdurchmesser war genau das, wonach ich suche, und die heuristik mit pseudodurchmesser funktioniert in meinem fall. Ich habe gerade dort neue Wörter gelernt!
Radouxju
7

Laut Wikipedia-Seite Längster Pfad Problem , dieses Problem

... ist NP-hart, was bedeutet, dass es für beliebige Graphen nicht in Polynomzeit gelöst werden kann , es sei denn P = NP. Es sind auch stärkere Härteergebnisse bekannt, die zeigen, dass eine Annäherung schwierig ist. Allerdings hat es eine lineare Zeitlösung für die gerichtete azyklische Graphen, die wichtigen Anwendungen bei der Suche nach dem kritischen Pfad in Planungsproblemen hat.

Wenn Sie mit DAG arbeiten (oder Ihr Diagramm als DAG darstellen können ), können networkxSie es mit dem Python-Paket berechnen. Suchen Sie nach der Funktion dag_longest_path.

Wenn mir nichts fehlt, müssen Sie die Länge zwischen den Diagrammknoten berechnen und sortieren, was leider nur in linearer Zeit funktioniert , dh es gibt keinen effizienten Algorithmus dafür.

Alex Tereshenkov
quelle
danke für die antwort, schon + 1 wegen der informationen. Ich suche jedoch den längsten DER KURZESTEN WEGE in einem Netzwerk (in meinem Beispiel kein Umweg nach B oder H). Daher ist Ihre Lösung nicht genau das, wonach ich suche, auch wenn darauf hingewiesen wird, dass "Brute Force" wahrscheinlich die einzige Lösung ist.
Radouxju
@ Radouxju, ah ich verstehe. Mal sehen, ob Gene das merkt, er hat viel Erfahrung mit Grafiken, vielleicht hat er ein paar gute Ideen.
Alex Tereshenkov