Dijkstra's Algorithm for an Undirected Weighted Graph

Dijkstra's algorithm is used to find the shortest path from a source vertex to all other vertices in a graph. It works on graphs with non-negative edge weights. Below is the step-by-step algorithm:

---

Algorithm:

1. Initialization:

   • Create a set $S$ to track visited vertices.
   • Initialize the distance for each vertex: $\text{dist}(v) = \infty, \quad \forall v \in G$ Set the distance of the source vertex $\text{dist}(\text{source}) = 0$.

2. Priority Queue:

   • Use a priority queue (or min-heap) to select the vertex $u$ with the smallest distance $\text{dist}(u)$ among unvisited vertices.

3. Relaxation:

   • For each neighbor $v$ of $u$, update the distance: $\text{dist}(v) = \min(\text{dist}(v), \text{dist}(u) + \text{weight}(u, v))$

4. Repeat:

   • Add $u$ to the visited set $S$.
   • Continue until all vertices are visited or the priority queue is empty.

5. Output:

   • The array $\text{dist}$ gives the shortest distance from the source to all vertices.

---

Mathematical Representation:

1. Input:

   • Graph $G = (V, E)$, where $V$ is the set of vertices and $E$ is the set of edges with weights $w(u, v)$.
   • Source vertex $s$.

2. Initialization:

   • Distance array: $\text{dist}(v) = \infty \; \forall v \in V$, $\text{dist}(s) = 0$.
   • Priority queue $Q = \{ (v, \text{dist}(v)) \mid v \in V \}$.

3. Algorithm: $\text{while } Q \neq \emptyset:$

   • Extract $u$ with the smallest $\text{dist}(u)$.
   • For each neighbor $v$ of $u$: $\text{if } \text{dist}(u) + w(u, v) < \text{dist}(v):$ $\text{dist}(v) = \text{dist}(u) + w(u, v)$
     • Update $Q$ with the new distance.

4. Output: $\text{dist}(v) \quad \forall v \in V$

---

Example Problem:

Graph:

Vertices: $\{A, B, C, D\}$
Edges: $\{(A, B, 4), (A, C, 1), (C, B, 2), (B, D, 5), (C, D, 8)\}$
Source: $A$

Step-by-step Calculation:

1. Initialize: $\text{dist}(A) = 0, \text{dist}(B) = \infty, \text{dist}(C) = \infty, \text{dist}(D) = \infty$

2. First Iteration:

   • Select $A$: $\text{dist}(A) = 0$.
   • Update neighbors: $\text{dist}(B) = \min(\infty, 0 + 4) = 4$ $\text{dist}(C) = \min(\infty, 0 + 1) = 1$

3. Second Iteration:

   • Select $C$: $\text{dist}(C) = 1$.
   • Update neighbors: $\text{dist}(B) = \min(4, 1 + 2) = 3$ $\text{dist}(D) = \min(\infty, 1 + 8) = 9$

4. Third Iteration:

   • Select $B$: $\text{dist}(B) = 3$.
   • Update neighbors: $\text{dist}(D) = \min(9, 3 + 5) = 8$

5. Fourth Iteration:

   • Select $D$: $\text{dist}(D) = 8$.

6. Final Distances: $\text{dist}(A) = 0, \text{dist}(B) = 3, \text{dist}(C) = 1, \text{dist}(D) = 8$

---

Would you like more details or have further questions?

---

Follow-Up Questions:

1. Can you explain the role of the priority queue in Dijkstra's algorithm?
2. How does Dijkstra’s algorithm ensure all vertices are visited exactly once?
3. What happens if the graph has negative weights?
4. How does Dijkstra’s algorithm differ for a directed vs. undirected graph?
5. Can you demonstrate the algorithm using another example graph?

---

Tip: Always verify graph connectivity before applying Dijkstra’s algorithm; it assumes all vertices are reachable from the source.