Ich brauche einen Algorithmus, um den kürzesten Weg zwischen zwei Punkten in einer Karte zu finden wo die Straßenentfernung durch eine Nummer angezeigt wird.
was gegeben ist: Start Stadt A Zielstadt Z
Liste der Entfernungen zwischen den Städten:
A - B: 10
F - K: 23
R - M: 8
K - O: 40
Z - P: 18
J - K: 25
D - B: 11
M - A: 8
P - R: 15
Ich dachte, ich könnte den Algorithmus von Dijkstra verwenden, findet jedoch die kürzeste Entfernung zu allen Zielen. nicht nur eins.
Jeder Vorschlag wird geschätzt.
Wie SplinterReality gesagt hat: There's no reason not to use Dijkstra's algorithm here.
Der Code unten, den ich aus hier geklaut habe und änderte es, um das Beispiel in der Frage zu lösen.
%Vor%Der obige Code erzeugt:
%Vor%Geschätzter sanjan:
Die Idee hinter dem Algorithmus von Dijkstra besteht darin, alle Knoten des Graphen geordnet zu untersuchen. Der Algorithmus speichert eine Prioritätswarteschlange, in der die Knoten nach den Kosten von Anfang an geordnet sind, und bei jeder Iteration des Algorithmus werden die folgenden Operationen ausgeführt:
Es stimmt, dass der Algorithmus die Kosten für den Pfad zwischen dem Start (A in Ihrem Fall) und allen anderen Knoten berechnet, aber Sie können die Exploration des Algorithmus stoppen, wenn er das Ziel erreicht (Z in Ihrem Beispiel) ). An diesem Punkt kennen Sie die Kosten zwischen A und Z und den Pfad, der sie verbindet.
Ich empfehle Ihnen, eine Bibliothek zu verwenden, die diesen Algorithmus implementiert, anstatt Ihren eigenen zu programmieren. In Java können Sie sich die Hipster-Bibliothek ansehen, die eine sehr benutzerfreundliche Methode zum Generieren des Diagramms und zum Starten der Suchalgorithmen bietet.
Hier haben Sie ein Beispiel, wie Sie das Diagramm definieren und Dijstra mit Hipster verwenden können.
%Vor%Sie müssen nur die Definition des Graphen für Ihren eigenen ersetzen und dann den Algorithmus wie im Beispiel instanziieren.
Ich hoffe, das hilft!
Das ist vielleicht zu spät, aber Niemand hat eine klare Erklärung dafür geliefert, wie der Algorithmus funktioniert
Die Idee von Dijkstra ist einfach, lassen Sie mich das mit dem folgenden Pseudocode zeigen.
Dijkstra unterteilt alle Knoten in zwei unterschiedliche Mengen. Ungeregt und erledigt. Anfangs sind alle Knoten in der nicht-gesetzten Menge, z.B. Sie müssen noch ausgewertet werden.
Zunächst wird nur der Quellknoten in den Satz von settledNodes aufgenommen. Ein bestimmter Knoten wird in den Settled Set verschoben, wenn der kürzeste Pfad von der Quelle zu einem bestimmten Knoten gefunden wurde.
Der Algorithmus wird ausgeführt, bis der Satz "unsettledNodes" leer ist. In jeder Iteration wählt es den Knoten mit dem niedrigsten Abstand zum Quellknoten aus dem SetsetsetsetsetablesetNodes aus. Z.B. Es liest alle Kanten, die von der Quelle ausgehen und wertet jeden Zielknoten von diesen Kanten aus, die noch nicht abgerechnet sind.
Wenn die bekannte Entfernung von der Quelle zu diesem Knoten reduziert werden kann, wenn die ausgewählte Kante verwendet wird, wird die Entfernung aktualisiert und der Knoten wird zu den Knoten hinzugefügt, die ausgewertet werden müssen.
Bitte beachten Sie, dass Dijkstra auf dem Weg zur Quelle auch den Pre-Nachfolger jedes Knotens ermittelt. Ich habe das aus dem Pseudocode weggelassen, um es zu vereinfachen.
Dank an Lars Vogel
Pflegen Sie eine Liste der Knoten, zu denen Sie reisen können, sortiert nach der Entfernung von Ihrem Startknoten. Zu Beginn wird nur Ihr Startknoten in der Liste sein.
Wenn Sie Ihr Ziel nicht erreicht haben: Rufen Sie den Knoten auf, der dem Startknoten am nächsten liegt. Dies ist der erste Knoten in Ihrer sortierten Liste. Wenn Sie einen Knoten besuchen, fügen Sie alle benachbarten Knoten zu Ihrer Liste hinzu, mit Ausnahme der Knoten, die Sie bereits besucht haben. Wiederholen!