Lecture Notes: Dijkstra and Prim
Weighted Graph Algorithms with Step-by-Step TikZ Examples
These notes explain the goal, intuition, proof idea, worked example, and a clean C++ implemen-
tation for the two most important greedy algorithms on weighted graphs.
Two common goals in weighted graphs
• Shortest path: from one source vertex, reach every other vertex as cheaply as possible.
This is the job of Dijkstra when all edge weights are nonnegative.
• Minimum spanning tree: connect all vertices using the smallest possible total edge
weight, with no cycles. This is the job of Prim.
1. Dijkstra’s Algorithm
Problem. Given a weighted graph and a starting vertex s, find the shortest distance from s to
every other vertex.
Plain-word description. Start from the source. Keep the best distance you know for
every vertex. Repeatedly choose the not-yet-finalized vertex with the smallest current
distance, declare it final, and try to improve the distances of its neighbors.
Core invariant
At every step, once a vertex is selected as the smallest not-yet-finalized distance, that distance
is already the true shortest-path distance.
Why the greedy choice is safe. All edge weights are nonnegative. So if vertex u already
has the smallest tentative distance, any other route to u that goes through some unfinished
vertex would only add more nonnegative weight. That route cannot beat the current value
of u. Hence once we settle u, we never need to change its distance again.
1
Algorithm outline
1. Set dist[s] = 0 and all other distances to ∞.
2. Put the source into a priority queue.
3. While the queue is not empty:
• take the vertex u with the smallest current distance,
• for every edge u → v with weight w, try to improve dist[v] using dist[u] + w.
4. If a distance improves, also store parent[v] = u so that the actual path can be
reconstructed later.
Worked example: step by step
We use the graph below, start from vertex 1, and show the state after each important step. A
gray vertex is already finalized. Red numbers are current distance estimates. Red arrows show
the relaxation that matters in that step.
∞ ∞ ∞ 9
3 6 4 6
2 3 4 2
2 9 5∞ 2 9 5
1
1 1
2 5 1 2 1
∞ 0 5
5 0
Step 1 Step 2
∞ 3 9 3
3 6 4 3 6 4
2 2
2 9 5 2 9 5
1 1
1 1
2 5 1 2 5 1
5 0 5 0
Step 3 Step 4
7 3 7 3
3 6 4 3 6 4
2 2
2 9 5 2 9 5
1 1
1 1
2 5 1 2 5 1
5 0 5 0
Step 5 Step 6
2
Reading the example.
• From vertex 1, we first discover tentative distances 5 to vertex 2, 9 to vertex 4, and 1
to vertex 5.
• The smallest tentative distance is at vertex 5, so we settle 5 next and improve vertex 4
from 9 to 3.
• Then we settle 4, giving vertex 3 a tentative value 9.
• Next we settle 2, which improves vertex 3 again from 9 to 7.
• Finally we settle vertex 3 and the algorithm is done.
Final distances from vertex 1 are
dist(1) = 0, dist(5) = 1, dist(4) = 3, dist(2) = 5, dist(3) = 7.
Recovering the actual path
Whenever we improve a vertex v through u, we store parent[v] = u. Then for any target
vertex we move backward through the parent array and reverse the order.
Example for the shortest path from 1 to 3 in this graph:
parent[3]=2, parent[2]=1, parent[1]=-1
so the path is 1 → 2 → 3.
Simple C++ implementation
The priority queue below is the usual max-heap in C++, so we push negative distances. That
way the smallest real distance comes out first.
#include <bits/stdc++.h>
using namespace std;
const long long INF = (long long)4e18;
int main() {
int n, m;
cin >> n >> m;
vector<vector<pair<int,int>>> adj(n + 1);
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
int start;
cin >> start;
vector<long long> dist(n + 1, INF);
vector<int> parent(n + 1, -1);
priority_queue<pair<long long,int>> pq;
3
dist[start] = 0;
[Link]({0, start});
while (![Link]()) {
long long d = -[Link]().first;
int u = [Link]().second;
[Link]();
if (d != dist[u]) continue;
for (int i = 0; i < (int)adj[u].size(); i++) {
int v = adj[u][i].first;
int w = adj[u][i].second;
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
parent[v] = u;
[Link]({-dist[v], v});
}
}
}
}
Complexity
With an adjacency list and a priority queue, Dijkstra runs in
O((n + m) log n),
where n is the number of vertices and m is the number of edges.
Important warning. Dijkstra requires all edge weights to be nonnegative. If negative
edges exist, the greedy decision is no longer safe.
2. Prim’s Algorithm
Problem. Given a connected, undirected, weighted graph, find a minimum spanning tree (MST):
a set of n − 1 edges that connects all vertices with minimum total cost.
Plain-word description. Start with any vertex. Grow one tree. At each step, look at all
edges that leave the current tree and choose the cheapest edge that adds a new vertex.
Core invariant
At every step, the cheapest edge that crosses from the current tree to the outside is safe to add
to some MST.
4
Why the greedy choice is safe. The current tree defines a cut: vertices already chosen
on one side, all remaining vertices on the other. The lightest edge crossing that cut can
always belong to an MST. If an MST did not contain it, we could add it, create a cycle,
and remove a crossing edge that is no lighter. The total weight would not increase.
Algorithm outline
1. Start from any vertex; it is the first vertex of the tree.
2. Maintain for every outside vertex the cheapest edge that can connect it to the current
tree.
3. Repeatedly choose the outside vertex with the smallest connection cost.
4. Add that vertex and its connecting edge to the tree.
5. Continue until all vertices are included.
Worked example: step by step
The following pictures show Prim’s algorithm growing a tree. Black edges are already part of
the tree, and the red edge is the new edge added in that step.
2 3 2 3
3
1 4 1 4
5 6 5 6
Step 1 Step 2
2 5 3 2 5 3
3 3
1 4 1 3 4
5 6 5 6
Step 3 Step 4
5
2 5 3 2 5 3
3 3
1 3 4 1 3 4
7
5 2 6 5 2 6
Step 5 Step 6
Reading the example.
• We start from vertex 1.
• The cheapest edge leaving the current tree is (1, 2) with weight 3.
• Then the cheapest new edge is (2, 3) with weight 5.
• Next we add (3, 6) with weight 3.
• Then we add (6, 5) with weight 2.
• Finally we add (6, 4) with weight 7.
The resulting MST uses the five edges
(1, 2), (2, 3), (3, 6), (6, 5), (6, 4)
and its total weight is
3 + 5 + 3 + 2 + 7 = 20.
Simple C++ implementation
Below is the standard adjacency-list implementation of Prim’s algorithm. Again we use a normal
C++ priority queue and store negative values.
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<vector<pair<int,int>>> adj(n + 1);
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
vector<bool> used(n + 1, false);
vector<int> parent(n + 1, -1);
vector<int> best(n + 1, (int)1e9);
priority_queue<pair<int,int>> pq;
int start = 1;
best[start] = 0;
6
[Link]({0, start});
long long total = 0;
while (![Link]()) {
int cost = -[Link]().first;
int u = [Link]().second;
[Link]();
if (used[u]) continue;
used[u] = true;
total += cost;
for (int i = 0; i < (int)adj[u].size(); i++) {
int v = adj[u][i].first;
int w = adj[u][i].second;
if (!used[v] && w < best[v]) {
best[v] = w;
parent[v] = u;
[Link]({-best[v], v});
}
}
}
}
Complexity
With an adjacency list and a priority queue, Prim’s algorithm runs in
O(m log n).
3. Dijkstra vs. Prim
Dijkstra Prim
Goal Shortest paths from one source Minimum spanning tree
Greedy choice Smallest tentative distance Cheapest edge leaving the
current tree
Needs source vertex? Yes Any starting vertex works
Works on directed Yes, if weights are nonnegative No, MST is for undirected
graphs? graphs
Output Distances, and optionally A tree with n − 1 edges
parents for paths
Main danger Negative edge weights break Disconnected graph gives a
correctness forest instead of one tree
Memory trick. Dijkstra asks: How cheaply can I get from the source to each vertex? Prim
asks: How cheaply can I connect all vertices together?
7
4. Practice prompts
• Change the Dijkstra example so that the edge (4, 1) has weight 4 instead of 9. Which
distances change?
• In the Prim example, what happens if the edge (2, 3) has weight 1 instead of 5? Which step
changes first?
• Modify the Dijkstra code to print the path from the source to a target vertex.
• Modify the Prim code to print the actual tree edges using the parent array.
Prepared in LaTeX with TikZ so the worked examples can be edited, extended, and reused in your own lecture
slides or notes.