Yet Another Blog

Problem

UVa – 10342

Given a simple weighted graph (having no loops and no multi-edges), we want to find for every two vertices a path between those vertices whose length is strictly greater than the length of the shortest path between them but still less than or equal to the length of any other path between them. Loops are allowed in our target path.

Solution

First use Floyd-Warshall to obtain shortest paths between all pairs. Let denote the shortest path between the vertices and . The shortest path between a vertex and itself is zero. If there is no path between and then .

Now use the following algorithm to obtain all-pairs second shortest paths. We will denote the second shortest path between a pair of vertices and as . Initially for any pair of vertices .

For each edge in
For each pair of vertices in
Let the path be the concatenation: , ,
If

The rationale behind that algorithm is as follows: Moving from a source vertex to a target vertex, if -at each vertex along our path- we move from our current vertex to an adjacent vertex that lies on the shortest path between the current vertex and the target vertex, we will eventually reach the target vertex throught shortest path. If, at one step, we made a mistake by moving to an adjacent vertex that doesn’t lie on the shortest path between the current vertex and the target vertex, we won’t reach our target vertex throught the shortest path. We need to know which wrong step will make us arrive through a path that is worse than the shortest path but still better than any other possible path. We also know that we have to make no more than one mistake since two mistakes will give us a path that is even worse than the second shortest path. So, for each pair of vertices and , we try to find all paths between and that is composed of a sequence of right steps (the shortest path between and some reachable vertex ) followed by an arbitrary step that could be our mistake (the edge ) then another sequence of right steps (the shortest path between and ). We search all such possible paths for a path that is longer than the shortest path (obtained through Floyd-Warshall) but still shorter than the rest.