Ich brauche einen Algorithmus, der den kürzesten Weg zwischen zwei Punkten auf einer Karte findet wobei die Straßenentfernung durch eine Zahl angegeben wird.
was gegeben ist: Start Stadt A Ziel Stadt Z
Liste der Entfernungen zwischen 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 Dijkstra's Algorithmus verwenden, aber er findet die kürzeste Entfernung zu allen Zielen, nicht nur zu einem.
Jeder Vorschlag ist willkommen.
Wie SplinterReality sagte: "Es gibt keinen Grund, hier nicht den Dijkstra-Algorithmus zu verwenden".
Den nachstehenden Code habe ich von hier geklaut und so verändert, dass er das Beispiel in der Frage löst.
import java.util.PriorityQueue;
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;
class Vertex implements Comparable<Vertex>
{
public final String name;
public Edge[] adjacencies;
public double minDistance = Double.POSITIVE_INFINITY;
public Vertex previous;
public Vertex(String argName) { name = argName; }
public String toString() { return name; }
public int compareTo(Vertex other)
{
return Double.compare(minDistance, other.minDistance);
}
}
class Edge
{
public final Vertex target;
public final double weight;
public Edge(Vertex argTarget, double argWeight)
{ target = argTarget; weight = argWeight; }
}
public class Dijkstra
{
public static void computePaths(Vertex source)
{
source.minDistance = 0.;
PriorityQueue<Vertex> vertexQueue = new PriorityQueue<Vertex>();
vertexQueue.add(source);
while (!vertexQueue.isEmpty()) {
Vertex u = vertexQueue.poll();
// Visit each edge exiting u
for (Edge e : u.adjacencies)
{
Vertex v = e.target;
double weight = e.weight;
double distanceThroughU = u.minDistance + weight;
if (distanceThroughU < v.minDistance) {
vertexQueue.remove(v);
v.minDistance = distanceThroughU ;
v.previous = u;
vertexQueue.add(v);
}
}
}
}
public static List<Vertex> getShortestPathTo(Vertex target)
{
List<Vertex> path = new ArrayList<Vertex>();
for (Vertex vertex = target; vertex != null; vertex = vertex.previous)
path.add(vertex);
Collections.reverse(path);
return path;
}
public static void main(String[] args)
{
// mark all the vertices
Vertex A = new Vertex("A");
Vertex B = new Vertex("B");
Vertex D = new Vertex("D");
Vertex F = new Vertex("F");
Vertex K = new Vertex("K");
Vertex J = new Vertex("J");
Vertex M = new Vertex("M");
Vertex O = new Vertex("O");
Vertex P = new Vertex("P");
Vertex R = new Vertex("R");
Vertex Z = new Vertex("Z");
// set the edges and weight
A.adjacencies = new Edge[]{ new Edge(M, 8) };
B.adjacencies = new Edge[]{ new Edge(D, 11) };
D.adjacencies = new Edge[]{ new Edge(B, 11) };
F.adjacencies = new Edge[]{ new Edge(K, 23) };
K.adjacencies = new Edge[]{ new Edge(O, 40) };
J.adjacencies = new Edge[]{ new Edge(K, 25) };
M.adjacencies = new Edge[]{ new Edge(R, 8) };
O.adjacencies = new Edge[]{ new Edge(K, 40) };
P.adjacencies = new Edge[]{ new Edge(Z, 18) };
R.adjacencies = new Edge[]{ new Edge(P, 15) };
Z.adjacencies = new Edge[]{ new Edge(P, 18) };
computePaths(A); // run Dijkstra
System.out.println("Distance to " + Z + ": " + Z.minDistance);
List<Vertex> path = getShortestPathTo(Z);
System.out.println("Path: " + path);
}
}
Der obige Code erzeugt:
Distance to Z: 49.0
Path: [A, M, R, P, Z]
Vielleicht ist es zu spät, aber Niemand hat eine klare Erklärung geliefert, wie der Algorithmus funktioniert.
Die Idee von Dijkstra ist einfach, lassen Sie mich dies mit dem folgenden Pseudocode zeigen.
Dijkstra unterteilt alle Knoten in zwei verschiedene Gruppen. Unsettled und settled. Zu Beginn sind alle Knoten in der unbestimmten Menge, d.h. sie müssen noch ausgewertet werden.
In die Menge der settledNodes wird zunächst nur der Quellknoten aufgenommen. Ein bestimmter Knoten wird in die settled Menge verschoben, wenn der kürzeste Weg von der Quelle zu einem bestimmten Knoten gefunden wurde.
Der Algorithmus läuft so lange, bis die Menge der unsettledNodes leer ist. In jeder Iteration wählt er den Knoten mit dem geringsten Abstand zum Quellknoten aus der unsettledNodes-Menge aus. Er liest z.B. alle Kanten, die von der Quelle ausgehen und wertet jeden Zielknoten aus diesen Kanten aus, der noch nicht erledigt ist.
Wenn die bekannte Entfernung von der Quelle zu diesem Knoten durch die Verwendung der ausgewählten Kante verringert werden kann, wird die Entfernung aktualisiert und der Knoten wird zu den zu bewertenden Knoten hinzugefügt.
Bitte beachten Sie, dass Dijkstra auch den Vorgänger eines jeden Knotens auf dem Weg zur Quelle bestimmt. Das habe ich zur Vereinfachung aus dem Pseudocode herausgelassen.
Gutschriften an Lars Vogel
Führen Sie eine Liste der Knoten, zu denen Sie reisen können, sortiert nach der Entfernung von Ihrem Startknoten. Am Anfang wird nur Ihr Startknoten in der Liste stehen.
Solange Sie Ihr Ziel noch nicht erreicht haben: Besuchen Sie den Knoten, der dem Startknoten am nächsten liegt; dies wird der erste Knoten in Ihrer sortierten Liste sein. Wenn Sie einen Knoten besuchen, fügen Sie alle seine Nachbarknoten zu Ihrer Liste hinzu, außer denen, die Sie bereits besucht haben. Wiederholen Sie!