Log in
MODULE 10

Graph Algorithms Calculator: BFS, DFS & Dijkstra

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.

What is Graph Algorithms?

Once a graph exists, algorithms extract useful answers from it: shortest paths (BFS, Dijkstra), minimum-cost connections (MST), and traversal orders — the same algorithms behind GPS routing and network design.

How Does This Calculator Work?

Build a graph the same way as the Graph Theory module, then choose an algorithm — BFS, DFS, Dijkstra, Prim's, or Kruskal's — and pick a start vertex. The tool traces every step of the algorithm, not just the final result.

Common Formulas & Rules

  • 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.

Study guide: Graph Algorithms

Written for students learning this topic for the first time. Last updated October 2026.

Overview

Graph algorithms each answer a specific question: what can I reach, what is the shortest route, in what order should tasks run. Breadth-first and depth-first search explore a graph; Dijkstra, Bellman–Ford and Floyd–Warshall find shortest paths; topological sort orders a dependency graph.

Choosing the right one depends on three things: are edges weighted, can weights be negative, and is the graph directed and acyclic?

Key ideas explained

BFS and DFS

BFS explores in layers using a queue and finds the fewest-edge path in an unweighted graph. DFS dives as deep as possible using a stack or recursion and is the basis for cycle detection, connected components and topological sort. Both run in O(V + E) on an adjacency list.

Dijkstra's algorithm

Repeatedly settle the unsettled vertex with the smallest known distance and relax its outgoing edges. It requires non-negative weights and runs in O((V + E) log V) with a heap. A negative edge breaks it because a vertex already settled could later be improved.

Bellman–Ford and Floyd–Warshall

Bellman–Ford relaxes every edge V − 1 times, tolerates negative weights, and detects a negative cycle if a further pass still improves something; it runs in O(VE). Floyd–Warshall computes all-pairs shortest paths by dynamic programming over allowed intermediate vertices in O(V³).

Topological sort

A topological order lists vertices so every edge points forward. It exists exactly when the directed graph has no cycle, and it can be built with DFS finishing times or Kahn's algorithm, which repeatedly removes vertices with no incoming edges.

Worked examples

Dijkstra by hand

Problem. Undirected graph: A–B 4, A–C 2, C–B 1, B–D 5, C–D 8, D–E 3. Shortest distances from A?

  1. Settle A (0): B = 4, C = 2.
  2. Settle C (2): B improves to 3, D = 10.
  3. Settle B (3): D improves to 8.
  4. Settle D (8): E = 11.

Answer. A = 0, C = 2, B = 3, D = 8, E = 11. The route to E is A–C–B–D–E.

Topological orders

Problem. Tasks with dependencies A→B, A→C, B→D, C→D. List the valid orders.

  1. A has no prerequisites, so it comes first; D depends on both B and C, so it comes last.
  2. B and C can appear in either order.

Answer. A, B, C, D and A, C, B, D. Adding an edge D→A would create a cycle and no order would exist.

Enter these same values in the calculator above and compare each step with the working shown here.

Common mistakes to avoid

  • Running Dijkstra on a graph with negative edge weights.
  • Using BFS for weighted shortest paths. It only minimises the number of edges.
  • Forgetting to mark vertices as visited, which causes infinite loops on cycles.
  • Expecting a unique traversal order. BFS and DFS orders depend on how neighbours are listed.
  • Confusing a single negative edge (fine for Bellman–Ford) with a negative cycle (no shortest path exists).

Where this shows up in computer science

  • Link-state routing (OSPF) uses Dijkstra, and distance-vector routing (RIP) is built on Bellman–Ford.
  • Build tools and course-prerequisite planners use topological sort.
  • BFS measures degrees of separation in social networks; Floyd–Warshall suits all-pairs queries on small networks.

Test yourself

Try each question before opening the answer.

What is the time complexity of BFS on an adjacency-list graph?

O(V + E).

Why can Dijkstra fail when an edge is negative?

It assumes a settled vertex can never be improved, but a later negative edge can shorten a path to it.

Does a directed graph containing a cycle have a topological order?

No.

Frequently asked questions

What's the difference between BFS and DFS?

BFS (Breadth-First Search) explores level by level, finding the shortest path in unweighted graphs. DFS (Depth-First Search) explores as deep as possible along one branch before backtracking, useful for detecting cycles and exploring structure.

When does Dijkstra's algorithm not work?

Dijkstra's algorithm requires all edge weights to be non-negative. If a graph has negative edge weights, use the Bellman-Ford algorithm instead.

What's the difference between Prim's and Kruskal's algorithm?

Both find a Minimum Spanning Tree. Prim's grows one connected tree by always adding the cheapest edge from the current tree. Kruskal's instead considers all edges globally, sorted by weight, adding any edge that doesn't create a cycle.