Finding shortest sequence of vertices in directed weighted graph

Question

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.

krjampani krjampani · Accepted Answer · 2015-04-11T12:58:59

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.

Finding shortest sequence of vertices in directed weighted graph

2 Answers