Not the Best

Problem Title: Not the Best
LightOJ ID: 1099
Keywords: dijkstra, single source shortest path, graph

This is a graph problem where, instead of finding the shortest path from point A to point B (which is the usual setup in this type of problems), it asks for the second best path, which is a path that is strictly longer than the shortest path(s), possibly visiting any edge or vertex more than once.

This can be solved by modifying a traditional Dijkstra algorithm, although you need to do it carefully. The beauty of this problem is that it puts your knowledge of this algorithm to the test. If you don’t have a deep understanding on how this algorithm works, coming up with a solution from this angle might not be very easy.

Anyway, the solution I came up with basically involves keeping track of 2 distances for each vertex: the best distances from the source, and, of course, the second best distances from the source. To illustrate the idea, I’ll use the following pseudo-code for Dijkstra’s algorithm, based on a snippet from Wikipedia, slightly modified to illustrate an implementation based on a priority queue:

function Dijkstra(Graph, source):
    for each vertex v in Graph:
        dist[v] := infinity ;
        vis[v]  := false ;     // flag to tell if a vertex has been visited
    end for ;
    dist[source] := 0 ;

    Q := a priority queue of tuples (d,v) ;
    push (0,source) to Q ;

    while Q is not empty:
        u := second element of the tuple from the front of Q ;
        pop front element from Q ;

        if vis[u]:
            continue ;
        end if ;
        vis[u] := true ;

        for each neighbor v of u:
            alt := dist[u] + dist_between(u, v) ;
            if alt < dist[v]:
                dist[v] := alt ;
                push (dist[v], v) to Q ;
            end if ;
        end for ;
    end while ;
    return dist[] ;
end Dijkstra.

Straightforward enough. A couple of things to notice: The tuples that are stored in Q have two elements, the first one represents a distance, and the second a vertex number. These tuples are sorted inside the queue according to their contents, first by the first element, and then by their second element (much like how C++ STL pairs behave).

Make sure that you understand what every step of this algorithm does, otherwise now would be a good time to read and think a little more about it.

Not let’s see the modifications that could be used to solve this problem:

// Second best (shortest) paths from single source
function Dijkstra2(Graph, source):
    for each vertex v in Graph:
        // Two dimensions to represent the two best distances
        dist[1][v] := infinity ;
        dist[2][v] := infinity ;
        vis[1][v]  := false ;
        vis[2][v]  := false ;
    end for ;
    dist[1][source] := 0 ;

    Q := a priority queue of tuples (t,d,v) ;
    push (1, 0, source) to Q ;

    while Q is not empty:
        t := first element of the tuple from the front of Q ;
        u := third element of the tuple from the front of Q ;
        pop front element from Q ;

        if vis[t][u]:
            continue ;
        end if ;
        vis[t][u] := true ;

        for each neighbor v of u:
            alt := dist[t][u] + dist_between(u, v) ;
            if alt < dist[1][v]:
                dist[2][v] := dist[1][v] ;
                push (2, dist[2][v], v) to Q ;

                dist[1][v] := alt ;
                push (1, dist[1][v], v) to Q ;
            else if alt > dist[1][v] and alt < dist[2][v]:
                dist[2][v] := alt ;
                push (2, dist[2][v], v) to Q ;
            end if ;
        end for ;
    end while ;
    return dist[2][] ;
end Dijkstra2.

As you can see, the idea is pretty simple, but the changes require attention to important details.

First of all, notice that the dist and vis arrays are two-dimensional arrays now, and the first index could be 1 or 2, representing the best or second-best path respectively.

Also, at line 12, the tuples that we store in Q have three elements now, where the first one is an integer to represent the type of tuple (1 or 2, as described for the dist and vis arrays).

Finally, notice how the decisions on what to push to the queue are affected. If a new best distance to a vertex is found, then the previous one is bumped as the new second-best distance (lines 28-29).

Also, if the alternative distance is strictly larger than the best path, but is better than the second-best, then it needs to be used (line 33).