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

Question

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

如果有示例，请提供C++代码或算法。

- Thaier Alkhateeb

Answer 1

编辑：糟糕，我误读了问题。感谢@jfclavette指出。旧答案在结尾处。

你试图解决的问题被称为旅行商问题。有许多潜在的解决方案, 但它是NP完全问题，因此你无法解决大型图形的问题。

旧答案：

你要找到的是图形的周长。可以通过将节点到自身的距离设置为无限远，并使用Floyd-Warshall算法来解决。然后从节点i开始的最短循环的长度就是ii位置的条目。

- moinudin

---

他想找到访问所有节点的最短路径，而不是返回原始节点的最短循环。至少这是我从问题中理解的。 - jfclavette

这可能并不是旅行商问题，因为问题中似乎没有限制节点必须恰好访问一次。因此，该问题不要求图具有哈密顿回路。 - jfclavette

此外，旅行商问题要求所有顶点都连接在一起。在上面的问题中，并没有说明图形的所有顶点都连接在一起。 - ChaimKut

Answer 2

在非加权情况下：广度优先搜索。 在加权情况下：Dijkstra算法。

- rjprins

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 返回 ∞，则图形为无环图。

要返回最短循环的实际路径，只需要进行轻微修改即可。

- agentargo

Answer 4

对于非加权图，BFS可以胜任。由于您的图中存在潜在的循环，因此您需要跟踪已访问的节点（无论如何，您都需要为BFS执行此操作）。

对于加权图，可以使用Bellman-Ford算法。它也能够检测到循环。

- leiz