Finding shortest sequence of vertices in directed weighted graph

Let's say I have vertices u and v and some number n .

How can I calculate the length (sum of weights of edges) of the shortest sequence of vertices where there is an edge between every two vertices?

For example:

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

The sequence is starting with vertex u , ending with vertex v and it has n edges.

---

Since repetitions are allowed this can be solved in polynomial time by a slight variation of the Bellman-Ford algorithm. Let OPT(v,i) denote the optimal cost to reach v using i edges and let w(x,y) denote the weight between vertices x and y. Then we have the following recurrence:

OPT(v, i+1) = min { OPT(u, i) + w(u,v) }, over all edges (u,v).

This can be solved in a bottom up fashion in O(nm), where m is the number of edges. Here's the pseudocode.

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];

Note that if repetitions aren't allowed the problem is a generalization of the Hamiltonian path problem which is NP-Hard.

---

I think you can do a modified BFS, where you calculate the shortest path from U to V with no regard to edge weight. When you have found shortest path to V you backtrace through the shortest path edges while calculating the edge weight.

---

This can be done by Dynamic Programming. We first solve the problem with "n-1" for each node with an outgoing edge to "v" starting from node "u" then the solution is min(sum(sol(u,r),weight(r,v))) This algorithm is of O(n|vertices|).

链接地址: http://www.djcxy.com/p/35286.html

上一篇: 有向无环图中最短的正路径

下一篇: 在有向加权图中寻找最短的顶点序列