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

Question

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

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

Answer 1

编辑：哎呀，误读了这个问题。感谢@jfclavette 接受这个。旧答案在最后。

您要解决的问题称为旅行推销员问题。有许多潜在的解决方案，但它是 NP 完全的，因此您将无法解决大图。

老答案：

您要查找的内容称为图形的周长。它可以通过将节点到自身的距离设置为无穷大并使用Floyd-Warshall算法来解决。节点 i 的最短循环长度就是位置 ii 的入口。

Answer 2

在未加权的情况下：广度优先搜索。在加权情况下：Dijkstra 的.

Answer 3

在伪代码中：

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

要返回最短循环的实际路径，只需稍作修改。

Answer 4

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

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