Log in
MODULE 10

Graph Algorithms

BFS, DFS, Dijkstra's shortest path, and Minimum Spanning Tree (Prim's / Kruskal's). Use weighted edges like A-B:4 for Dijkstra and MST.

Graph

Check Directed for Bellman-Ford (to allow negative weights) and Topological Sort (required).

Note: Dijkstra requires non-negative weights (use Bellman-Ford instead if you have negative edges). MST algorithms (Prim's/Kruskal's) and Floyd-Warshall's negative-cycle check assume undirected input unless "Directed graph" is checked. Topological Sort requires a directed acyclic graph.

Understanding Graph Algorithms

Once a graph is built, algorithms let us extract useful answers from it: the shortest route between two points, the minimum-cost way to connect every vertex, or the order in which dependent tasks must run. These algorithms are some of the most widely used in all of computer science, powering everything from GPS navigation to network routing protocols.

Key Definitions & Formulas

  • Breadth-First Search (BFS): explores a graph level by level, finding the shortest path in unweighted graphs.
  • Depth-First Search (DFS): explores as far as possible along each branch before backtracking.
  • Dijkstra's algorithm: finds shortest paths in weighted graphs with non-negative edge weights.
  • Minimum Spanning Tree (MST): the cheapest set of edges connecting all vertices without forming a cycle (Kruskal's and Prim's algorithms).
  • Topological sort: an ordering of vertices in a directed acyclic graph so every edge points forward.

Worked Example

Running BFS from vertex 1 in a graph with edges (1,2), (1,3), (2,4) visits vertices in the order 1, then 2 and 3 (both one step away), then 4 (two steps away) — guaranteeing the shortest unweighted path from 1 to 4 has length 2, found without ever having to check every possible path individually.

Where This Is Used

  • GPS and mapping software for shortest-route calculation.
  • Network design for laying cable or fiber at minimum cost (MST).
  • Build systems and task schedulers (topological sort for dependencies).
  • Web crawling and social network traversal (BFS/DFS).