Which algorithm can I use to find the next to shortest path in a graph?

Question

I want to find the next shortest path between 2 vertices in a graph and the path has a positive cost.The next shortest path is allowed to share edges of the shortest path .Which algorithm can I use?

Answer 1

Use the K-shortest path algorithm, where k=2 for you, some sample reference:

Finding the k shortest paths. D. Eppstein. 35th IEEE Symp. Foundations of Comp. Sci., Santa Fe, 1994, pp. 154-165. Tech. Rep. 94-26, ICS, UCI, 1994. SIAM J. Computing 28(2):652-673, 1998.

http://www.ics.uci.edu/~eppstein/pubs/Epp-TR-94-26.pdf

Answer 2

I doubt this is optimal in terms of running time but:

1. Use Dijkstra's algorithm on graph G to get path P
2. For all edges E in path P:
3. -- If G - E is not connected, continue for next edge (go to 2)
4. -- Use Dijkstra's algorithm on G - E to find path X_i
5. -- If length of current X_i is shorter than all other X_i, save it
6. The X_i at the end of the for loop is the second shortest path

The second-shortest path can't go through all edges in P, but it could go through all but one of them, potentially. I assume by "second-shortest" that you don't use edges more than once, otherwise the second-shortest path could contain P.

Answer 3

One way is to use Floyd-Warshall's algorithm to find all pairs shortest path and then testing all intermediate edges is a sure - but perhaps not optimal way - to solve this. Here's a great explanation http://hatemabdelghani.wordpress.com/2009/07/04/second-shortest-path/

Answer 4

This is assuming you can reuse edges and nodes:

A straightfoward solution is do make an extension of the Djikstra Algorithm.

• Instead of storing for each node the smallest cost and its respective parent, store the two smallest costs (and their respective parents).

• For the priority queue, intead of storing nodes, store (node, i) pairs, so you know wether to use the 1st or 2nd path during propagation.

• Take care during the propagation phases to keep the multiple path values correctly updated.

(I might be missing some important details but the basic idea is here...)

Answer 5

Use the shortest path algorithm to find the shortest path, P.

You then can view this problem as a constraint satisfaction problem (where the constraint is "the shortest path which is not P") and, use a backtracking algorithm to find the shortest path which is not the shortest path you already found.

Answer 6

This answer assumes you are looking for the edge-disjoint second shortest path, which means the second shortest path cannot share any common edges with the shortest path.

Recall that the maximum flow in a network between two nodes A and B gives you the number of edge-disjoint paths between those two nodes. Also recall that algorithms such as Edmonds-Karp work by sending flow over a shortest path at each step.

So this problem only has a solution if the max flow between your two nodes is > 1, where each edge has a capacity of 1. If it does, find two augmenting paths as described in the Edmonds-Karp algorithm, and the second one is your second shortest.

See this problem and this solution to it (The description is in Chinese. I can't translate it, and babelfish can't really do it either, but won't admit it. The code is easy to follow though) for an example.

Answer 7

When you prefer a practical solution to an academic one, here is one.

I solved this by setting a penalty to the shortest path edges and running the search again.

E.g. shortest path has length 1000, penalty is 10%, so I search for a 2nd shortest path with 1000<=length<=1100.

In the worst case I find the previous shortest path.
In the best case I find a disjunct path with the same length.
In most cases I find a path sharing some locally optimal subpaths.

Increasing the penalty forces the algorithm to find alternative routes, while decreasing makes it sharing tolerant.

When I find the 2nd shortest path, I have to subtract the sum of penalties on shared edges from the computed length to get the real length.

For k-th shortest path I set the penalty to all edges used in previous k-1 shortest paths.

Answer 8

You're looking for k shortest path routing. Basically, run modified Dijkstra, but instead of keeping edges on the min-heap, keep all paths found so far.

I prefer working code since the devil is always in the detail:

@SuppressWarnings("unchecked")
public static Iterable<Integer>[] kShortestPaths(EdgeWeightedDigraph g, int s, int t, int k) {
    if (k <= 0) throw new IllegalArgumentException("k must be positive");

    boolean[] visited = new boolean[g.V()];
    int[] count = new int[g.V()];
    MinPQ<Map.Entry<Map.Entry<Integer, Double>, Queue<Integer>>> heap = new MinPQ<>(
            comparingDouble(e -> e.getKey().getValue())
    );
    Queue<Integer>[] p = (Queue<Integer>[]) new Queue<?>[k];

    heap.insert(new SimpleImmutableEntry<>(new SimpleImmutableEntry<>(s, 0.0d), new Queue<>()));

    int i = 0;
    while (!heap.isEmpty()) {
        Map.Entry<Map.Entry<Integer, Double>, Queue<Integer>> node = heap.delMin();
        Integer u = node.getKey().getKey();
        if (count[u] >= k) break;

        Queue<Integer> pathU = node.getValue();
        visited[u] = true;
        pathU.enqueue(u);

        if (u == t) {
            p[i] = new Queue<>();
            for (int w : pathU) {
                p[i].enqueue(w);
            }
            i++;
        }

        if (count[u]++ <= k) {
            double costU = node.getKey().getValue();
            for (DirectedEdge e : g.adj(u)) {
                int v = e.to();
                if (!visited[v]) {
                    Queue<Integer> pathV = new Queue<>();
                    for (int w : pathU) {
                        pathV.enqueue(w);
                    }
                    heap.insert(new SimpleImmutableEntry<>(new SimpleImmutableEntry<>(v, e.weight() + costU), pathV));
                }
            }
        }
    }
    return p;
}

EdgeWeightedDigraph and MinPQ are from https://github.com/kevin-wayne/algs4.

k = 1, p = [0, 1, 2, 3]

k = 2, p = [0, 4, 5, 3]