使用Dijkstra算法尋找最短路徑

Question

我需要找到圖的2個頂點之間的最短路徑。我有一個矩陣，其中包含所有的權重。我該怎麼做？目前，我有以下代碼：

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

它的工作原理，但是，但是我不知道如何使它之間找到最短的路線，例如1和3，回到像1路=> 4 => 2 => 3。
在此先感謝。

Answer 1

Djikstra的算法使用父陣列來跟蹤從開始到結束的最短路徑。你會從父母開始[結束]，並按照數組中的條目操作，直到你回到開始狀態。

一些僞代碼：

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

shortestPath.Reverse(); 

你擔心唯一擔心你的功能是傳遞的起點和終點值是否是合適的值（無論他們是否實際上在圖形中表示頂點， 例如 ）。

Answer 2

嘗試QuickGraph溶液：http://quickgraph.codeplex.com/（也可通過的NuGet提供）

Answer 3

一旦你到達目標頂點，你可以使用父矩陣回溯到起始頂點的路徑。類似於（從源到目標有一條路徑）：

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

注意：路徑將按相反的順序排列。