如何找到覆盖有向循环图中所有节点的最短路径？

Question

我需要一个来自一个节点 （它应该到达将作为输入的节点的图的所有节点）的有向循环图的最短路径的示例。

请如果有一个例子，我需要它在C++或算法。

Answer 1

编辑：哎呀，误读了这个问题。感谢@jfclavette提取这个。老答案在最后。

你试图解决的问题叫做Travelling salesman problem。有很多potential solutions，但它是NP完整的，所以你不能解决大图。

老答案：

你试图找到所谓的图形的girth。可以通过设置从节点到其自身到无穷远的距离并使用Floyd-Warshall算法来解决。从节点i开始的最短周期的长度就是位置ii中的条目。

Answer 2

对于非加权图，BFS将完成这项工作。由于图形中存在潜在的循环，因此您需要跟踪访问的节点（无论如何您都需要为BFS执行此操作）。

对于加权图，可以使用bellman-Ford算法。它也能够检测周期。

Answer 3

在未加权的情况下：Breadth first search。 在加权情况下：Dijkstra's。

Answer 4

伪代码：

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

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