我在寻找一种算法，它能在一个包含指定数量边的图中找到两个顶点（i和j）之间的最短路径，n。我有一个动态程序，它能看到到目的地的最短路径有n-1条边，但我如何能确定找到的最短路径从i开始？
最佳答案
我猜这些边有不同的代价/长度，约束条件是有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)