Tìm tuyến đường ngắn nhất bằng thuật toán Dijkstra

Question

Tôi cần tìm tuyến đường ngắn nhất giữa 2 đỉnh của biểu đồ. Tôi có một ma trận, trong đó có tất cả các trọng lượng. Tôi làm nó như thế nào? Hiện tại, tôi có mã sau:

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

Nó hoạt động, nhưng, tôi không biết cách tìm tuyến đường ngắn nhất, ví dụ 1 và 3 và trả lại tuyến đường như 1 => 4 => 2 => 3.
Cảm ơn bạn trước.

Answer 1

Djikstra Thuật toán sử dụng các mảng phụ huynh để theo dõi con đường ngắn nhất từ ​​đầu đến cuối. Bạn sẽ bắt đầu ở cấp độ [parent] và làm theo các mục của mảng cho đến khi bạn bắt đầu trở lại.

Một số giả:

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

shortestPath.Reverse(); 

Chỉ có điều bạn lo lắng phải lo lắng về với chức năng của mình là có hay không sự bắt đầu và kết thúc giá trị được truyền vào là những giá trị thích hợp (dù có hoặc không thực sự đại diện cho đỉnh trong đồ thị của bạn , ví dụ).

Answer 2

Hãy thử QuickGraph giải pháp: http://quickgraph.codeplex.com/ (cũng có sẵn thông qua NuGet)

Answer 3

Khi bạn đạt đến đỉnh đích, bạn có thể quay lại đường dẫn đến đỉnh bắt đầu bằng ma trận gốc. Một cái gì đó như (có một con đường từ nguồn đến 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); 
} 

Lưu ý: đường dẫn sẽ theo thứ tự ngược lại.