In cases where there are several different shortest paths between two nodes (and edges hav...

In cases where there are several different shortest paths between two nodes (and edges have varying lengths), the most convenient of these paths is often the one with fewest edges. For instance, if nodes represent cities and edge lengths represent costs of flying between cities, there might be many ways to get from city s to city t which all have the same cost. The most convenient of these alternatives is the one which involves the fewest stopovers. Accordingly, for a specific starting node s, define

b e s t [u] = minimum number of edges in a shortest path from s to u.

In the example below, the best values for nodes S, A, B, C, D, E, F are 0,1,1,1,2,2, 3, respectively.

Give an efficient algorithm for the following problem.

Input: Graph G = (V, E); positive edge lengths le; starting node s ∈ V.

Output: The values of b e s t [u] should be set for all nodes u ∈ V.