在有向加权图中寻找最短的顶点序列
假设我有顶点u和v和一些数字n 。
如何计算每两个顶点之间存在边的最短顶点序列的长度（边的权重和）？
例如：
(u, e_1, u_2, e_2, ..., e_n, v)
该序列从顶点u开始，以顶点v结束，并且它具有n边。
由于允许重复，因此可以通过Bellman-Ford算法的轻微变化在多项式时间内解决。 设OPT（v，i）表示使用i边达到v的最优代价，令w（x，y）表示顶点x和y之间的权重。 然后我们有以下几次发生：
在所有边（u，v）上的OPT（v，i + 1）= min {OPT（u，i）+ w（u，v）}。
这可以用O（nm）以自下而上的方式来解决，其中m是边的数量。 这是伪代码。
function computeShortestPath (u, v, n):
foreach q in vertices:
OPT[q][0] = inf;
OPT[u][0] = 0;
for (i = 1; i <= n; i++):
foreach q in vertices:
OPT[q][i] = inf;
foreach (p,q) in edges:
OPT[q][i] = min(OPT[q][i], OPT[p][i-1] + w[p][q]);
return OPT[v][n];
请注意，如果不允许重复，则问题是NP-Hard哈密尔顿路径问题的泛化。
我认为你可以做一个修改后的BFS，在这里你可以计算从U到V的最短路径，而不考虑边缘权重。 当找到V的最短路径时，可以在计算边权重时通过最短路径边回溯。
这可以通过动态编程完成。 我们首先用“n-1”来解决这个问题，每个节点的输出边从“u”节点开始到“v”，那么解就是min(sum(sol(u,r),weight(r,v)))这个算法是O（n |顶点|）。
上一篇: Finding shortest sequence of vertices in directed weighted graph