Questions: Dijkstra's Shortest Path Algorithm in Routing

Question 1

A student argues that Dijkstra's greedy step — always confirming the minimum-cost tentative node — might miss a cheaper path discovered later through other nodes. Why is this concern unfounded in standard routing networks?

• A. Routers cache all possible paths, so any missed path is retrieved from cache
• B. The priority queue automatically re-examines all tentative nodes after each confirmation
• C. All link costs are non-negative, so no path through an unvisited node can be cheaper than a path already confirmed
• D. In practice, the greedy step occasionally produces suboptimal results, but the error is negligible

Answer: (C)

The correctness proof relies on non-negative edge weights. If all costs are ≥ 0, then adding any further edge to a path can only increase or maintain its total cost — it can never decrease it. So once a node is confirmed (selected as the minimum-cost tentative node), no future path through unvisited nodes can be cheaper. If negative weights were allowed, a 'cheaper' path could appear later, breaking the algorithm. This is why Dijkstra fails with negative weights.

Question 2

After running Dijkstra's algorithm, what does a router actually store in its forwarding table for use in packet delivery?

• A. The complete shortest-path tree so it can recompute optimal paths on demand for each packet
• B. Only the first hop toward each destination — the outgoing interface for each reachable network prefix
• C. The complete sequence of routers for every destination path through the network
• D. The total cost (distance) to each destination, updated on every packet arrival

Answer: (B)

A router only needs to know which interface to forward a packet through — the next hop. Once a packet takes the correct first hop, the next router applies its own forwarding table, and so on. Because all routers run Dijkstra on the same synchronized topology, their independent first-hop decisions produce globally consistent, loop-free paths. Storing full paths would be wasteful and scale poorly.

Question 3

In link-state routing with OSPF, every router in the network independently runs Dijkstra's algorithm on the same topology database, each computing a shortest-path tree rooted at itself.

• T. True
• F. False

Answer: True

This distributed independence is the key architectural property of link-state routing. Because every router has flooded its link-state advertisement to all others, all routers share an identical topology database. Each runs Dijkstra independently to compute its own SPT. The results are globally consistent even though no central coordinator exists — as long as all routers have the same database, their independent computations produce compatible forwarding decisions.

Question 4

Dijkstra's algorithm produces correct shortest paths even when some link costs are negative, as long as no cycle in the network has a negative total cost.

• T. True
• F. False

Answer: False

Dijkstra requires all individual edge weights to be non-negative — not just that no negative cycle exists. The greedy step's correctness depends on the property that confirmed paths cannot be improved by going through unvisited nodes. A single negative edge (even without a negative cycle) can violate this: a cheaper path through a not-yet-visited node might exist after a node is already confirmed. Bellman-Ford handles negative edges (without negative cycles) at the cost of higher time complexity.

Question 5

Explain why the greedy step in Dijkstra's algorithm — always selecting the minimum-cost tentative node and treating its shortest path as final — is guaranteed to produce correct results in a routing network.

Model answer: The greedy step is correct because all link costs are non-negative. When a tentative node v is selected as the cheapest unconfirmed node, the cost to reach it via the current best path is d(v). Any alternative path to v would have to pass through some other unconfirmed node u, whose current tentative cost is ≥ d(v). Since all remaining edge weights are ≥ 0, the cost through u can only be ≥ d(v). Therefore no cheaper path to v can exist, and confirming it as d(v) is correct.

This is a proof by contradiction: assume confirming v is wrong and a cheaper path exists. That cheaper path must pass through some unvisited node u. But u's tentative cost is already ≥ d(v), and adding the non-negative edge from u to v can only increase cost further. Contradiction. Non-negative weights are the essential precondition — the entire correctness argument collapses if any edge weight is negative, which is why Dijkstra cannot be used on networks with negative link costs.