Analysis of Dijkstra's Algorithm for Single-Source Shortest Path Problem

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

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(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. 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). 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. Why is Dijkstra correct? 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. 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. Why is Dijkstra correct (for positive edge weights)? 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. 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. Why is Dijkstra correct (for positive edge weights)? 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. When a vertex v becomes in-tree, the value dist[v] is the length of the shortest path from s to v, given in the tree. 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. Why is Dijkstra correct (for positive edge weights)? 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. When a vertex v becomes in-tree, the value dist[v] is the length of the shortest path from s to v, given in the tree. Proof. By induction on the number k of in-tree vertices. 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. Why is Dijkstra correct (for positive edge weights)? 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. When a vertex v becomes in-tree, the value dist[v] is the length of the shortest path from s to v, given in the tree. Proof. By induction on the number k of in-tree vertices. k = 1: s is the only in-tree vertex, dist[s] = 0. Assume the theorem is true for k-1. 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. Why is Dijkstra correct (for positive edge weights)? 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. When a vertex v becomes in-tree, the value dist[v] is the length of the shortest path from s to v, given in the tree. Proof. By induction on the number k of in-tree vertices. k = 1: s is the only in-tree vertex, dist[s] = 0. Assume the theorem is true for k-1. Let v be the k-th in-tree v s 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. Why is Dijkstra correct (for positive edge weights)? 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. When a vertex v becomes in-tree, the value dist[v] is the length of the shortest path from s to v, given in the tree. Proof. By induction on the number k of in-tree vertices. k = 1: s is the only in-tree vertex, dist[s] = 0. Assume the theorem is true for k-1. Let v be the k-th in-tree v s 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. Why is Dijkstra correct (for positive edge weights)? 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. When a vertex v becomes in-tree, the value dist[v] is the length of the shortest path from s to v, given in the tree. Proof. By induction on the number k of in-tree vertices. k = 1: s is the only in-tree vertex, dist[s] = 0. Assume the theorem is true for k-1. Let v be the k-th in-tree v s 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. Why is Dijkstra correct (for positive edge weights)? 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. When a vertex v becomes in-tree, the value dist[v] is the length of the shortest path from s to v, given in the tree. Proof. By induction on the number k of in-tree vertices. k = 1: s is the only in-tree vertex, dist[s] = 0. Assume the theorem is true for k-1. Let v be the k-th in-tree v s 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. Why is Dijkstra correct (for positive edge weights)? 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. When a vertex v becomes in-tree, the value dist[v] is the length of the shortest path from s to v, given in the tree. Proof. By induction on the number k of in-tree vertices. k = 1: s is the only in-tree vertex, dist[s] = 0. Assume the theorem is true for k-1. Let v be the k-th in-tree > 0 > 0 v s Time = O(n2) (without the red part) O(m log n) (with the read part) Contradiction!

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. Theorem. On a weighted graph of n vertices and m edges in which all edge weights are non-negative, Dijkstra s algorithm solves the shortest path problem in time O(m log n) or O(n2). 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. 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. Theorem. On a weighted graph of n vertices and m edges in which all edge weights are non-negative, Dijkstra s algorithm solves the shortest path problem in time O(m log n) or O(n2). 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. Discussion. 1. We can develop a version of Dijkstra s algorithm that solves the problem in time O(min{m log n, 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. Theorem. On a weighted graph of n vertices and m edges in which all edge weights are non-negative, Dijkstra s algorithm solves the shortest path problem in time O(m log n) or O(n2). 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. Discussion. 1. We can develop a version of Dijkstra s algorithm that solves the problem in time O(min{m log n, n2}) 2. Dijkstra s algorithm is independent of the vertex t. It finds the shortest path from s to EVERY vertex that is reachable from s, thus solves the Single-Source Shortest Path Problem. 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. Theorem. On a weighted graph of n vertices and m edges in which all edge weights are non-negative, Dijkstra s algorithm solves the shortest path problem in time O(m log n) or O(n2). 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. Discussion. 1. We can develop a version of Dijkstra s algorithm that solves the problem in time O(min{m log n, n2}) 2. Dijkstra s algorithm is independent of the vertex t. It finds the shortest path from s to EVERY vertex that is reachable from s, thus solves the Single-Source Shortest Path Problem. 3. How do we find the actual shortest path from s to a vertex using the output of Dijkstra s algorithm (i.e., the array dad[1..n])? 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. Theorem. On a weighted graph of n vertices and m edges in which all edge weights are non-negative, Dijkstra s algorithm solves the shortest path problem in time O(m log n) or O(n2). Discussion. s 1. We can develop a version of Dijkstra s algorithm that solves the problem in time O(min{m log n, n2}) 2. Dijkstra s algorithm is independent of the vertex t. It finds the shortest path from s to EVERY vertex that is reachable from s, thus solves the Single-Source Shortest Path Problem. 3. How do we find the actual shortest path from s to a vertex using the output of Dijkstra s algorithm (i.e., the array dad[1..n])?

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. Theorem. On a weighted graph of n vertices and m edges in which all edge weights are non-negative, Dijkstra s algorithm solves the shortest path problem in time O(m log n) or O(n2). Discussion. s 1. We can develop a version of Dijkstra s algorithm that solves the problem in time O(min{m log n, n2}) a b c 2. Dijkstra s algorithm is independent of the vertex t. It finds the shortest path from s to EVERY vertex that is reachable from s, thus solves the Single-Source Shortest Path Problem. Array dad[1..n] 3. How do we find the actual shortest path from s to a vertex using the output of Dijkstra s algorithm (i.e., the array dad[1..n])? b c s a 0 s a b

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. Theorem. On a weighted graph of n vertices and m edges in which all edge weights are non-negative, Dijkstra s algorithm solves the shortest path problem in time O(m log n) or O(n2). 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. Discussion. Discussion. 4. Dijkstra can be incorrect if there are negative edges. 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. Theorem. On a weighted graph of n vertices and m edges in which all edge weights are non-negative, Dijkstra s algorithm solves the shortest path problem in time O(m log n) or O(n2). 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. Discussion. 4. Dijkstra can be incorrect if there are negative edges. v 10 -8 s t 5 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. Theorem. On a weighted graph of n vertices and m edges in which all edge weights are non-negative, Dijkstra s algorithm solves the shortest path problem in time O(m log n) or O(n2). 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. Discussion. 4. Dijkstra can be incorrect if there are negative edges. v 10 -8 s t 5 Dijkstra would return the single arc [s, t] as the shortest path from s to t. 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. Theorem. On a weighted graph of n vertices and m edges in which all edge weights are non-negative, Dijkstra s algorithm solves the shortest path problem in time O(m log n) or O(n2). 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. Discussion. 4. Dijkstra can be incorrect if there are negative edges. v 10 -8 s t 5 Dijkstra would return the single arc [s, t] as the shortest path from s to t. Can we solve the shortest path problem when the graph has negative edges? 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. Solving the Shortest Path Problem on graphs with negative edges.

Single-Source Shortest Path Problem The following discussion is valid for both directed and undirected graphs. Problem. Solving the Shortest Path Problem on graphs with negative edges. Does the problem always make sense?

Single-Source Shortest Path Problem The following discussion is valid for both directed and undirected graphs. Problem. Solving the Shortest Path Problem on graphs with negative edges. Does the problem always make sense? -1 A B 20 18 10 9 S D T 5 15 2 12 3 6 E C 4

Single-Source Shortest Path Problem The following discussion is valid for both directed and undirected graphs. Problem. Solving the Shortest Path Problem on graphs with negative edges. Does the problem always make sense? -1 A B By repeating on a negative edge in an undirected graph, we can find a path from s to t whose length can be arbitrarily small. 20 18 10 9 S D T 5 15 2 12 3 6 E C 4

Single-Source Shortest Path Problem The following discussion is only for directed graphs. Problem. Solving the Shortest Path Problem on graphs with negative edges. Does the problem always make sense? -1 A B By repeating on a negative edge in an undirected graph, we can find a path from s to t whose length can be arbitrarily small. 20 18 10 9 S D T 5 15 2 12 3 6 E C 4

Single-Source Shortest Path Problem The following discussion is only for directed graphs. Problem. Solving the Shortest Path Problem on graphs with negative edges. Does the problem always make sense? -1 A B By repeating on a negative edge in an undirected graph, we can find a path from s to t whose length can be arbitrarily small. 20 18 10 9 S D T 5 15 2 12 3 6 E C 4 -1 A B 20 18 -2 2 S D T 5 15 11 12 3 6 E C 4

Single-Source Shortest Path Problem The following discussion is only for directed graphs. Problem. Solving the Shortest Path Problem on graphs with negative edges. Does the problem always make sense? -1 A B By repeating on a negative edge in an undirected graph, we can find a path from s to t whose length can be arbitrarily small. 20 18 10 9 S D T 5 15 2 12 3 6 E C 4 -1 A B By repeating on a negative cycle in a directed graph, we can find a path from s to t whose length can be arbitrarily small. 20 18 -2 2 S D T 5 15 11 12 3 6 E C 4

Single-Source Shortest Path Problem The following discussion is only for directed graphs. Problem. Solving the Shortest Path Problem on graphs with negative edges. Does the problem always make sense? The problem is meaningful only for directed graphs with no negative cycles. -1 A B By repeating on a negative edge in an undirected graph, we can find a path from s to t whose length can be arbitrarily small. 20 18 10 9 S D T 5 15 2 12 3 6 E C 4 -1 A B By repeating on a negative cycle in a directed graph, we can find a path from s to t whose length can be arbitrarily small. 20 18 -2 2 S D T 5 15 11 12 3 6 E C 4

Single-Source Shortest Path Problem The following discussion is only for directed graphs. Problem. Solving the Shortest Path Problem on graphs with negative edges. Does the problem always make sense? The problem is meaningful only for directed graphs with no negative cycles. -1 A B 20 18 10 9 Why is the shortest path problem on directed graphs with no negative cycles always meaningful? S D T 5 15 2 12 3 6 E C 4 -1 A B 20 18 -2 2 S D T 5 15 11 12 3 6 E C 4