循环指导中的最短路径图

我需要一个有向图循环的最短路径的示例再见一个节点（它应该达到图的所有节点从阳极将是输入）请如果有一个例子，我需要它在C++或算法非常感谢.........循环指导中的最短路径图

来源

2009-04-25 Thaier Alkhateeb

Dupe http://stackoverflow.com/questions/789159/cycle-directed-graph – krosenvold 2009-04-25 16:04:25

您需要为它找到minimum spanning tree。

对于根据维基百科的有向图，您可以使用this算法。

来源

2009-04-25 16:05:34 Naveen

算法链接：http：//en.wikipedia.org/wiki/Chu-Liu/Edmonds_algorithm。我无法将链接放在我的答案中。 – Naveen 2009-04-25 16:10:43

伪代码：

//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返回 ∞，那么该图是非循环的。

要返回最短周期的实际路径，只需稍作修改即可。

来源

2010-10-20 04:29:27 agentargo

循环指导中的最短路径图

回答

相关问题