我有一张图,想用 Dijkstra 算法进行一些最短路径搜索(我并不真正关心算法,但 dijkstra 是我熟悉的算法)。
这是我拥有的图表的相关部分:
现在我按照 Quickgraph 文档进行 dijkstra 搜索:
//Build QuickGraph UndirectedGraph from our data
UndirectedGraph<int, Edge<int>> ug = g.CreateUndirectedQuickGraph();
Func<Edge<int>,double> weightFunc = (Edge<int> edge) =>
{
return 1; //without weights at this moment
};
var tryGetPath = ug.ShortestPathsDijkstra(weightFunc, 20);
IEnumerable<Edge<int>> path;
if (tryGetPath(23, out path))
foreach (var e in path)
Trace.WriteLine(e);
如您所见,我试图获得节点 20 和 23 之间的最短路径。我得到的输出是
20 -> 4
22 -> 4
23 -> 22
这似乎是对的,但我真的不明白如何从中提取节点路径。我期待的是:
20 -> 4
4 -> 22
22 -> 23
如何从此输出构建最终路径?
从 20 到 34 的示例:
20->3
5->3
8->5
9->8
36->9
36->11
34->11
注意36->11
在最后一条边之前是如何出现的。