Wyszukiwanie najkrótszej trasy z użyciem algorytmu Dijkstra

Question

Potrzebuję znaleźć najkrótszą trasę między 2 wierzchołkami wykresu. Mam matrycę, która zawiera wszystkie wagi. Jak mogę to zrobić? Obecnie mam następujący kod:

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

To działa, ale jednak nie wiem jak zrobić to znaleźć najkrótszą trasę między, na przykład 1 i 3, a powrót trasą jak 1 => 4 => 2 => 3.
Z góry dziękuję.

Answer 1

Algorytm Djikstra wykorzystuje tablicę nadrzędną śledzić najkrótszą drogę od początku do końca. Zaczynasz od rodzica [end] i podążaj za wpisami tablicy, dopóki nie wrócisz, aby zacząć.

Niektóre pseudokod:

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

shortestPath.Reverse(); 

Jedyne co martwić muszą się martwić o swoją funkcję, czy też nie, początkowe i końcowe wartości przekazywane w to odpowiednie wartości (czy rzeczywiście stanowią wierzchołki na wykresie , na przykład).

Answer 2

Spróbuj roztwór QuickGraph: http://quickgraph.codeplex.com/ (także dostępny poprzez Nuget)

Answer 3

Po dotarciu do wierzchołka docelowego można cofnąć ścieżkę do początkowego wierzchołka za pomocą macierzy macierzystej. Coś jak (biorąc pod uwagę ścieżkę od źródła do 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); 
} 

Uwaga: ścieżka będzie w odwrotnej kolejności.