Chapter 4: Q18E (page 136)

In cases where there are several different shortest paths between two nodes (and edges have varying length),the most convenient of these paths is often the one with fewest edges. Forinstance, if nodes represent cities and edge lengths represent costs of flying between cities, theremight be many ways to get from cityto city t which all have the same cost. The mostconvenientof 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, thebestvalues 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 $l_{e}$ ; starting node $s \in V$ .
Output: The values of $b e s t [u]$ should be set for all nodes $u \in V$

Short Answer

Expert verified

The efficient algorithm is as follows:

Input: $G = (V, E)$ ,positive edge length $l_{e}$ ; starting node $s \in V$

Output: the values of $b e s t [u]$ should be set for all nodes $u \in V$ .

While $Q \neq ϕ$ do

$u \leftarrow v$ in Q with smallest distance

For all edges $(u, v) \in E$ do

If $d [v] > d [u] + l [u, v]$ then

$d [v] \leftarrow d [u] + l [u, v]$

$b e s t [v] \leftarrow b e s t [u] + 1$

If $b e s t [v] \leftarrow b e s t [u] + 1$ then

If $b e s t [v] > b e s t [u] + 1$ then

$b e s t [v] \leftarrow b e s t [u] + 1$

Step by step solution

Step 1:Explain the given information

Consider that there exists several shortest paths between two nodes. The path with the few edges is often considered as the convenient one.

For specific starting node ,

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

Give an efficient algorithm for the given problem.

The efficient algorithm is as follows:

Input: $G = (V, E)$ ,positive edge length $l_{e}$ ; starting node $s \in V$

Output: the values of $b e s t [u]$ should be set for all nodes .

$u \in V$

While $Q \neq ϕ$ do

$u \leftarrow v$ in Q with smallest distance

For all edges $(u, v) \in E$ do

If $d [v] > d [u] + l [u, v]$ then

$d [v] \leftarrow d [u] + l [u, v]$

$b e s t [v] \leftarrow b e s t [u] + 1$

If $d [v] = d [u] + l [u, v]$ then

If $b e s t [v] > b e s t [u] + 1$ then

$b e s t [v] \leftarrow b e s t [u] + 1$

The algorithm, checks for the empty queue and put the edge with shortest distance. If thesum of distance of the positive edge length and the distance of the next vertex less than the current vertex. Update the best vertex queue. If the sum of distance of the positive edge length and the distance of the next vertex equal to the current vertex. Then if the best of current vertex is greater than the previous one, update.

Therefore, the algorithm efficiently finds the path with the fewest edges.