Graph Algorithms

Learning Objectives

By the end of this page, you should be able to:

• Define a graph and distinguish directed, undirected, weighted, cyclic, and connected graphs.
• Trace BFS and DFS traversals on a small graph by hand and explain when each is preferred.
• Explain how Dijkstra's algorithm finds shortest paths and why it fails with negative edge weights.
• Explain what topological sorting produces and why it only works on directed acyclic graphs (DAGs).
• Compare Bellman-Ford and Floyd-Warshall to Dijkstra's algorithm in terms of use case and complexity.
• Choose the appropriate graph algorithm given a real-world scenario (e.g., routing, scheduling, social networks).

Quick Answer

A graph is a collection of vertices (nodes) connected by edges, used to model any system of interconnected objects — road networks, social connections, web links, or task dependencies. Graph algorithms matter because so many real problems reduce to "how are these things connected?" or "what's the cheapest way to get from A to B?" This page covers the two foundational traversal algorithms (BFS and DFS), the classic shortest-path algorithms (Dijkstra's, Bellman-Ford, Floyd-Warshall), and topological sorting for ordering dependent tasks — the toolkit behind GPS navigation, dependency resolution, and network analysis.

What Is a Graph?

Definition: A graph G = (V, E) consists of a set of vertices V and a set of edges E, where each edge connects a pair of vertices.

Explanation: Unlike a tree, a graph doesn't require a single root or a strict parent-child hierarchy — any vertex can connect to any number of others, including forming cycles. The type of graph (directed vs. undirected, weighted vs. unweighted) determines which algorithms apply and what "shortest" or "connected" even means.

Example: Vertices {A, B, C} with edges {(A,B), (B,C)} form a simple path graph — three cities connected by two roads.

Real-World Example: A city's road network is a graph — intersections are vertices, roads are edges, and travel times or distances are edge weights.

Why It Matters: Nearly any "relationship" data — friendships, flight routes, dependencies, web links — can be modeled as a graph, unlocking a whole family of well-studied algorithms for answering questions about that data.

Common Misunderstanding: Students often confuse "graph" (the data structure) with "chart" (a visual plot of data, like a bar graph). In computer science, a graph specifically means vertices and edges, regardless of whether it's plotted at all.

Types of Graphs

• Undirected Graphs: Edges have no direction — if A connects to B, B connects to A. Example: a social network where friendship is mutual.
• Directed Graphs (Digraphs): Edges point from one vertex to another in a specific order. Example: web pages linking to each other — A linking to B doesn't mean B links back.
• Weighted Graphs: Edges carry a numeric cost (distance, time, capacity). Example: a road network where each road has a different travel time.
• Cyclic vs. Acyclic: A cyclic graph contains at least one path that starts and ends at the same vertex; an acyclic graph has none (a tree is always acyclic).
• Connected vs. Disconnected: A connected graph has a path between every pair of vertices; a disconnected graph has at least one pair with no path between them.

Common Misunderstanding: Students assume "weighted" and "directed" are the same axis or mutually exclusive. They're independent properties — a graph can be directed and weighted (a one-way toll road), undirected and weighted (a two-way road with a distance), or any other combination.

Basic Graph Algorithms

Breadth-First Search (BFS)

BFS explores a graph level by level: visit the starting node, then all its direct neighbors, then all of their unvisited neighbors, and so on — using a queue to track what to visit next.

Algorithm:

1. Initialize a queue with the starting node and mark it visited.
2. While the queue isn't empty, dequeue a node, process it, and enqueue any unvisited neighbors (marking them visited immediately to avoid duplicates).

from collections import deque

def bfs(graph, start):
    visited = {start}
    queue = deque([start])
    order = []

    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return order

graph = {
    'A': ['B', 'C'], 'B': ['A', 'D', 'E'], 'C': ['A', 'F'],
    'D': ['B'], 'E': ['B', 'F'], 'F': ['C', 'E']
}
print(bfs(graph, 'A'))  # ['A', 'B', 'C', 'D', 'E', 'F']

Time Complexity: O(V + E) — every vertex and edge is examined once. Space Complexity: O(V) for the visited set and queue.

Real-World Example: Finding the shortest number of "hops" between two people on a social network (LinkedIn's "degrees of connection") uses BFS, since it explores connections level by level.

Why It Matters: BFS guarantees the shortest path in terms of number of edges for unweighted graphs — it will never find a longer path before a shorter one exists.

Common Misunderstanding: Students think BFS finds the shortest path in any graph. It only guarantees the shortest path by edge count, which only equals the true shortest path when the graph is unweighted (or all weights are equal).

Depth-First Search (DFS)

DFS explores as far as possible along one branch before backtracking, typically implemented recursively (using the call stack) or iteratively with an explicit stack.

Algorithm:

1. Visit the starting node and mark it visited.
2. Recursively visit each unvisited neighbor, going as deep as possible before returning to try other branches.

def dfs(graph, start, visited=None, order=None):
    if visited is None:
        visited = set()
        order = []
    visited.add(start)
    order.append(start)

    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited, order)
    return order

print(dfs(graph, 'A'))  # ['A', 'B', 'D', 'E', 'F', 'C']

Time Complexity: O(V + E). Space Complexity: O(V) — for the visited set and recursion stack (worst case O(V) deep on a skewed graph).

Real-World Example: Solving a maze by committing to a path and backtracking only when you hit a dead end is exactly DFS.

Why It Matters: DFS is the basis for cycle detection, topological sorting, and finding connected components — many graph algorithms are DFS with extra bookkeeping added.

Common Misunderstanding: Students assume DFS and BFS always visit nodes in the same relative order, just "differently." They can produce entirely different visitation orders and different results for tasks like path-finding — DFS finding a path doesn't mean it finds the shortest one.

Dijkstra's Algorithm

Dijkstra's algorithm finds the shortest path from a source vertex to every other vertex in a weighted graph with non-negative edge weights. It uses a priority queue (min-heap) to always expand the currently-closest unvisited vertex next.

import heapq

def dijkstra(graph, start):
    distances = {vertex: float('inf') for vertex in graph}
    distances[start] = 0
    priority_queue = [(0, start)]

    while priority_queue:
        current_distance, current_vertex = heapq.heappop(priority_queue)
        if current_distance > distances[current_vertex]:
            continue  # stale entry, skip it
        for neighbor, weight in graph[current_vertex].items():
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))
    return distances

weighted_graph = {
    'A': {'B': 1, 'C': 4}, 'B': {'A': 1, 'D': 2, 'E': 5},
    'C': {'A': 4, 'F': 3}, 'D': {'B': 2},
    'E': {'B': 5, 'F': 1}, 'F': {'C': 3, 'E': 1}
}
print(dijkstra(weighted_graph, 'A'))
# {'A': 0, 'B': 1, 'C': 4, 'D': 3, 'E': 6, 'F': 7}

Time Complexity: O((V + E) log V) using a binary heap priority queue. Space Complexity: O(V) for distances and the priority queue.

Real-World Example: GPS navigation apps use Dijkstra's algorithm (or optimized variants like A*) to compute the fastest route between two points on a road network weighted by travel time.

Why It Matters: It's the standard efficient algorithm for shortest paths whenever edge weights represent real, non-negative costs — like distance, time, or price.

Common Misunderstanding: Students try to apply Dijkstra's algorithm to graphs with negative edge weights and get wrong answers with no warning. Dijkstra's greedy approach assumes that once a vertex's shortest distance is finalized, no future path could improve it — a negative edge can violate that assumption.

Topological Sorting

Topological sorting produces a linear ordering of vertices in a directed acyclic graph (DAG) such that for every directed edge u → v, u appears before v in the ordering. It only works on DAGs — a cycle would create a contradiction (something would need to come before itself).

def topological_sort(graph):
    visited = set()
    stack = []

    def dfs(node):
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                dfs(neighbor)
        stack.append(node)  # append after all descendants are processed

    for node in graph:
        if node not in visited:
            dfs(node)
    return stack[::-1]

dag = {'A': ['B', 'C'], 'B': ['D'], 'C': ['D'], 'D': []}
print(topological_sort(dag))  # ['A', 'C', 'B', 'D']

Time Complexity: O(V + E). Space Complexity: O(V) for the visited set and result stack.

Real-World Example: Build systems (like Make or npm) use topological sorting to determine the order to compile files or install packages when some depend on others.

Why It Matters: It's the standard way to resolve dependency ordering problems — course prerequisites, task scheduling, spreadsheet cell recalculation.

Common Misunderstanding: Students think topological sort produces a unique ordering. Multiple valid topological orderings can exist for the same DAG whenever two vertices have no dependency relationship between them (either order is valid).

Bellman-Ford Algorithm

Bellman-Ford computes shortest paths from a source to all vertices, handling negative edge weights (unlike Dijkstra's) by relaxing every edge V-1 times. A further pass can detect negative-weight cycles, which make "shortest path" undefined.

Time Complexity: O(V × E) — slower than Dijkstra's, but tolerant of negative weights. Space Complexity: O(V).

Why It Matters: It's essential when negative weights are meaningful, such as modeling currency arbitrage (where a "negative cost" edge represents a profitable trade) or network flow problems with penalties.

Floyd-Warshall Algorithm

Floyd-Warshall computes shortest paths between every pair of vertices in a weighted graph, using dynamic programming to progressively consider each vertex as a possible intermediate stop.

Time Complexity: O(V³) — practical only for smaller, dense graphs. Space Complexity: O(V²) for the distance matrix.

Why It Matters: When you need the shortest path between every pair of vertices (not just from one source), Floyd-Warshall's single O(V³) run beats running Dijkstra's V separate times, especially on dense graphs.

Real-World Applications

• Navigation apps: Dijkstra's algorithm (and A*, a heuristic-guided variant) power turn-by-turn shortest-route calculation.
• Social networks: BFS computes "degrees of separation"; graph connectivity algorithms detect communities and suggest friends.
• Build systems and package managers: Topological sorting orders compilation steps and dependency installation.
• Currency and financial arbitrage: Bellman-Ford detects negative-weight cycles that indicate profitable arbitrage loops.
• Network routing protocols: Distance-vector routing protocols use Bellman-Ford-like relaxation to propagate shortest paths across routers.

Key Terms

Term	Definition	Context/Related
Vertex (Node)	A fundamental unit of a graph representing an entity	Connected to others via edges
Edge	A connection between two vertices	Can be directed, undirected, or weighted
Adjacency List	A representation storing each vertex's list of neighbors	Space-efficient for sparse graphs, used in BFS/DFS examples
Directed Acyclic Graph (DAG)	A directed graph with no cycles	Required precondition for topological sorting
Relaxation	Updating a vertex's shortest known distance when a shorter path is found	Core step in Dijkstra's and Bellman-Ford
Negative-Weight Cycle	A cycle whose total edge weight sums to a negative number	Makes "shortest path" undefined; detected by Bellman-Ford
Priority Queue (Min-Heap)	A data structure that always returns the smallest element first	Used to efficiently pick the next closest vertex in Dijkstra's

Common Mistakes

Misconception 1: "BFS always finds the shortest path in a graph." Why it's wrong: BFS guarantees the shortest path in terms of number of edges, which only equals the shortest path when the graph is unweighted or all weights are equal. Correct explanation: For weighted graphs, use Dijkstra's algorithm (non-negative weights) or Bellman-Ford (if negative weights are possible) to find the true shortest path by total weight.

Misconception 2: "Dijkstra's algorithm works on any weighted graph." Why it's wrong: Dijkstra's greedy strategy finalizes a vertex's shortest distance as soon as it's dequeued, assuming no future edge could ever improve it — a negative edge can break that assumption and produce an incorrect result. Correct explanation: Only use Dijkstra's algorithm when all edge weights are non-negative; switch to Bellman-Ford if negative weights are possible.

Misconception 3: "Topological sort works on any directed graph." Why it's wrong: A cycle means some vertex would need to appear both before and after another vertex in the ordering, which is a logical contradiction. Correct explanation: Topological sorting is only defined for directed acyclic graphs (DAGs) — always check for cycles first (or let the algorithm's incomplete output reveal one).

Comparison and Connections

Concept A	Concept B	Key Difference
BFS	DFS	BFS explores level by level using a queue (finds shortest path by edge count); DFS explores one branch fully using a stack/recursion (finds a path, not necessarily shortest)
Dijkstra's Algorithm	Bellman-Ford Algorithm	Dijkstra's is faster (O((V+E) log V)) but fails on negative weights; Bellman-Ford is slower (O(V×E)) but handles negative weights and detects negative cycles
Dijkstra's Algorithm	Floyd-Warshall Algorithm	Dijkstra's finds shortest paths from one source; Floyd-Warshall finds shortest paths between all pairs in O(V³)
Directed Graph	Undirected Graph	Directed edges have a one-way relationship (A→B ≠ B→A); undirected edges are symmetric
Tree	Graph	A tree is a connected, acyclic graph with exactly one path between any two vertices; a general graph allows cycles and multiple paths

Practice Questions

Recall 1: What data structure does BFS use to track which node to visit next, and what does DFS typically use? Answer guidance: BFS uses a queue (FIFO); DFS uses a stack (LIFO), often implicitly via recursion's call stack.

Recall 2: What precondition must a graph satisfy for topological sorting to be valid? Answer guidance: The graph must be a directed acyclic graph (DAG) — directed, with no cycles.

Understanding 1: Explain why Dijkstra's algorithm fails to produce correct results on graphs with negative edge weights. Answer guidance: Dijkstra's algorithm greedily finalizes the shortest distance to a vertex as soon as it's popped from the priority queue, assuming any future path to it could only be longer. A negative edge encountered later could reduce the total distance below the already-finalized value, but the algorithm never revisits finalized vertices, so it produces an incorrect (too-high) distance.

Understanding 2: Why does BFS guarantee the shortest path in an unweighted graph, but not in a weighted one? Answer guidance: BFS explores vertices in order of increasing edge count from the source, so the first time it reaches a vertex is guaranteed to be via the fewest edges. In a weighted graph, a path with more edges can have a smaller total weight than a path with fewer edges, so "reached first" (fewest edges) no longer corresponds to "cheapest total cost."

Application 1: You're building a feature that recommends "people you may know" based on mutual connections within 2 degrees of separation. Which traversal algorithm fits, and why? Answer guidance: BFS — it naturally explores connections level by level, so stopping after 2 levels directly gives everyone within 2 degrees of separation, without needing to explore deeper branches first.

Application 2: A build system needs to determine the order to compile files, where some files depend on others being compiled first. Which algorithm fits, and why? Answer guidance: Topological sorting — the dependency graph is a DAG (assuming no circular dependencies), and topological sort produces a valid compile order where every file is compiled after its dependencies.

Analysis 1: A network engineer wants the shortest path between every pair of routers in a small network of 20 routers, some with negative-cost links representing subsidized routes. Evaluate whether Dijkstra's, Bellman-Ford, or Floyd-Warshall is most appropriate. Answer guidance: Floyd-Warshall is most appropriate — it computes all-pairs shortest paths in a single O(V³) run, which is very manageable for only 20 vertices, and it correctly handles negative edge weights (as long as there's no negative cycle), unlike Dijkstra's. Running Bellman-Ford V times would also work and handle negatives, but would be less direct than Floyd-Warshall's built-in all-pairs computation.

Analysis 2: Compare using DFS versus BFS to detect whether a graph is connected. Does the choice matter for correctness or only for performance? Answer guidance: Either DFS or BFS can correctly detect connectivity — run a single traversal from any vertex, and if it visits all vertices, the graph is connected. Both have the same O(V + E) time complexity, so the choice doesn't affect correctness or asymptotic performance; it mainly comes down to implementation preference (DFS's recursion can hit stack limits on very large graphs, where an iterative BFS might be safer).

FAQ

Q: Do I need to memorize the code for all these algorithms? A: Focus on understanding the pattern each solves (level-by-level exploration, greedy shortest-path expansion, dependency ordering) — once the reasoning is clear, the code becomes a natural expression of that logic rather than something to memorize by rote.

Q: What's the difference between a graph and a tree? A: A tree is a special case of a graph: connected, acyclic, and with exactly one path between any two vertices. A general graph can have cycles, multiple paths between vertices, or even be disconnected.

Q: Why does Dijkstra's algorithm use a priority queue instead of a regular queue? A: A regular queue (like in BFS) processes nodes in the order they were added, which only matches "closest first" when all edges have equal weight. A priority queue always pops the vertex with the smallest known distance, which is essential when edges have different weights.

Q: When would I ever need Floyd-Warshall instead of just running Dijkstra's multiple times? A: When you need all-pairs shortest paths on a small-to-medium, possibly negative-weighted graph, Floyd-Warshall's single O(V³) pass is simpler to implement correctly than running Bellman-Ford V times, though for large sparse graphs, running Dijkstra's V times is usually faster.

Q: How do I know if a directed graph has a cycle before trying to topologically sort it? A: Run DFS and track nodes currently in the recursion stack (not just visited overall) — if you ever reach a node that's already in the current recursion path, you've found a cycle referred to as a "back edge."

Quick Revision

• A graph is vertices + edges; can be directed/undirected, weighted/unweighted, cyclic/acyclic, connected/disconnected.
• BFS explores level by level using a queue — O(V + E), finds shortest path by edge count in unweighted graphs.
• DFS explores depth-first using a stack/recursion — O(V + E), basis for cycle detection and topological sort.
• Dijkstra's algorithm finds shortest paths from one source using a priority queue — O((V+E) log V), requires non-negative weights.
• Bellman-Ford handles negative weights and detects negative cycles — O(V × E), slower than Dijkstra's but more tolerant.
• Floyd-Warshall computes all-pairs shortest paths — O(V³), best for smaller dense graphs.
• Topological sort orders vertices of a DAG so dependencies come before dependents — undefined on graphs with cycles.
• BFS ≠ "always shortest path" — only true for unweighted graphs; use Dijkstra's/Bellman-Ford for weighted shortest paths.
• Negative edges break Dijkstra's greedy assumption; use Bellman-Ford when negative weights are possible.
• A tree is a connected, acyclic graph — a special, simpler case of the general graph.
• Adjacency lists are the typical representation for sparse graphs; adjacency matrices suit dense graphs needing O(1) edge lookup.
• Algorithm choice depends on: weighted vs. unweighted, negative weights present, single-source vs. all-pairs, and graph density.

Related Topics

Prerequisites:

• Trees and Graphs (basic graph terminology and representations)
• Stacks and Queues (needed to understand DFS and BFS implementations)
• Recursion (used heavily in DFS and topological sort)

Related Topics:

• Sorting and Searching Algorithms (searching a graph is a specialized search problem)
• Advanced Data Structures (priority queues/heaps power Dijkstra's algorithm)
• Dynamic Programming (Floyd-Warshall is a DP algorithm)

Next Topics:

• Advanced Data Structures (heaps, tries, and balanced trees used to implement efficient graph algorithms)
• Dynamic Programming (shared divide-and-conquer/optimal-substructure reasoning)
• Network flow algorithms (a natural extension of weighted graph traversal)