在有向赋权图中寻找最短顶点序列

Question

假设我有顶点u和v，还有一些数字n。

在每两个顶点之间有一条边的情况下，如何计算最短顶点序列的长度(边的权重之和)？

例如：

(u, e_1, u_2, e_2, ..., e_n, v)

该序列以顶点u开始，以顶点v结束，并具有n边。

Answer 1

由于允许重复，因此可以通过对贝尔曼-福特算法进行微小的变化来在多项式时间内解决此问题。设OPT(v，i)表示使用i条边到达v的最优成本，w(x，y)表示顶点x和y之间的权重。

OPT(v，i+1) = min { OPT(u，i) + w(u，v) }，在所有边(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困难的。

Answer 2

这可以通过动态编程来实现。我们首先用"n-1“解决问题，对于每个节点，从节点"u”开始向"v“输出边，然后解决方案是min(sum(sol(u,r),weight(r,v)))这个算法是O(n|顶点|)。