Поиск кратчайшего маршрута с использованием алгоритма Дейкстры

Question

Мне нужно найти кратчайший маршрут между двумя вершинами графа. У меня есть матрица, содержащая все веса. Как мне это сделать? В настоящее время, у меня есть следующий код:

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 использует родительский массив для отслеживания кратчайшего пути от начала до конца. Вы начинаете с родителя [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

Как только вы достигнете конечной вершины, вы можете вернуть путь к исходной вершине, используя родительскую матрицу. Что-то вроде (если есть путь от источника к 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); 
} 

Примечание: путь будет в обратном порядке.