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.
미리 감사드립니다. http://quickgraph.codeplex.com/ (NuGet 통해도 가능)

Answer 1

Djikstra 알고리즘의 시작에서 끝으로 최단 경로를 추적하기 위해 상위 배열을 사용

Answer 2

는 QuickGraph 용액을보십시오. parent [end]에서 시작하여 배열의 항목을 따라 가면 다시 시작할 수 있습니다.

일부 의사 : 당신이 걱정

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

shortestPath.Reverse(); 

만 일이 함수는 전달 된 시작과 끝 값이 실제로 그래프에 정점을 표현 여부 (해당 값인지 아닌지에 대해 걱정할 필요가 예를 들어,).

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

참고 : 경로는 역순입니다.