Kürzeste Pfad zwischen zwei Knoten in einem Diagramm (Java)

Question

Ich habe ein Programm mit einem Graphen, dessen Knoten einige Prozesse darstellen, und die Prozessrechenzeit ist die Kosten des Knotens.Dieses Diagramm wird im Speicher als eine Liste von Knoten und jeder Nicken hat eine Liste von Eltern und Kindern und seine Ausführungszeit.

Ich muss den Pfad mit der minimalen Ausführungszeit finden.

• Jeder Knoten kann mit jedem anderen verbunden werden.
• Es gibt nur einen Startknoten und einen Endknoten.
• Ein Knoten kann verschiedene „Eltern“ haben und „Kinder“

Kann mir jemand sagen, der beste Weg, dies zu tun?

Answer 1

Sie können hierfür Dijkstra's Algorithm verwenden.

Answer 2

Eine Möglichkeit hierfür besteht in der Verwendung verschiedener Algorithmen für den kürzesten Pfad, z. B. Dijkstra's algorithm. Damit dies funktioniert, müssten Sie einen "Heap" codieren, eine Datenstruktur, in der der Knoten mit dem kleinsten Gewichtsalter oben liegt.

Die Idee hinter dem Algorithmus besteht darin, den Gesamtabstand vom Start zum aktuellen Knoten für die aktuelle Route zu verfolgen. Der übliche Greedy-Algorithmus ist einer, bei dem Sie einfach den Nachbarknoten mit dem kürzesten Pfad auswählen. Dijkstra erweitert dies, indem er den Knoten auswählt, der den kürzesten Gesamtabstand vom Startknoten zu diesem Knoten ergeben würde.

Answer 3

JGraph hat eine Implementierung der Dijkstra algorithm.

Answer 4

Dijkstra wurde bereits erwähnt, es gibt auch die A* algorithm, die unter bestimmten Bedingungen leistungsfähiger sein kann und aus der man viel lernen kann. Es gibt auch ein gutes Buch über Graph-Algorithmen mit vielen Java-Code-Beispielen von Robert Sedgewick, die ich vor einigen Jahren nützlich fand. Der Titel lautet "Algorithmen in Java, Teil 5: Graphalgorithmen".

Answer 5

Einige specificly auf Dijkstra-Algorithmus Noten in Java:

http://renaud.waldura.com/doc/java/dijkstra/

und eine Notiz über die Leistung:

Die Komplexität des Algorithmus von Dijkstra stark von der Komplexität der Prioritätswarteschlange Q. hängt Wenn diese Warteschlange naiv implementiert wird, wie ich sie zum ersten Mal einführte (dh sie wird bei jeder Iteration neu geordnet, um den Mininum-Knoten zu finden), führt der Algorithmus in O (n2) aus, wobei n die Anzahl der Knoten im Graphen ist.

Mit einer reellen Prioritätswarteschlange, die zu jeder Zeit geordnet ist, wie wir es implementiert haben, ist die Komplexität durchschnittlich O (n log m). Die Logarithmusfunktion stammt aus der Collection PriorityQueue-Klasse, einer Heap-Implementierung, die in log (m) ausgeführt wird. Mit einer reellen Prioritätswarteschlange, die zu jeder Zeit geordnet ist, wie wir sie implementiert haben, ist die Komplexität durchschnittlich O (n log m).