Finding the Shortest Path
How does Google Maps find the fastest route? Dijkstra’s Algorithm finds the shortest path from a start node to all other nodes in a weighted graph.
1. The Logic (Greedy + BFS)
It’s like BFS, but instead of a standard Queue, we use a Priority Queue.
- Explore: Always pick the node with the smallest distance found so far.
- Relax: If going through current node
Uto neighborVis shorter than the known distance toV, updateVand push to PQ.
2. Interactive: Dijkstra Step-by-Step
Find the shortest path from Node A.
PQ: [(A, 0)]
Dist: {A:0, B:inf, C:inf, D:inf}
3. Implementation
Java
Go
```java
public int networkDelayTime(int[][] times, int n, int k) {
Map<Integer, List<int[]>> graph = new HashMap<>();
for (int[] t : times) graph.computeIfAbsent(t[0], x -> new ArrayList<>()).add(new int[]{t[1], t[2]});
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]); // Min Heap (Node, Dist)
pq.offer(new int[]{k, 0});
Map<Integer, Integer> dist = new HashMap<>();
while (!pq.isEmpty()) {
int[] curr = pq.poll();
int u = curr[0], d = curr[1];
if (dist.containsKey(u)) continue;
dist.put(u, d);
if (graph.containsKey(u)) {
for (int[] edge : graph.get(u)) {
int v = edge[0], w = edge[1];
if (!dist.containsKey(v)) {
pq.offer(new int[]{v, d + w});
}
}
}
}
return dist.size() == n ? Collections.max(dist.values()) : -1;
}
```
```go
import "container/heap"
type Node struct { id, dist int }
type MinHeap []Node
func (h MinHeap) Len() int { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i].dist < h[j].dist }
func (h MinHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *MinHeap) Push(x interface{}) { *h = append(*h, x.(Node)) }
func (h *MinHeap) Pop() interface{} {
old := *h; n := len(old); x := old[n-1]; *h = old[0 : n-1]; return x
}
func networkDelayTime(times [][]int, n int, k int) int {
graph := make(map[int][][]int)
for _, t := range times {
graph[t[0]] = append(graph[t[0]], []int{t[1], t[2]})
}
pq := &MinHeap{Node{k, 0}}
heap.Init(pq)
dist := make(map[int]int)
for pq.Len() > 0 {
curr := heap.Pop(pq).(Node)
u, d := curr.id, curr.dist
if _, exists := dist[u]; exists { continue }
dist[u] = d
for _, edge := range graph[u] {
v, w := edge[0], edge[1]
if _, exists := dist[v]; !exists {
heap.Push(pq, Node{v, d + w})
}
}
}
if len(dist) != n { return -1 }
maxDist := 0
for _, d := range dist {
if d > maxDist { maxDist = d }
}
return maxDist
}
```