How it works
Dijkstra settles vertices in increasing distance and therefore cannot tolerate negative edges. Kruskal and Prim build minimum spanning trees by different strategies.
Choose Bellman-Ford over Dijkstra when negative weights are possible.
Common error
Running Dijkstra on a graph with negative edges, which finalises a vertex a later edge could still improve.
Worked example
Example
Weighted edges: A-B 2, A-C 5, B-C 1, B-D 4, C-D 1
All weights are positive
Goal 1: shortest path from A to D
Goal 2: minimum total weight connecting all verticesThe shortest A-to-D path is A-B-C-D with weight 4. A minimum spanning tree uses A-B, B-C, and C-D, also totaling 4 here, but the two optimization goals differ. Standard Dijkstra requires nonnegative edge weights.
Exercises
8.4.1 · Explain
Compare the A-B-D path with A-B-C-D using the displayed weights.
Show solution
A-B-D costs 2 + 4 = 6. A-B-C-D costs 2 + 1 + 1 = 4, which is shorter.
8.4.2 · Explain
Why does a minimum spanning tree not generally preserve every original shortest path?
Show solution
It minimizes the total weight needed to connect all vertices without cycles. That global objective differs from minimizing route length between particular endpoints.