查找使用Dijkstra算法的最短路线(Finding the shortest route usi

我需要找到一个图的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:

一旦你到达目的地的顶点，你可以原路返回的路径，使用父矩阵起始顶点。 喜欢的东西（因为有一个从源至目的的路径）：

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

注意：路径将是相反的顺序。

文章来源: Finding the shortest route using Dijkstra algorithm