Trovare il percorso più breve usando l'algoritmo Dijkstra

Question

Ho bisogno di trovare il percorso più breve tra 2 vertici di un grafico. Ho una matrice, che contiene tutti i pesi. Come posso farlo? Attualmente, ho il seguente codice:

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; 
    } 

Funziona, ma, comunque non so come farlo trovare il percorso più breve tra, ad esempio 1 e 3, e restituire il percorso come 1 => 4 => 2 => 3.
Grazie in anticipo.

Answer 1

algoritmo di Djikstra utilizza la matrice genitore di tracciare il percorso più breve dall'inizio alla fine. Cominceresti con il genitore [fine] e seguirai le voci dell'array finché non tornerai per iniziare.

Alcuni pseudocodice:

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

shortestPath.Reverse(); 

L'unica cosa che ti preoccupi deve preoccuparsi di con la vostra funzione è se i valori di inizio e fine passate in sono valori appropriati (anche se non rappresentano in realtà i vertici nel grafico , per esempio).

Answer 2

provare la soluzione QuickGraph: http://quickgraph.codeplex.com/ (disponibile anche tramite NuGet)

Answer 3

Una volta raggiunto il vertice di destinazione, è possibile tornare indietro del percorso al vertice iniziale utilizzando la matrice madre. Qualcosa di simile (dato c'è un percorso dalla sorgente alla dest):

void backtrack(int source, int dest, vector<int> &path) 
{ 
    path.push_back(dest); 

    for(int vertex = parent[dest]; vertex != source; vertex = parent[vertex]) 
    path.push_back(vertex); 

    path.push_back(source); 
} 

Nota: percorso sarà in ordine inverso.