我需要一个有向图循环的最短路径的示例再见一个节点(它应该达到图的所有节点从阳极将是输入)请如果有一个例子,我需要它在C++或算法非常感谢.........循环指导中的最短路径图
1
A
回答
1
您需要为它找到minimum spanning tree。
对于根据维基百科的有向图,您可以使用this算法。
+0
算法链接:http://en.wikipedia.org/wiki/Chu-Liu/Edmonds_algorithm。我无法将链接放在我的答案中。 – Naveen 2009-04-25 16:10:43
1
伪代码:
//INPUT: graph G = (V,E)
//OUTPUT: shortest cycle length
min_cycle(G)
min = ∞
for u in V
len = dij_cyc(G,u)
if min > len
min = len
return min
//INPUT: graph G and vertex s
//OUTPUT: minimum distance back to s
dij_cyc(G,s)
for u in V
dist(u) = ∞
//makequeue returns a priority queue of all V
H = makequeue(V) //using dist-values as keys with s First In
while !H.empty?
u = deletemin(H)
for all edges (u,v) in E
if dist(v) > dist(u) + l(u,v) then
dist(v) = dist(u) + l(u,v)
decreasekey(H,v)
return dist(s)
这个运行在每个顶点略有不同Dijkstra的。突变的Dijkstras 有几个关键的区别。首先,所有的初始距离都设为∞,即使是 也开始顶点。其次,必须首先将起始顶点放在队列中,以确保它首先脱落,因为它们都具有相同的优先级。最后, 变异Dijkstras返回到开始节点的距离。如果没有 路径返回到开始顶点,则距离保持∞。所有这些 从变异Dijkstras返回的最小值是最短路径。由于Dijkstras在O(| V |^2)的最坏情况下运行 ,并且min_cycle运行这种形式的Dijkstras | V |次, 最后的运行时间找到最短周期为O(| V |^3)。如果min_cyc返回 ∞,那么该图是非循环的。
要返回最短周期的实际路径,只需稍作修改即可。
相关问题
- 1. 图最短路径无限循环
- 2. 最短路径:标识导致负循环的边缘
- 3. 图最短路径?
- 4. 将循环图分解为最短路径子图的最小数目
- 5. JGraphT图最短路径
- 6. 最短路径
- 7. 彩色边图中的最短路径
- 8. 优先图中的最短路径
- 9. 图中最短路径的数量
- 10. Trie中的最短路径
- 11. 的Dijkstra最短路径算法无限循环
- 12. 最短路径不是图中的路径
- 13. DAG最短路径
- 14. 通过加权图的最短路径
- 15. 找到有向图的最短路径
- 16. Dag的最短路径
- 17. 直接非循环图中最长的路径
- 18. 稀疏循环图中最长的简单路径
- 19. 循环图中最长路径问题的优化
- 20. 定向未加权图中最长的非循环路径
- 21. C# - 最短路径地图查找
- 22. 谷歌地图。找到最短路径
- 23. 自定义地图最短路径
- 24. 最短路径Dijkstra Java
- 25. Python,圆形最短路径
- 26. OrientDB:在最短路径
- 27. 最短路径查找器
- 28. OrientDB获取最短路径()
- 29. 最短路径/伪代码
- 30. 最短路径tsp算法
Dupe http://stackoverflow.com/questions/789159/cycle-directed-graph – krosenvold 2009-04-25 16:04:25