Graph Algorithms Shortest Paths and Network Search Cheat Sheet

Updated 2026-05-19

🧠Study flashcards on this topic34 cards · spaced repetition→

Graph algorithms form the backbone of countless real-world systems — from GPS navigation and social networks to compiler design and circuit layout. This cheat sheet covers the full spectrum: graph representations, traversals, shortest-path algorithms (single-source and all-pairs), minimum spanning trees, union-find, topological ordering, cycle detection, strongly connected components, and advanced heuristic search. Entries are ordered from foundational to specialized, and within each table from most-used to most-obscure.

What This Cheat Sheet Covers

This topic spans 12 focused tables and 48 indexed concepts, 34 flashcards. Below is a complete table-by-table outline of this topic, spanning foundational concepts through advanced details.

Table 1: Graph RepresentationsTable 2: Core Graph TraversalTable 3: Single-Source Shortest PathsTable 4: All-Pairs Shortest PathsTable 5: Minimum Spanning TreesTable 6: Union-Find (Disjoint Set Union)Table 7: Topological OrderingTable 8: Cycle DetectionTable 9: Strongly Connected ComponentsTable 10: Structural Graph AnalysisTable 11: Heuristic and Advanced SearchTable 12: Algorithm Complexity Quick Reference

Quick IndexSubscribe to unlock

A jump-to index of every table row in this cheat sheet.

Mind MapSubscribe to unlock

An interactive map of every table and concept in this topic.

Table 1: Graph Representations

Before choosing an algorithm, the right data structure determines time and space efficiency. Adjacency lists are the default for sparse graphs; matrices suit dense graphs or when O(1) edge lookup is needed; edge lists are the input format for many sorting-based algorithms like Kruskal's.

Representation	Example	Description
Adjacency List	`graph = [[] for _ in range(V))` `graph[u].append((v, w))`	• Array of lists where `graph[u]` stores `(neighbor, weight)` pairs. Space $O(V+E)$ — optimal for sparse graphs • Standard choice for BFS, DFS, Dijkstra, and most traversal algorithms
Adjacency Matrix	`dist = [[INF]*V for _ in range(V)]` `dist[u][v] = w`	• $V \times V$ matrix where `dist[u][v]` = edge weight or $\infty$. Space $O(V^2)$ — O(1) edge lookup • required for Floyd-Warshall • Wasteful for sparse graphs
Edge List	`edges = []` `edges.append((w, u, v))`	Flat list of `(weight, u, v)` tuples. Space $O(E)$ — natural input for Bellman-Ford and Kruskal's (sort by weight).
Implicit Graph	`def neighbors(node):` `return grid_neighbors(node)`	• Graph encoded as a function returning neighbors on demand • Used in grid pathfinding (A*, BFS on 2-D grids) where storing all edges explicitly is wasteful

Table 2: Core Graph Traversal

BFS and DFS are the two fundamental traversal primitives; every other graph algorithm builds on or resembles one of them. Choose BFS for shortest-hop paths on unweighted graphs; DFS for reachability, cycle detection, and tree-structured recursion.

Technique	Example	Description
Breadth-First Search (BFS)	`from collections import deque` `q = deque([src]); dist[src]=0` `while q:` `u=q.popleft()` `for v,_ in g[u]:` `if dist[v]==INF:` `dist[v]=dist[u]+1; q.append(v)`	• Explores vertices layer by layer using a queue. Guarantees shortest path in hop count on unweighted graphs • Time $O(V+E)$, space $O(V)$.

The rest of this section is part of the full cheat sheet

Table 3: Single-Source Shortest Paths

When you need the shortest path from one source to all reachable vertices, the algorithm choice hinges on whether edges can be negative and whether the graph is a DAG.

Technique	Example	Description
Dijkstra's Algorithm	`import heapq` `pq = [(0, src)]; dist[src]=0` `while pq:` `d,u = heapq.heappop(pq)` `if d>dist[u]: continue` `for v,w in g[u]:` `if dist[u]+w < dist[v]:` `dist[v]=dist[u]+w` `heapq.heappush(pq,(dist[v],v))`	Greedy SSSP using a min-heap. Time $O((V+E)\log V)$ with binary heap. Requires non-negative edge weights. The `if d>dist[u]: continue` lazy-deletion guard is essential for correctness with the Python heapq.

The rest of this section is part of the full cheat sheet

Table 4: All-Pairs Shortest Paths

All-pairs algorithms compute shortest paths between every pair of vertices. They are used when you need a full distance matrix — for example, routing tables, network analysis, and transitive closure.

Technique	Example	Description
Floyd-Warshall	`for k in range(V):` `for i in range(V):` `for j in range(V):` `dist[i][j]=min(dist[i][j],` `dist[i][k]+dist[k][j])`	Dynamic programming over intermediate vertices $k$. Time $O(V^3)$, space $O(V^2)$. Handles negative edges (not negative cycles). Negative-cycle detection: if `dist[i][i] < 0` after the algorithm, a negative cycle exists.

The rest of this section is part of the full cheat sheet

Table 1: Graph Representations

Representation	Example	Description
Adjacency List	`graph = [[] for _ in range(V))` `graph[u].append((v, w))`	• Array of lists where `graph[u]` stores `(neighbor, weight)` pairs. Space $O(V+E)$ — optimal for sparse graphs • Standard choice for BFS, DFS, Dijkstra, and most traversal algorithms
Adjacency Matrix	`dist = [[INF]*V for _ in range(V)]` `dist[u][v] = w`	• $V \times V$ matrix where `dist[u][v]` = edge weight or $\infty$. Space $O(V^2)$ — O(1) edge lookup • required for Floyd-Warshall • Wasteful for sparse graphs
Edge List	`edges = []` `edges.append((w, u, v))`	Flat list of `(weight, u, v)` tuples. Space $O(E)$ — natural input for Bellman-Ford and Kruskal's (sort by weight).
Implicit Graph	`def neighbors(node):` `return grid_neighbors(node)`	• Graph encoded as a function returning neighbors on demand • Used in grid pathfinding (A*, BFS on 2-D grids) where storing all edges explicitly is wasteful

Table 2: Core Graph Traversal

Technique	Example	Description
Breadth-First Search (BFS)	`from collections import deque` `q = deque([src]); dist[src]=0` `while q:` `u=q.popleft()` `for v,_ in g[u]:` `if dist[v]==INF:` `dist[v]=dist[u]+1; q.append(v)`	• Explores vertices layer by layer using a queue. Guarantees shortest path in hop count on unweighted graphs • Time $O(V+E)$, space $O(V)$.

Table 3: Single-Source Shortest Paths

When you need the shortest path from one source to all reachable vertices, the algorithm choice hinges on whether edges can be negative and whether the graph is a DAG.

Technique	Example	Description
Dijkstra's Algorithm	`import heapq` `pq = [(0, src)]; dist[src]=0` `while pq:` `d,u = heapq.heappop(pq)` `if d>dist[u]: continue` `for v,w in g[u]:` `if dist[u]+w < dist[v]:` `dist[v]=dist[u]+w` `heapq.heappush(pq,(dist[v],v))`	Greedy SSSP using a min-heap. Time $O((V+E)\log V)$ with binary heap. Requires non-negative edge weights. The `if d>dist[u]: continue` lazy-deletion guard is essential for correctness with the Python heapq.

Table 4: All-Pairs Shortest Paths

Technique	Example	Description
Floyd-Warshall	`for k in range(V):` `for i in range(V):` `for j in range(V):` `dist[i][j]=min(dist[i][j],` `dist[i][k]+dist[k][j])`	Dynamic programming over intermediate vertices $k$. Time $O(V^3)$, space $O(V^2)$. Handles negative edges (not negative cycles). Negative-cycle detection: if `dist[i][i] < 0` after the algorithm, a negative cycle exists.

Graph Algorithms – Shortest Paths and Network Search Cheat Sheet

Table 1: Graph Representations

Table 2: Core Graph Traversal

Table 3: Single-Source Shortest Paths

Table 4: All-Pairs Shortest Paths

Graph Algorithms – Shortest Paths and Network Search Cheat Sheet

Table 1: Graph Representations

Table 2: Core Graph Traversal

Table 3: Single-Source Shortest Paths

Table 4: All-Pairs Shortest Paths