Summary of All Shortest Path Algorithms

Shortest Path (SP) AlgorithmsBFSA*Dijkstra’sBellman FordFloyd Warshall
Recommended graph sizeLargeLargeLarge/MediumMedium/SmallSmall
All-PairsOnly works on unweighted graphsNoOkBadYes
Can detect negative cycles?---
SP on graph with unweighted edges✓(Best)✓(Bad)✓(Bad)
SP on graph with weighted edgesMust expand graph✓(Best)✓(Bad)

Single Source Shortest Path (SSSP)

alg. BFS Shortest Path

  • Assumption: Graph doesn’t have weights
  • Idea: BFS, but every time you encounter a tense edge, relax it

alg. Dijkstra’s Shortest Path

alg. A-Star (A*) Shortest Path

alg. Bellman–Ford Shortest Path

  • Idea:
    • Repeat BFS edge relaxation for times. Get shortest path
    • Repeat BFS edge relaxation again, for times. But this time, if any cost values are updated, the node is part of a negative cycle. Mark cost to that node as .
    • See Bellman Ford Algorithm | Graph Theory - YouTube
    • Able to deal with negative edges/negative cycles
    • Often used in finance for identifying No-Arbitrage opportunities.
  • Complexity. Time:

All Pairs Shortest Path (APSP)

alg. Floyd-Warshall Shortest Path

  • Idea: Dynamically Programmed algorithm. from to , compare the two paths:
    1. using only vertices
    2. , but only using vertices
    3. Take the smaller of the two.
  • Complexity. Time: , Space by retaining most recent only

Tips and Tricks

  • If the problem demands you multiply edge weights instead of summing them, use of weights instead to transform it back into a problem with summation of edge weights. (See Example)