path - 循环有向图中的最短路径

Question

我需要一个关于一个节点的有向图循环最短路径的示例（它应该从阳极到达图的所有节点将是输入）如果有一个示例我需要它在 c++ 或算法中非常感谢... ……

Answer 1

您需要找到它的最小生成树 。

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

Answer 2

在伪代码中：

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

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