Single-Source Shortest Path Problem and Dijkstra's Algorithm

CSCE-411 Design and Analysis of Algorithms Spring 2025 Instructor: Jianer Chen Office: PETR 428 Phone: 845-4259 Email: chen@cse.tamu.edu Notes 20: Dijkstra s algorithm

Single-Source Shortest Path Problem The following discussion is valid for both directed and undirected graphs. Problem. Given a weighted graph G and two vertices s and t in G, find a shortest path from s to t in G The weight of a path P is equal to the sum of edge weights over all edges in P Dijkstra s Idea: start from the vertex s, gradually grow a tree rooted at s, by adding the vertex that currently looks the best. https://www.w3schools.com/dsa/dsa_algo_graphs_dijkstra.php Notes 19: The Shortest Path Problem

Single-Source Shortest Path Problem The following discussion is valid for both directed and undirected graphs. Problem. Given a weighted graph G and vertices s and t, find a shortest path from s to t. Dijkstra s Idea: start from the vertex s, gradually grow a tree Ts rooted at s, by adding the vertex that currently looks the best. Dijkstra(G, s, t) 1. for (v=1; v n; v++) status[v] = unseen; 2. status[s] = in-tree; dist[s] = 0; 3. for (each edge [s, w]) status[w] = fringe; dad[w] = s; dist[w] = wt(s, w); 4. While (there are fringes) 4.1 pick the fringe v of minimum dist[v]; 4.2 status[v] = in-tree; 4.3 for (each edge [v, w]) 4.3.1 if (status[w] == unseen) status[w] = fringe; dad[w] = v; dist[w] = dist[v] + wt(v, w); 4.3.2 else if (status[w] == fringe) & (dist[w] > dist[v] + wt(v, w)) dad[w] = v; dist[w] = dist[v] + wt(v, w); 5. The array dad[1..n] gives the path from s. s fringe in-tree unseen status[1..n]: the status of vertices dad[1..n]: the parent of vertices dist[1..n]: the distance of vertices to s Notes 19: The Shortest Path Problem

Single-Source Shortest Path Problem The following discussion is valid for both directed and undirected graphs. Problem. Given a weighted graph G and vertices s and t, find a shortest path from s to t. Dijkstra s Idea: start from the vertex s, gradually grow a tree Ts rooted at s, by adding the vertex that currently looks the best. Dijkstra(G, s, t) 1. for (v=1; v n; v++) status[v] = unseen; 2. status[s] = in-tree; dist[s] = 0; 3. for (each edge [s, w]) status[w] = fringe; dad[w] = s; dist[w] = wt(s, w); 4. While (there are fringes) 4.1 pick the fringe v of minimum dist[v]; 4.2 status[v] = in-tree; 4.3 for (each edge [v, w]) 4.3.1 if (status[w] == unseen) status[w] = fringe; dad[w] = v; dist[w] = dist[v] + wt(v, w); 4.3.2 else if (status[w] == fringe) & (dist[w] > dist[v] + wt(v, w)) dad[w] = v; dist[w] = dist[v] + wt(v, w); 5. The array dad[1..n] gives the path from s. initialization Make s a vertex in the tree s Add the next vertex to the tree fringe in-tree unseen status[1..n]: the status of vertices dad[1..n]: the parent of vertices dist[1..n]: the distance of vertices to s Notes 19: The Shortest Path Problem

Single-Source Shortest Path Problem The following discussion is valid for both directed and undirected graphs. Problem. Given a weighted graph G and vertices s and t, find a shortest path from s to t. Dijkstra s Idea: start from the vertex s, gradually grow a tree Ts rooted at s, by adding the vertex that currently looks the best. complexity Dijkstra(G, s, t) 1. for (v=1; v n; v++) status[v] = unseen; 2. status[s] = in-tree; dist[s] = 0; 3. for (each edge [s, w]) status[w] = fringe; dad[w] = s; dist[w] = wt(s, w); 4. While (there are fringes) 4.1 pick the fringe v of minimum dist[v]; 4.2 status[v] = in-tree; 4.3 for (each edge [v, w]) 4.3.1 if (status[w] == unseen) status[w] = fringe; dad[w] = v; dist[w] = dist[v] + wt(v, w); 4.3.2 else if (status[w] == fringe) & (dist[w] > dist[v] + wt(v, w)) dad[w] = v; dist[w] = dist[v] + wt(v, w); 5. The array dad[1..n] gives the path from s. O(n) O(1) O(n) initialization Make s a vertex in the tree s n times O(n) O(1) Add the next vertex to the tree O(1) time per edge fringe in-tree unseen status[1..n]: the status of vertices dad[1..n]: the parent of vertices dist[1..n]: the distance of vertices to s O(n) Time = O(n2) Notes 19: The Shortest Path Problem

Single-Source Shortest Path Problem The following discussion is valid for both directed and undirected graphs. Problem. Given a weighted graph G and vertices s and t, find a shortest path from s to t. Dijkstra s Idea: start from the vertex s, gradually grow a tree Ts rooted at s, by adding the vertex that currently looks the best. complexity Dijkstra(G, s, t) 1. for (v=1; v n; v++) status[v] = unseen; 2. status[s] = in-tree; dist[s] = 0; 3. for (each edge [s, w]) status[w] = fringe; dad[w] = s; dist[w] = wt(s, w); 4. While (there are fringes) 4.1 pick the fringe v of minimum dist[v]; 4.2 status[v] = in-tree; 4.3 for (each edge [v, w]) 4.3.1 if (status[w] == unseen) status[w] = fringe; dad[w] = v; dist[w] = dist[v] + wt(v, w); 4.3.2 else if (status[w] == fringe) & (dist[w] > dist[v] + wt(v, w)) dad[w] = v; dist[w] = dist[v] + wt(v, w); 5. The array dad[1..n] gives the path from s. O(n) O(1) O(n) initialization Make s a vertex in the tree s n times O(n) O(1) Add the next vertex to the tree O(1) time per edge fringe in-tree unseen status[1..n]: the status of vertices dad[1..n]: the parent of vertices dist[1..n]: the distance of vertices to s O(n) Time = O(n2) Notes 19: The Shortest Path Problem

Single-Source Shortest Path Problem The following discussion is valid for both directed and undirected graphs. Problem. Given a weighted graph G and vertices s and t, find a shortest path from s to t. Dijkstra s Idea: start from the vertex s, gradually grow a tree Ts rooted at s, by adding the vertex that currently looks the best. complexity Dijkstra(G, s, t) 1. for (v=1; v n; v++) status[v] = unseen; 2. status[s] = in-tree; dist[s] = 0; 3. for (each edge [s, w]) status[w] = fringe; dad[w] = s; dist[w] = wt(s, w); 4. While (there are fringes) 4.1 pick the fringe v of minimum dist[v]; 4.2 status[v] = in-tree; 4.3 for (each edge [v, w]) 4.3.1 if (status[w] == unseen) status[w] = fringe; dad[w] = v; dist[w] = dist[v] + wt(v, w); 4.3.2 else if (status[w] == fringe) & (dist[w] > dist[v] + wt(v, w)) dad[w] = v; dist[w] = dist[v] + wt(v, w); 5. The array dad[1..n] gives the path from s. Use a min-heap H to store the fringes: 1. RetrieveMin(H): find the minimum, and restore the heap O(log n) time; 2. Insert(H, v): add a new fringe v and restore the heap O(log n) time; 3. Delete(H, v): delete v and restore the heap O(log n) time O(n) O(1) O(n) n times O(n) O(1) O(n) Time = O(n2) Notes 19: The Shortest Path Problem

Single-Source Shortest Path Problem The following discussion is valid for both directed and undirected graphs. Problem. Given a weighted graph G and vertices s and t, find a shortest path from s to t. Dijkstra s Idea: start from the vertex s, gradually grow a tree Ts rooted at s, by adding the vertex that currently looks the best. complexity Dijkstra(G, s, t) 1. for (v=1; v n; v++) status[v] = unseen; 2. status[s] = in-tree; dist[s] = 0; H = ; 3. for (each edge [s, w]) status[w] = fringe; dad[w] = s; dist[w] = wt(s, w); Insert(H, w); 4. While (there are fringes) 4.1 pick the fringe v of minimum dist[v]; 4.2 status[v] = in-tree; 4.3 for (each edge [v, w]) 4.3.1 if (status[w] == unseen) status[w] = fringe; dad[w] = v; dist[w] = dist[v] + wt(v, w); 4.3.2 else if (status[w] == fringe) & (dist[w] > dist[v] + wt(v, w)) dad[w] = v; dist[w] = dist[v] + wt(v, w); 5. The array dad[1..n] gives the path from s. Use a min-heap H to store the fringes: 1. RetrieveMin(H): find the minimum, and restore the heap O(log n) time; 2. Insert(H, v): add a new fringe v and restore the heap O(log n) time; 3. Delete(H, v): delete v and restore the heap O(log n) time O(n) O(1) O(n) n times O(n) O(1) v = RetrieveMin(H) Insert(H, w); Delete(H, w); dad[w] = v; dist[w] = dist[v] + wt(v, w); Insert(H, w); O(n) Time = O(n2) Notes 19: The Shortest Path Problem

Single-Source Shortest Path Problem The following discussion is valid for both directed and undirected graphs. Problem. Given a weighted graph G and vertices s and t, find a shortest path from s to t. Dijkstra s Idea: start from the vertex s, gradually grow a tree Ts rooted at s, by adding the vertex that currently looks the best. complexity Dijkstra(G, s, t) 1. for (v=1; v n; v++) status[v] = unseen; 2. status[s] = in-tree; dist[s] = 0; H = ; 3. for (each edge [s, w]) status[w] = fringe; dad[w] = s; dist[w] = wt(s, w); Insert(H, w); 4. While (there are fringes) 4.1 pick the fringe v of minimum dist[v]; 4.2 status[v] = in-tree; 4.3 for (each edge [v, w]) 4.3.1 if (status[w] == unseen) status[w] = fringe; dad[w] = v; dist[w] = dist[v] + wt(v, w); 4.3.2 else if (status[w] == fringe) & (dist[w] > dist[v] + wt(v, w)) dad[w] = v; dist[w] = dist[v] + wt(v, w); 5. The array dad[1..n] gives the path from s. Use a min-heap H to store the fringes: 1. RetrieveMin(H): find the minimum, and restore the heap O(log n) time; 2. Insert(H, v): add a new fringe v and restore the heap O(log n) time; 3. Delete(H, v): delete v and restore the heap O(log n) time O(n) O(1) O(n) O(n log n) n times O(n) O(1) O(log n) v = RetrieveMin(H) O(log n) Insert(H, w); O(1) time per edge Delete(H, w); dad[w] = v; dist[w] = dist[v] + wt(v, w); Insert(H, w); O(n) Time = O(n2) Time = O(m log n) Notes 19: The Shortest Path Problem

Single-Source Shortest Path Problem The following discussion is valid for both directed and undirected graphs. Problem. Given a weighted graph G and vertices s and t, find a shortest path from s to t. Dijkstra(G, s, t) 1. for (v=1; v n; v++) status[v] = unseen; 2. status[s] = in-tree; dist[s] = 0; H = ; 3. for (each edge [s, w]) status[w] = fringe; dad[w] = s; dist[w] = wt(s, w); Insert(H, w); 4. While (there are fringes) 4.1 v = min-weight fringe; RetrieveMin(H); 4.2 status[v] = in-tree; 4.3 for (each edge [v, w]) 4.3.1 if (status[w] == unseen) status[w] = fringe; dad[w] = v; dist[w] = dist[v] + wt(v, w); Insert(H, w); 4.3.2 else if (status[w] == fringe) & (dist[w] > dist[v] + wt(v, w)) Delete(H, w); dad[w] = v; dist[w] = dist[v] + wt(v, w); Insert(H, w); 5. The array dad[1..n] gives the path from s. Theorem. On a weighted graph of n vertices and m edges, Dijkstra s algorithm solves the shortest path problem in time O(m log n) or O(n2). Time = O(n2) (without the red part) O(m log n) (with the read part)

Single-Source Shortest Path Problem The following discussion is valid for both directed and undirected graphs. Problem. Given a weighted graph G and vertices s and t, find a shortest path from s to t. Dijkstra(G, s, t) 1. for (v=1; v n; v++) status[v] = unseen; 2. status[s] = in-tree; dist[s] = 0; H = ; 3. for (each edge [s, w]) status[w] = fringe; dad[w] = s; dist[w] = wt(s, w); Insert(H, w); 4. While (there are fringes) 4.1 v = min-weight fringe; RetrieveMin(H); 4.2 status[v] = in-tree; 4.3 for (each edge [v, w]) 4.3.1 if (status[w] == unseen) status[w] = fringe; dad[w] = v; dist[w] = dist[v] + wt(v, w); Insert(H, w); 4.3.2 else if (status[w] == fringe) & (dist[w] > dist[v] + wt(v, w)) Delete(H, w); dad[w] = v; dist[w] = dist[v] + wt(v, w); Insert(H, w); 5. The array dad[1..n] gives the path from s. Theorem. On a weighted graph of n vertices and m edges, Dijkstra s algorithm solves the shortest path problem in time O(m log n) or O(n2). (We will see that this holds only when all edge weights of the graph are non-negative.) Time = O(n2) (without the red part) O(m log n) (with the read part)

Single-Source Shortest Path Problem The following discussion is valid for both directed and undirected graphs. Problem. Given a weighted graph G and vertices s and t, find a shortest path from s to t. Dijkstra(G, s, t) 1. for (v=1; v n; v++) status[v] = unseen; 2. status[s] = in-tree; dist[s] = 0; H = ; 3. for (each edge [s, w]) status[w] = fringe; dad[w] = s; dist[w] = wt(s, w); Insert(H, w); 4. While (there are fringes) 4.1 v = min-weight fringe; RetrieveMin(H); 4.2 status[v] = in-tree; 4.3 for (each edge [v, w]) 4.3.1 if (status[w] == unseen) status[w] = fringe; dad[w] = v; dist[w] = dist[v] + wt(v, w); Insert(H, w); 4.3.2 else if (status[w] == fringe) & (dist[w] > dist[v] + wt(v, w)) Delete(H, w); dad[w] = v; dist[w] = dist[v] + wt(v, w); Insert(H, w); 5. The array dad[1..n] gives the path from s. Theorem. On a weighted graph of n vertices and m edges, Dijkstra s algorithm solves the shortest path problem in time O(m log n) or O(n2). (We will see that this holds only when all edge weights of the graph are non-negative.) Question: How do we ensure that Dijkstra s algorithm solves the problem in time not larger than the smaller of O(m log n) and O(n2)? Time = O(n2) (without the red part) O(m log n) (with the read part)