我需要找到图的两个顶点之间的最短路线。我有一个矩阵,其中包含所有权重。我该怎么做?目前,我有以下代码:
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 算法使用父数组来跟踪从开始到结束的最短路径。您将从parent[end] 开始并跟踪数组的条目,直到回到开始为止。
一些伪代码:
List<int> shortestPath = new List<int>();
int current = end;
while( current != start ) {
shortestPath.Add( current );
current = parent[current];
}
shortestPath.Reverse();
对于函数,您唯一需要担心的是传入的开始值和结束值是否是适当的值(例如,它们是否实际上代表图形中的顶点)。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)