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 U to neighbor V is shorter than the known distance to V, update V and 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

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;
}