Ich wurde diese Frage in einem Interview gestellt, aber ich konnte keine vernünftige Lösung finden. Also sagte ich ihnen den naiven Ansatz, alle Zyklen zu finden und dann den Zyklus mit der geringsten Länge auszuwählen.Zyklus kürzeste Länge in einem gerichteten Graphen mit positiven Gewichten finden
Ich bin gespannt, was eine effiziente Lösung für dieses Problem ist.
Sie leicht Floyd-Warshall algorithm ändern können. (Wenn Sie mit der Graphentheorie überhaupt nicht vertraut sind, schlage ich vor, es auszuprobieren, beispielsweise eine Kopie von Introduction to Algorithms zu erhalten).
Traditionell starten Sie path[i][i] = 0 für jeden i. Aber Sie können stattdessen von path[i][i] = INFINITY starten. Es wirkt sich nicht auf den Algorithmus selbst aus, da diese Nullen sowieso nicht in der Berechnung verwendet wurden (da sich der Pfad path[i][j] niemals für k == i oder k == j ändert).
Am Ende ist path[i][i] die Länge der kürzeste Zyklus durch i geht. Folglich müssen Sie min(path[i][i]) für alle i finden. Und wenn Sie selbst (nicht nur seine Länge) Zyklus wollen, können Sie es tun, wie es normalerweise mit normalen Pfaden getan wird: durch Auswendiglernen k während der Ausführung des Algorithmus.
Darüber hinaus können Sie auch Dijkstra's algorithm verwenden, um einen kürzesten Zyklus zu finden, der durch einen bestimmten Knoten geht. Wenn Sie diesen modifizierten Dijkstra für jeden Knoten ausführen, erhalten Sie das gleiche Ergebnis wie bei Floyd-Warshall. Und da jeder Dijkstra O(n^2) ist, erhalten Sie die gleiche O(n^3) Gesamtkomplexität.
Tree Edge, Back Edge, Down Edge und Parent EdgeBack Edge bekommen und haben einen weiteren Zähler um die Länge zu bekommen.Siehe Algorithms in C++ Part5 - Robert Sedgwick für weitere Details
Netter Versuch, aber das hat exponentielle Komplexität am besten. Ich vermute, Robert Sedgwick löst in seinem Buch ein etwas allgemeineres und komplexeres Problem, da dieses viel einfacher ist. –
Sie müssen jedem Knoten, der immer 1 ist, ein anderes Gewicht zuweisen. Führen Sie nun einen beliebigen Algorithmus für den kürzesten Pfad von einem Knoten zum selben Knoten mit diesen Gewichtungen aus. Aber unter Berücksichtigung der Zwischenpfade müssen Sie die Pfade ignorieren, deren tatsächliche Gewichte negativ sind.
Der Pseudocode ist eine einfache Modifikation des Dijkstra-Algorithmus.
for all u in V:
for all v in V:
path[u][v] = infinity
for all s in V:
path[s][s] = 0
H = makequeue (V) .. using pathvalues in path[s] array as keys
while H is not empty:
u = deletemin(H)
for all edges (u,v) in E:
if path[s][v] > path[s][u] + l(u, v) or path[s][s] == 0:
path[s][v] = path[s][u] + l(u,v)
decreaseKey(H, v)
lengthMinCycle = INT_MAX
for all v in V:
if path[v][v] < lengthMinCycle & path[v][v] != 0 :
lengthMinCycle = path[v][v]
if lengthMinCycle == INT_MAX:
print(“The graph is acyclic.”)
else:
print(“Length of minimum cycle is ”, lengthMinCycle)
Zeitkomplexität: O (| V |^3)
Wir auch Branch and Bound Algorithmus für Handlungsreisende Problem verwenden können, wie Ihre Frage mit TSP übereinstimmt. http://lcm.csa.iisc.ernet.in/dsa/node187.html
Dies entspricht nicht den Anforderungen. In diesen Algorithmen bedeutet die kürzeste die am wenigsten gewichtete und nicht die kleinste Länge. z.B. wenn es zwei Zyklen wie 1,2,3 und dann 100,500 gibt; dann wird Zyklus 1 gewählt, aber was benötigt wird, ist Zyklus 2, da er die kürzeste Länge hat. Korrigiere mich, wenn ich falsch liege. –
@Manoj Zweites Problem ist eine Teilmenge der ersten. Ordnen Sie jeder Kante einfach Gewicht 1 zu und Sie erhalten den Pfad mit der kleinsten Anzahl an Kanten. Das eigentliche Problem (obwohl klein) ist, dass weder Dijkstra noch Floyd-Warshal einen kürzesten Weg vom Knoten zurück zu sich selbst finden. Sie müssen sie ein wenig zwicken. –
Danke..ich benutzte die modifizierte Version von Dijkstra und es funktionierte –