SimuVedaAlgorithms Lab Open in the lab

Graphs / Advanced

Dijkstra's Shortest Path Visualizer

Always finalize the closest unfinished node next, then try to improve the distance to each of its neighbors.

Start the Dijkstra's Shortest Path simulation → Step forward and back, change the input, follow the code line by line in Java, Python, C++, C or JavaScript. Free, no sign-up.

Time and space complexity

Best timeO((V+E) log V)
Average timeO((V+E) log V)
Worst timeO((V+E) log V)
Extra spaceO(V)

Worked example, step by step

The same steps the simulator shows, on a small input.

  1. Every distance starts at ∞, except A which is 0.
  2. Take A, the closest at 0. Its distance is now final.
  3. A to B: 0 + 4 = 4, better than ∞. Update B.
  4. A to C: 0 + 2 = 2, better than ∞. Update C.
  5. Take C, the closest at 2. Its distance is now final.
  6. C to B: 2 + 1 = 3, better than 4. Update B.
  7. C to D: 2 + 8 = 10, better than ∞. Update D.
  8. C to E: 2 + 10 = 12, better than ∞. Update E.
  9. Take B, the closest at 3. Its distance is now final.
  10. B to D: 3 + 5 = 8, better than 10. Update D.
  11. B:4 is outdated, the best is already 3. Skip it.
  12. Take D, the closest at 8. Its distance is now final.
  13. D to E: 8 + 2 = 10, better than 12. Update E.
  14. D to F: 8 + 6 = 14, better than ∞. Update F.
  15. D:10 is outdated, the best is already 8. Skip it.
  16. Take E, the closest at 10. Its distance is now final.
  17. E to F: 10 + 3 = 13, better than 14. Update F.
  18. E:12 is outdated, the best is already 10. Skip it.
  19. Take F, the closest at 13. Its distance is now final.
  20. F:14 is outdated, the best is already 13. Skip it.
  21. Done. Shortest distances from A: A 0, B 3, C 2, D 8, E 10, F 13.

Try it with your own input →

Dijkstra's shortest path in Java, Python, C++, C and JavaScript

int[] dijkstra(int src) {
  int[] dist = new int[n]; fill(dist, INF);
  dist[src] = 0;
  PriorityQueue<int[]> pq = new PriorityQueue<>((x, y) -> x[1] - y[1]);
  pq.add(new int[]{src, 0});
  while (!pq.isEmpty()) {
    int[] cur = pq.poll(); int u = cur[0];
    if (cur[1] > dist[u]) continue;
    for (int[] e : adj[u]) {
      int v = e[0], w = e[1];
      if (dist[u] + w < dist[v]) {
        dist[v] = dist[u] + w;
        pq.add(new int[]{v, dist[v]});
      }
    }
  }
  return dist;
}
import heapq

def dijkstra(adj, src):
    dist = [float('inf')] * len(adj)
    dist[src] = 0
    pq = [(0, src)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        for v, w in adj[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(pq, (dist[v], v))
    return dist
vector<int> dijkstra(const vector<vector<pair<int,int>>>& adj, int src) {
  vector<int> dist(adj.size(), INT_MAX);
  dist[src] = 0;
  priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;  // (dist, node)
  pq.push({0, src});
  while (!pq.empty()) {
    auto [d, u] = pq.top(); pq.pop();
    if (d > dist[u]) continue;
    for (auto [v, w] : adj[u]) {
      if (dist[u] + w < dist[v]) {
        dist[v] = dist[u] + w;
        pq.push({dist[v], v});
      }
    }
  }
  return dist;
}
#include <limits.h>
#define MAXN 100
int n, w[MAXN][MAXN];   /* w[u][v] = edge weight, 0 = no edge */

/* Simple O(n^2) version: pick the closest unfinished node each round instead of a heap. */
void dijkstra(int src, int dist[]) {
  int done[MAXN] = {0};
  for (int i = 0; i < n; i++) dist[i] = INT_MAX;
  dist[src] = 0;
  for (int round = 0; round < n; round++) {
    int u = -1;
    for (int i = 0; i < n; i++)
      if (!done[i] && (u < 0 || dist[i] < dist[u])) u = i;
    if (dist[u] == INT_MAX) break;
    done[u] = 1;
    for (int v = 0; v < n; v++) {
      if (w[u][v] && dist[u] + w[u][v] < dist[v]) {
        dist[v] = dist[u] + w[u][v];
      }
    }
  }
}
// adj[u] = [[v, w], ...]. A sorted array stands in for a priority queue to keep it short.
function dijkstra(adj, src) {
  const dist = new Array(adj.length).fill(Infinity);
  dist[src] = 0;
  const pq = [[src, 0]];
  while (pq.length > 0) {
    pq.sort((x, y) => x[1] - y[1]);
    const [u, d] = pq.shift();
    if (d > dist[u]) continue;
    for (const [v, w] of adj[u]) {
      if (dist[u] + w < dist[v]) {
        dist[v] = dist[u] + w;
        pq.push([v, dist[v]]);
      }
    }
  }
  return dist;
}

In an interview

It breaks with negative edge weights. Use Bellman-Ford there. The "skip outdated entry" check is a common bug in interviews.

More graphs