IMG_0280.jpeg

# Lecture 16 ## Dijkstra's Algorithm ### Single-source shortest path problem * Given a graph $G=(V, E)$ and a source node $s \in V$, find the shortest path from s to every other vertex $v \in V$ ### Assumptions * The graph is directed * All edge weights are non-negative ### Idea * Main...

# Lecture 16 ## Dijkstra's Algorithm ### Single-source shortest path problem * Given a graph $G=(V, E)$ and a source node $s \in V$, find the shortest path from s to every other vertex $v \in V$ ### Assumptions * The graph is directed * All edge weights are non-negative ### Idea * Maintain a set $S$ of vertices whose final shortest-path weights from s have already been determined * Repeatedly select the vertex $u \in V-S$ with the minimum shortest-path estimate, add $u$ to $S$, and update the shortest-path estimates of all neighbors of $u$ that are not already in $S$ ### Relaxation For each vertex $v \in V$, we maintain $d[v]$, which is the shortest-path estimate from s to $v$ * Initialize: * $d[s] = 0$ * $d[v] = \infty$ for all other $v$ * Relaxation step: ``` RELAX (u, v, w) if d[v] > d[u] + w(u, v) then d[v] ← d[u] + w(u, v) π[v] ← u ``` ### Dijkstra's Algorithm ``` DIJKSTRA(G, s) 1. Initialize-Single-Source(G, s) 2. S ← Ø 3. Q ← V[G] 4. while Q ≠ Ø 5. u ← Extract-Min(Q) 6. S ← S ∪ {u} 7. for each vertex v ∈ Adj[u] 8. Relax(u, v, w) ``` ### Example The image is a step-by-step example of how Dijkstra's algorithm works on a graph. The graph has 5 vertices labeled A, B, C, D, and E. The source vertex is A. The algorithm maintains a table of shortest-path estimates d[v] from A to each vertex v, and a set S of vertices whose final shortest-path weights from A have already been determined. Each step of the algorithm selects the vertex u in V-S with the minimum shortest-path estimate, adds u to S, and updates the shortest-path estimates of all neighbors of u that are not already in S. The shortest path from A to each vertex is shown in the final step. * Step 0: Initialization * Step 1: Select A, update neighbors B and D * Step 2: Select B, update neighbor C * Step 3: Select D, update neighbor E * Step 4: Select C, update neighbor E * Step 5: Select E, done ### Analysis * The while loop is executed $|V|$ times * In each iteration, Extract-Min takes $O(\log V)$ time * The for loop is executed $|E|$ times in total * In each iteration, Relax takes $O(1)$ time * Total time: $O(V \log V + E)$ ### Correctness * Dijkstra's algorithm maintains the following invariant: At the start of each iteration of the while loop, $d[v] = \delta(s, v)$ for all $v \in S$ * Proof by induction: * Base case: Initially, $S = \emptyset$, so the invariant holds trivially * Inductive step: Assume that the invariant holds at the start of some iteration. Let $u$ be the vertex extracted from $Q$. Then $d[u] = \delta(s, u)$. After adding $u$ to $S$, the invariant still holds. ### Conclusion * Dijkstra's algorithm is a greedy algorithm that solves the single-source shortest path problem in $O(V \log V + E)$ time * It is a very efficient algorithm for finding shortest paths in graphs with non-negative edge weights * It is widely used in practice, for example, in routing protocols ## Breadth-First Search ### Idea * BFS is a special case of Dijkstra's algorithm where all edge weights are 1 * It can be implemented using a queue ### Algorithm ``` BFS(G, s) 1. for each vertex u ∈ V[G] - {s} 2. do color[u] ← WHITE 3. d[u] ← ∞ 4. π[u] ← NIL 5. color[s] ← GRAY 6. d[s] ← 0 7. π[s] ← NIL 8. Q ← Ø 9. ENQUEUE(Q, s) 10. while Q ≠ Ø 11. do u ← DEQUEUE(Q) 12. for each v ∈ Adj[u] 13. do if color[v] = WHITE 14. then color[v] ← GRAY 15. d[v] ← d[u] + 1 16. π[v] ← u 17. ENQUEUE(Q, v) 18. color[u] ← BLACK ``` ### Properties * BFS computes shortest-path distances from s to all vertices in $O(V+E)$ time * The path from s to $v$ computed by BFS has the minimum number of edges ### Example The image shows an example of how BFS works on a graph. The graph has 8 vertices labeled A, B, C, D, E, F, G, and H. The source vertex is A. The algorithm maintains a queue of vertices to visit. Each vertex is colored white, gray, or black. White vertices have not been discovered yet. Gray vertices have been discovered but not processed yet. Black vertices have been processed. The algorithm visits each vertex in the graph in order of its distance from the source vertex. The shortest path from A to each vertex is shown in the final step. * The vertices are explored layer by layer * The algorithm terminates when all vertices have been visited ### Application * BFS can be used to find the shortest path in an unweighted graph * It can also be used to find the connected components of a graph * It is widely used in practice, for example, in web crawling