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のアルゴリズムは、開始から終了までの最短経路を追跡するために、親配列を使用しています。あなたはparent [end]で始まり、始めに戻るまで配列のエントリーに従います。

いくつかの擬似コード：あなたの機能を心配する必要は心配

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

デスティネーション頂点に到達すると、親マトリックスを使用して開始頂点までのパスをバックトラックできます。何かが好きです（送信元から宛先へのパスがある場合）。

注：パスは逆の順序です。