使用 Dijkstra 算法查找最短路线

本文关键字：短路 查找 Dijkstra 算法 使用 | 更新日期: 2023-09-27 18:34:56

我需要找到图的两个顶点之间的最短路径。我有一个矩阵，其中包含所有权重。我该怎么做？目前，我有以下代码： 

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 这样的路线。
提前谢谢。

使用 Dijkstra 算法查找最短路线

Djikstra 的算法使用父数组从头到尾跟踪最短路径。 您将从父[结束]开始并遵循数组的条目，直到您回到开头。

一些伪代码：

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

对于您的函数，您唯一需要担心的是传入的开始值和结束值是否是适当的值(例如，无论它们是否实际表示图中的顶点(。

到达目标顶点后，可以使用父矩阵回溯到起始顶点的路径。类似的东西(假设有一条从源到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);
}

注意：路径将按相反顺序排列。

相关文章：