What is Dijkstra’s Algorithm?

Dijkstra’s algorithm finds the shortest path between a starting node and other nodes in a weighted graph by always exploring the closest unvisited node next.

Graph Theory & Dijkstra Pathfinder - Discrete Math

Pathfinder Router

Drag any city node above to reshape the travel network routes. Select start/destination to compute the optimal flight path.

Start City

Destination City

Shortest Route Solution

BLR → BOM → DEL

Total Duration:3 hours

Graph Theory & Pathfinder

GRAPH

Graph theory analyzes networks of Vertices (nodes) and Edges (links). In travel networks, edges have weights representing distance or travel time. Dijkstra's algorithm finds the absolute shortest route from a starting node to all others by iteratively visiting the closest unvisited vertex and updating neighbor path costs.

D(v) = \min(D(v), D(u) + w(u, v))

Whiteboard Solver Steps

Step 1

Initialize Dijkstra Node Table

Visual Guide: - Set the starting node distance to $0$ , and all other nodes to $\infty$ . - Set up a priority queue to always inspect the closest unvisited city first.

D(BLR) = 0, \quad D(v) = \infty \text{ for all } v \neq BLR

Step 2

Step-by-Step Priority Queue Traversals

Dijkstra Log:

Visiting BLR (Current shortest dist = 0).

- Relaxing neighbor BOM: updated path distance from Infinity to 1 (via BLR)
- Relaxing neighbor HYD: updated path distance from Infinity to 1 (via BLR)
- Relaxing neighbor MAA: updated path distance from Infinity to 1 (via BLR)

Visiting BOM (Current shortest dist = 1).

- Relaxing neighbor DEL: updated path distance from Infinity to 3 (via BOM)

Visiting MAA (Current shortest dist = 1).

- Relaxing neighbor CCU: updated path distance from Infinity to 3 (via MAA)

Visiting HYD (Current shortest dist = 1).

Visiting DEL (Current shortest dist = 3).

\begin{aligned}\text{Path: } BLR \rightarrow BOM \rightarrow DEL \\ \text{Total Travel Time: } 3 \text{ hours}\end{aligned}

Step 3

Shortest Path Selection Summary

Why this matters: - Without Dijkstra's algorithm, finding the shortest path across large graphs (like Google Maps or network routers) would require checking every possible permutation, which is computationally impossible for large graphs. - Dijkstra resolves this in $O(V^2)$ (or $O(E \log V)$ ) time, making GPS pathfinding, flight routing, and network packet delivery fast and efficient.

\text{Shortest Route: } BLR \rightarrow BOM \rightarrow DEL \quad \text{Cost: } 3 \text{ hrs}

RV Anveshana