Den kürzesten Weg mit dem Dijkstra-Algorithmus finden

Question

Ich muss den kürzesten Weg zwischen zwei Knoten eines Graphen finden. Ich habe eine Matrix, die alle Gewichte enthält. Wie kann ich es tun? Derzeit habe ich den folgenden Code:

private int[] Dijkstra(int start, int end) 
    { 
     bool[] done = new bool[8]; 
     int[] parent = new int[8]; 
     for (int i = 0; i < parent.Length; i++) 
      parent[i] = -1; 
     int[] distances = new int[8]; 
     for (int i = 0; i < distances.Length; i++) 
      distances[i] = int.MaxValue; 
     distances[start] = 0; 
     int current = start; 
     while (!done[current]) 
     { 
      done[current] = true; 
      for (int i = 0; i < 8; i++) 
      { 
       if (graph[current, i] != int.MaxValue) 
       { 
        int dist = graph[current, i] + distances[current]; 
        if (dist < distances[i]) 
        { 
         distances[i] = dist; 
         parent[i] = current; 
        } 
       } 
      } 
      int min = int.MaxValue; 
      for (int i = 0; i < 8; i++) 
      { 
       if (distances[i] < min&&!done[i]) 
       { 
        current = i; 
        min = distances[i]; 
       } 
      } 
     } 
     return parent; 
    } 

Es funktioniert, aber, aber ich weiß nicht, wie es den kürzesten Weg zwischen zum Beispiel 1 und 3, und gibt die Route wie 1 => finden machen 4 => 2 => 3.
Vielen Dank im Voraus.

Answer 1

Djikstra-Algorithmus verwendet die übergeordnete Array vom Anfang bis zum Ende, den kürzesten Weg zu verfolgen. Du würdest bei eltern [end] beginnen und den Einträgen des Arrays folgen, bis du wieder startest.

Einige Pseudo-Code:

List<int> shortestPath = new List<int>(); 
int current = end; 
while(current != start) { 
    shortestPath.Add(current); 
    current = parent[current]; 
} 

shortestPath.Reverse(); 

Das Einzige, was Sie kümmern sich Sorgen zu machen mit Ihrer Funktion ist, ob die Start- und Ziel in gebenen Werte entsprechenden Werte sind (ob sie in Ihrem Diagramm darstellen Ecken tatsächlich , beispielsweise).

Answer 2

Versuchen QuickGraph Lösung: http://quickgraph.codeplex.com/ (auch erhältlich über NuGet)

Answer 3

Sobald Sie den Zielscheitelpunkt erreicht haben, können Sie den Pfad zum Ausgangsscheitelpunkt mithilfe der übergeordneten Matrix zurückverfolgen. Etwas wie (vorausgesetzt, es gibt einen Pfad von der Quelle zu dest):

Hinweis: Pfad wird in umgekehrter Reihenfolge sein.