The GPS Problem

[!NOTE] This module explores the core principles of Shortest Path algorithms, deriving solutions from first principles and hardware constraints to build world-class, production-ready expertise.

1. Concept Definition

Problem: Find the shortest path from a Start Node to all other nodes in a weighted graph.

Algorithms:

1. Dijkstra: Greedy. Always pick the closest unvisited node. Works on non-negative weights. O((V+E) log V).
2. Bellman-Ford: Dynamic Programming. Relaxes all edges V-1 times. Works with negative weights. O(VE).

---

2. Interactive Analysis: Dijkstra

1. Init: Set distance to Start = 0, others = Infinity.
2. PQ: Add (0, Start) to Min-Heap.
3. Loop: Pop min u. For neighbor v with weight w:
   • If dist[u] + w < dist[v], update dist[v] and add to PQ.

Ready.

Distances: [0, ∞, ∞, ∞, ∞]

---

3. Implementation (Dijkstra)

Java

Go

public int[] dijkstra(int n, int[][] edges, int start) {
    List<List<int[]>> adj = new ArrayList<>();
    for(int i=0; i<n; i++) adj.add(new ArrayList<>());
    for(int[] e : edges) adj.get(e[0]).add(new int[]{e[1], e[2]}); // u -> {v, w}

    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[start] = 0;

    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]); // {node, dist}
    pq.offer(new int[]{start, 0});

    while(!pq.isEmpty()) {
        int[] curr = pq.poll();
        int u = curr[0];
        int d = curr[1];

        if(d > dist[u]) continue; // Stale

        for(int[] edge : adj.get(u)) {
            int v = edge[0];
            int w = edge[1];
            if(dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.offer(new int[]{v, dist[v]});
            }
        }
    }
    return dist;
}

type Item struct {
    node, dist int
}
// PriorityQueue boiler-plate omitted for brevity (using container/heap)

func Dijkstra(n int, edges [][]int, start int) []int {
    adj := make([][][2]int, n)
    for _, e := range edges {
        adj[e[0]] = append(adj[e[0]], [2]int{e[1], e[2]})
    }

    dist := make([]int, n)
    for i := range dist { dist[i] = 1e9 }
    dist[start] = 0

    h := &MinHeap{ {start, 0} }
    heap.Init(h)

    for h.Len() > 0 {
        curr := heap.Pop(h).(Item)
        u := curr.node
        if curr.dist > dist[u] { continue }

        for _, edge := range adj[u] {
            v, w := edge[0], edge[1]
            if dist[u] + w < dist[v] {
                dist[v] = dist[u] + w
                heap.Push(h, Item{v, dist[v]})
            }
        }
    }
    return dist;
}

---

4. Complexity Analysis

Strategy	Time	Space	Notes
Dijkstra	O(E log V)	O(V + E)	Standard for weighted, non-negative.
Bellman-Ford	O(VE)	O(V)	Handles negative weights.