首页 文章

具有指定边数的最短路径

提问于
浏览
1

我正在寻找一种算法,该算法在包含指定数量的边n的图中找到两个顶点(i和j)之间的最短路径 . 我有一个动态程序,查看到n-1边缘到目的地的最短路径,但我怎么能确定找到的最短路径从i开始?

2 回答

  • 1

    我猜边缘有不同的成本/长度,约束是有n个边,在i到j的所有路径中都有n个单独的边,目标是找到总成本/长度最小的边 .

    如果使用动态编程执行此操作,则重复发生

    spath(f, t, n): --- returns shortest path from 'f' to 't' that has 'n' edges
    
    spath(x, x, 0) = [x] --- path that has only one vertex
    spath(x, y, 0) = NO PATH --- when x != y
    
    spath(f, t, n) =
      min cost path over (x is any node that is connected to t):
         spath(f, x, n-1) + [t] (x can be appended because there is edge x - t)
    
  • 3

    你的措辞含糊不清 . n 是图表中的边数或路径中的跳数?如果是后者,那么它不再是最短的路径了 . 如果你的意思是前者,那么任何流行的shortest-path algorithm如Dijkstra都会奏效 . 如果你的意思是后者,那么从 i 开始 n 迭代BFS并在第n个边界找到你的 j . 如果's not there, then there'在 n 跳跃中没有从 ij 的路径 . 沿着BFS边界走下去读你的路径 .

相关问题