Question
In Section 4.5.1 we studied Dijkstra’s link-state routing algorithm for computing the unicast paths that are individually the least-cost paths from the source to all destinations. The union of these paths might be thought of as forming a least-unicast-cost path tree (or a shortest unicast path tree, if all link costs are identical). By constructing a counterexample, show that the least cost path tree is not always the same as a minimum spanning tree.
Answer
Consider the following graph:
Find the minimum spanning tree from node A using Dijkstra’s algorithm.
The minimum spanning from node A is AD, DC, CB.
The cost of minimum spanning tree can be calculated as 4+1+1 = 6.
Now calculate the least cost path with source node A.
The unicast paths according Dijkstra’s algorithm are individually least cost paths. The paths from source A are as follows:
- Node A unicast paths to nodes B and D with costs 5 and 4 respectively.
- Node D has unicast to node C with cost 1.
- Node C has unicast to node B with cost 1.
- Node B to node A unicast is ignored as already exists.
The least unicast cost is the union of all the unicasts paths. The cost is calculated as 4+5+6=15.
Therefore, the least unicast path cost tree and minimum spanning tree are not always same.