Graph Algorithms Shortest Path Dijkstra

Dijkstra's Algorithm Visualizer

Find the shortest path from a start node to all other nodes in a weighted graph using Dijkstra's algorithm with a priority queue.

Theory

Dijkstra's algorithm finds the shortest path between nodes in a weighted graph with non-negative edge weights. It uses a priority queue to always expand the node with the smallest tentative distance, guaranteeing the shortest path when weights are positive.

Strategy: Greedily select the unvisited node with smallest distance, update neighbors' distances if shorter path found
Time Complexity: O((V + E) log V) with binary heap priority queue
Space Complexity: O(V) for distance array and priority queue
Common Applications:
- Network routing protocols
- GPS navigation systems
- Minimum cost path problems
- Game pathfinding with costs

Problem Statement

Given a weighted graph and a starting node, compute the shortest path distances to all reachable nodes. Use the visualizer to step through Dijkstra's algorithm, observing how the priority queue selects nodes and updates distances across the graph.

priority_queue.txt

1// Min-Heap Priority Queue
2struct PriorityQueue {
3Node[] heap;
4int[] distances;
5bool[] visited;
6}
7
8// extract-min → smallest distance

dijkstra_anatomy.svg

graph.svg — Dijkstra's Visualization

Current

Visited

In Queue

Unvisited

Start: Ready to start

Traversal State

priority_queue.log

Min-Heap Priority Queue

[ ]

distances.log

Shortest Distances

[ ]

Algorithm & Pseudocode

dijkstra_algorithm.txt

1// Dijkstra's with priority queue
2function dijkstra(graph, start):
3dist = array(INF)
4dist[start] = 0
5pq = priority_queue()
6pq.insert(start, 0)
7visited = set()
8
9while pq is not empty:
10node, cost = pq.extract_min()
11if node in visited: continue
12visited.add(node)
13for neighbor, weight in graph[node]:
14if dist[neighbor] > dist[node] + weight:
15dist[neighbor] = dist[node] + weight
16pq.insert(neighbor, dist[neighbor])

complexity.md

Aspect	Complexity
Time	O((V + E) log V)
Space	O(V)
Greedy Choice	Min Distance

Implementation

Language:

dijkstra.c

1#include <stdio.h>
2#include <stdlib.h>
3#define INF 99999
4#define MAX 100
5
6int graph[MAX][MAX];
7int dist[MAX];
8int visited[MAX];
9
10int minDistance(int n) {
11int min = INF, min_index;
12for (int v = 0; v < n; v++) {
13if (!visited[v] && dist[v] <= min) {
14min = dist[v]; min_index = v;
15}
16}
17return min_index;
18}
19
20void dijkstra(int start, int n) {
21for (int i = 0; i < n; i++) {
22dist[i] = INF; visited[i] = 0;
23}
24dist[start] = 0;
25
26for (int count = 0; count < n - 1; count++) {
27int u = minDistance(n);
28visited[u] = 1;
29for (int v = 0; v < n; v++) {
30if (!visited[v] && graph[u][v] && dist[u] != INF && dist[u] + graph[u][v] < dist[v]) {
31  dist[v] = dist[u] + graph[u][v];
32}
33}
34}
35
36printf("Vertex\tDistance from Source\n");
37for (int i = 0; i < n; i++) {
38if (dist[i] == INF) printf("%d\t\t∞\n", i);
39else printf("%d\t\t%d\n", i, dist[i]);
40}
41}
42
43int main() {
44int n = 6;
45// build adjacency matrix with weights ...
46printf("Dijkstra's Algorithm:\n");
47dijkstra(0, n);
48return 0;
49}

Explanation

1. Distance Array (line 7): Initialized to INT_MAX (infinity), then start node set to 0. This stores the shortest known distance from source to each node.

2. minDistance() Function (lines 9-16): Performs linear search O(V) through all unvisited nodes to find minimum distance. Returns index of nearest unvisited node. Called V times in the algorithm.

3. Main Loop (lines 18-33): Runs V-1 iterations. Each iteration: (a) selects closest unvisited node u, (b) marks u as visited, (c) checks all neighbors of u for relaxation: if dist[u]+weight < dist[v], update dist[v]. This is the core relaxation step.

4. Edge Relaxation (lines 26-30): Updates neighbor distances if path through current node is shorter. Formula: new_dist = dist[current] + edge_weight. Only updates if this is smaller than previously known distance.

5. Time Complexity O(V²): V iterations of main loop × V searches in minDistance() = O(V²). Suitable for dense graphs where E ≈ V². Without heap optimization, linear search dominates. Consider priority queue (binary heap) for sparse graphs to reduce to O((V+E) log V).

dijkstra.py

1import heapq
2from collections import defaultdict
3
4def dijkstra(graph, start):
5"""Find shortest path from start to all nodes"""
6distances = {node: float('inf') for node in graph}
7distances[start] = 0
8pq = [(start, 0)]  # (distance, node)
9visited = set()
10
11while pq:
12cost, node = heapq.heappop(pq)
13if node in visited:
14continue
15visited.add(node)
16
17for neighbor, weight in graph[node]:
18alt = distances[node] + weight
19if alt < distances[neighbor]:
20distances[neighbor] = alt
21heapq.heappush(pq, (alt, neighbor))
22
23return distances
24
25# Example usage
26graph = defaultdict(list)
27edges = [('A','B',4), ('A','D',2)]
28for u, v, w in edges:
29graph[u].append((v, w))
30graph[v].append((u, w))
31
32result = dijkstra(graph, 'A')
33print("Shortest distances:", result)

Explanation

1. Imports & Initialization (lines 1-9): heapq provides binary min-heap operations (O(log V)). defaultdict(list) creates graph as adjacency list: {node: [(neighbor1, weight1), (neighbor2, weight2), ...]}. distances initialized as float('inf'), then start=0. Priority queue stores (distance, node) tuples.

2. Min-Heap Property (line 12): heapq.heappop(pq) extracts tuple with smallest first element (distance) in O(log V). Much faster than C's linear O(V) search. Heap automatically maintains order by repeatedly moving smaller elements toward root.

3. Visited Tracking (lines 13-15): Prevents processing same node twice. After popping (cost, node), check if node already visited. If yes, skip (continue) because we already processed it with smaller cost. Otherwise mark visited and process neighbors.

4. Edge Relaxation (lines 17-21): For each neighbor of current node: calculate alt = distances[current] + edge_weight. If alt < distances[neighbor], update distance and push (alt, neighbor) to heap. Multiple entries for same node may exist in heap; visited set ensures we only process each node once (the first time popped = minimum distance).

5. Time Complexity O((V+E) log V): Process each node once (V iterations) and each edge once (E pushes to heap). Each heap operation (push/pop) is O(log V). Total: V×O(log V) + E×O(log V) = O((V+E) log V). Superior to C's O(V²) for sparse graphs (E << V²). Graph representation with adjacency list enables efficient neighbor iteration.