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

发布于 2024-07-18 17:00:09 字数 92 浏览 4 评论 0原文

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

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

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

Hello爱情风 2024-07-25 17:00:09

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

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

旧答案：

您要查找的称为图形的周长。可以通过将节点到自身的距离设置为无穷大并使用 Floyd-Warshall 算法。从节点 i 开始的最短循环的长度就是位置 ii 的条目。

回复收藏 0 原文

苯莒 2024-07-25 17:00:09

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

回复收藏 0 原文

半世蒼涼 2024-07-25 17:00:09

在伪代码中：

//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 返回是最短路径。自从迪杰斯特拉斯运行以来
最坏的情况是 O(|V|^2) 且 min_cycle 运行这种形式的 Dijkstras |V| 次，
找到最短循环的最终运行时间是 O(|V|^3)。如果 min_cyc 返回
∞ 则该图是无环图。

要返回最短循环的实际路径，只需进行少量修改。

In Pseudocode:

//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)

This runs a slightly different Dijkstra's on each vertex. The mutated Dijkstras
has a few key differences. First, all initial distances are set to ∞, even the
start vertex. Second, the start vertex must be put on the queue first to make
sure it comes off first since they all have the same priority. Finally, the
mutated Dijkstras returns the distance back to the start node. If there was no
path back to the start vertex the distance remains ∞. The minimum of all these
returns from the mutated Dijkstras is the shortest path. Since Dijkstras runs
at worst in O(|V|^2) and min_cycle runs this form of Dijkstras |V| times, the
final running time to find the shortest cycle is O(|V|^3). If min_cyc returns
∞ then the graph is acyclic.

To return the actual path of the shortest cycle only slight modifications need to be made.

回复收藏 0 原文