Your free access ends in 7 days — and you haven’t tried it yet. Watch one algorithm run, start to finish. It takes about two minutes.

Try one problem
0
Concept

Shortest Path Algorithms

BFS vs Dijkstra vs Bellman-Ford
step 1 / 14
weighted directed graph
52113
A
B
C
D
Which shortest-path algorithm to pick
▸
1// choose by the edge weights:
2unweighted          -> BFS          (fewest edges)
3weights all >= 0    -> Dijkstra     (greedy, heap)
4any negative weight -> Bellman-Ford (relax all, V-1x)
5 
6Dijkstra: dist[src]=0; pop nearest; finalize;
7          relax u->v: if d+w < dist[v]: update
8 
9Bellman-Ford: relax EVERY edge, V-1 times;
10          one more pass relaxes => negative cycle
state
  • sourceA
  • questionwhich algorithm?

line 1"Shortest path" has three classic tools, and choosing the right one is mostly about the EDGE WEIGHTS. The decision: are the edges unweighted? Use BFS. Weighted but all non-negative? Use Dijkstra. Any negative weights? Use Bellman-Ford. Pick the cheapest tool the weights allow — using a heavier one is correct but wasteful.