22. Dijkstra's Algorithm (Shortest Path)

🧸 ELI5: You're using GPS to find the fastest way to grandma's house, and some roads are slower than others (traffic, distance). Dijkstra's algorithm always explores the closest unvisited place first (using a heap/priority queue, like #19!), gradually building the shortest-distance map to everywhere from your starting point.

🌍 Real life: GPS/Google Maps shortest route calculation. Network routers finding the fastest path for your internet data to travel. Flight-booking sites finding the cheapest connecting flights.

📝 Pseudocode:

function dijkstra(graph, start):
    distances = { all nodes: infinity }
    distances[start] = 0
    priorityQueue = [(0, start)]

    while priorityQueue is not empty:
        (dist, current) = extractMin(priorityQueue)
        for (neighbor, weight) in graph[current]:
            newDist = dist + weight
            if newDist < distances[neighbor]:
                distances[neighbor] = newDist
                priorityQueue.add((newDist, neighbor))
    return distances

🐹 Go:

package main

import (
	"container/heap"
	"fmt"
	"math"
)

type Edge struct {
	to     string
	weight int
}

type Item struct {
	node string
	dist int
}

type PriorityQueue []Item

func (pq PriorityQueue) Len() int            { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool  { return pq[i].dist < pq[j].dist }
func (pq PriorityQueue) Swap(i, j int)       { pq[i], pq[j] = pq[j], pq[i] }
func (pq *PriorityQueue) Push(x interface{}) { *pq = append(*pq, x.(Item)) }
func (pq *PriorityQueue) Pop() interface{} {
	old := *pq
	n := len(old)
	item := old[n-1]
	*pq = old[:n-1]
	return item
}

func dijkstra(graph map[string][]Edge, start string) map[string]int {
	distances := make(map[string]int)
	for node := range graph {
		distances[node] = math.MaxInt32
	}
	distances[start] = 0

	pq := &PriorityQueue{{node: start, dist: 0}}
	heap.Init(pq)

	for pq.Len() > 0 {
		current := heap.Pop(pq).(Item)
		for _, edge := range graph[current.node] {
			newDist := current.dist + edge.weight
			if newDist < distances[edge.to] {
				distances[edge.to] = newDist
				heap.Push(pq, Item{node: edge.to, dist: newDist})
			}
		}
	}
	return distances
}

func main() {
	roadMap := map[string][]Edge{
		"Home":   {{"School", 5}, {"Park", 2}},
		"Park":   {{"School", 1}},
		"School": {},
	}
	fmt.Println(dijkstra(roadMap, "Home"))
	// Home:0, Park:2, School:3 (Home->Park->School is faster than Home->School directly!)
}

🇨 C — this version picks the closest unvisited place with a plain O(V) scan each round instead of #19's heap, trading O((V+E) log V) for a simpler O(V²); wiring the heap from #19 into this loop instead of the scan is exactly how you'd get the faster version:

#include <stdio.h>
#include <limits.h>
#include <string.h>

#define MAX_NODES 8

typedef struct {
    char names[MAX_NODES][32];
    int  weight[MAX_NODES][MAX_NODES]; // 0 = no direct road
    int  num_nodes;
} RoadMap;

int roadmap_add_node(RoadMap *g, const char *name) {
    strncpy(g->names[g->num_nodes], name, 31);
    return g->num_nodes++;
}

void roadmap_add_road(RoadMap *g, int a, int b, int weight) {
    g->weight[a][b] = weight;   // directed; call twice for a two-way road
}

void dijkstra(RoadMap *g, int start, int *dist) {
    int visited[MAX_NODES] = {0};
    for (int i = 0; i < g->num_nodes; i++) dist[i] = INT_MAX;
    dist[start] = 0;

    for (int iter = 0; iter < g->num_nodes; iter++) {
        int current = -1;
        for (int i = 0; i < g->num_nodes; i++) {      // pick the closest unvisited place —
            if (!visited[i] && (current == -1 || dist[i] < dist[current])) current = i;
        }
        if (current == -1 || dist[current] == INT_MAX) break;
        visited[current] = 1;

        for (int next = 0; next < g->num_nodes; next++) {
            if (g->weight[current][next] > 0 && dist[current] + g->weight[current][next] < dist[next]) {
                dist[next] = dist[current] + g->weight[current][next];
            }
        }
    }
}

int main(void) {
    RoadMap roadMap = {0};
    int home = roadmap_add_node(&roadMap, "Home");
    int park = roadmap_add_node(&roadMap, "Park");
    int school = roadmap_add_node(&roadMap, "School");

    roadmap_add_road(&roadMap, home, school, 5);
    roadmap_add_road(&roadMap, home, park, 2);
    roadmap_add_road(&roadMap, park, school, 1);

    int dist[MAX_NODES];
    dijkstra(&roadMap, home, dist);

    for (int i = 0; i < roadMap.num_nodes; i++) printf("%s:%d ", roadMap.names[i], dist[i]);
    printf("\n"); // Home:0 Park:2 School:3 — Home->Park->School beats Home->School directly
    return 0;
}

⏱️ Complexity: O((V + E) log V) using a heap — fast enough for GPS to recalculate routes on the fly.