Training Trains Internship
Student login
← Algorithm Design learning path
Algorithm Design · Module 6 of 10

Graph algorithms

Solve path, connectivity and spanning problems.

📖 Key ideas

  1. BFS: shortest path in unweighted graphs.
  2. Dijkstra: shortest paths with non-negative weights.
  3. Bellman-Ford handles negative weights and detects negative cycles.
  4. Floyd-Warshall: all-pairs shortest paths O(V³).
  5. MST: Kruskal (edges + union-find), Prim (grow from a vertex).
💡 Real-life example: Shortest path algorithms are Google Maps choosing the quickest route between places.
DijkstraSingle-source shortest paths, non-negative weights
Bellman-FordHandles negative weights
Floyd-WarshallAll-pairs shortest paths
MSTMinimum spanning tree