Dijkstra's Shortest Path — Animated Distance Relaxation

The idea

Repeatedly pick the unvisited node with smallest tentative distance. Relax its edges. Finalize it.

The idea

Repeatedly pick the unvisited node with smallest tentative distance. Relax its edges. Finalize it.

Priority queue template

PriorityQueue pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
int[] dist = new int[n]; Arrays.fill(dist, INF);
dist[start] = 0; pq.offer(new int[]{start, 0});
while (!pq.isEmpty()) {
  int[] cur = pq.poll();
  int u = cur[0], d = cur[1];
  if (d > dist[u]) continue;
  for (int[] edge : graph[u]) {
    int v = edge[0], w = edge[1];
    if (dist[u] + w < dist[v]) {
      dist[v] = dist[u] + w;
      pq.offer(new int[]{v, dist[v]});
    }
  }
}

Why non-negative weights

Dijkstra assumes distance only grows. Negative weights can decrease distance to already-finalized node. Use Bellman-Ford instead.

Complexity

O((V + E) log V) with binary heap. O(E + V log V) with Fibonacci heap.