Given a weighted (nonnegative weights) directed graph, Dijkstras algorithm or Bellman-Fords

algorithm can tell you a shortest path between two nodes. What if there are two (or n ) paths that

are shortest, is there an algorithm that will tell you all such paths?

One of your friend, Paul, suggest the following algorithm.

Use Dijkstras algorithm and find a first shortest path. Then, for each link in the graph remove it

(one at a time), launch Dijkstras algorithm again and see if it finds a new path (and put the link

in the graph again). For each pair of links do the same, etc. until you remove all arcs.

(i) Argue that the algorithm is exact, or provide a counter example to show that it is not exact.

What is the time complexity of the algorithm?

Another one of your friends, Peter, who did a search on Google comes with this second suggestion.

There are algorithms that compute the k-shortest paths, i.e., algorithms that not only find the

shortest path, but also k 1 other paths in non-decreasing order of cost. k is the number of

shortest paths to find. The problem can be restricted to have the k shortest paths without loops

(loopless k shortest path) or with loop. For instance, one can use the algorithm of Epstein [1] (its

complexity is O (m + nlogn + k ) where n is the number of nodes, m is the number of links and k

is the number of paths), and increase k until the length of an output path is larger than the length

of the shortest path (e.g., the first path).

(ii) You learn that Eppsteins algorithm does not require paths to be simple, i.e, they may contain

loops. What is the time complexity of the algorithm of Peter? Before answering to this last

question, provide the details on how you increase the k value from one call to Eppsteins algorithm

to the next.

(iii) Can the number of paths between two nodes be exponential? If you believe so, provide a

graph example in which this is the case. Otherwise, explain why it cannot be exponential.