C# 使用 Dijkstra 算法寻找最短路径
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/10674468/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Finding the shortest route using Dijkstra algorithm
提问by SirSergio
I need to find the shortest route between 2 vertices of a graph. I have a matrix, which contains all the weights. How can I do it? Currently, I have the following code:
我需要找到图形的 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;
}
It works, but, however I don't know how to make it find the shortest route between, for example 1 and 3, and return the route like 1=>4=>2=>3.
Thanks in advance.
它有效，但是，但是我不知道如何让它找到例如 1 和 3 之间的最短路线，并返回 1=>4=>2=>3 之类的路线。
提前致谢。
采纳答案by Travis
Djikstra's Algorithm uses the parent array to track the shortest path from start to end. You'd start at parent[end] and follow the entries of the array until you got back to start.
Djikstra 算法使用父数组来跟踪从开始到结束的最短路径。您将从 parent[end] 开始并按照数组的条目进行操作，直到您重新开始。
Some pseudocode:
一些伪代码：
List<int> shortestPath = new List<int>();
int current = end;
while( current != start ) {
shortestPath.Add( current );
current = parent[current];
}
shortestPath.Reverse();
Only thing you worry have to worry about with your function is whether or not the start and end values passed in are appropriate values (whether or not they actually represent vertices in your graph, for example ).
对于函数，您唯一需要担心的是传入的开始值和结束值是否是合适的值（例如，它们是否实际上代表了图中的顶点）。
回答by Helstein
Once you reach the destination vertex you can backtrack the path to the starting vertex using the parent matrix. Something like (given there's a path from source to 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);
}
Note: path will be in reverse order.
注意：路径顺序相反。
