# Graph Theory: The Math of What's Connected to What > A graph is a map of relationships: who is friends with whom, which files import which other files, how data flows through a network. This guide teaches you to think in connections, find the shortest path, and see the graph theory running your package manager, your social feed, and the internet itself. --- # Graph Theory: The Math of What's Connected to What If you have ever used a package manager, followed a social network, or traced a network request through a series of services, you have used graph theory. The difference is that the computer knew it was using graph theory, and you did not. This guide fixes that. We are not going to prove theorems about planar embeddings. We are going to start from something you already understand - a group chat where everyone is connected to everyone else - and build up to the algorithms that find the shortest route, detect cycles, and rank the most important nodes. By the end, a graph will look like a map you already know how to read. This is the eighth guide in the Mathematics track. It assumes the set idea from [Sets, Relations, and Functions](/guides/sets-relations-and-functions) and the counting basics from [Counting & Combinatorics](/guides/counting-and-combinatorics). If you can follow a family tree or a subway map, you are ready. ## How to read this - **Here for the "what problem does this solve" answer?** Start with [Phase 1](01-nodes-edges-and-the-graphs-you-already-use.md) - graphs as real relationships. - **Want the full toolkit?** Read in order - paths and trees build on the basic graph, and the applications build on both. ## The phases 1. **[Nodes, Edges, and the Graphs You Already Use](01-nodes-edges-and-the-graphs-you-already-use.md)** - what a graph is, directed vs undirected, weighted edges, and the code that represents a dependency tree. 2. **[Finding the Shortest Path and Detecting Cycles](02-finding-the-shortest-path-and-detecting-cycles.md)** - BFS and DFS, shortest path with Dijkstra, minimum spanning tree, and why circular dependencies are a graph problem. 3. **[Graphs That Run the World](03-graphs-that-run-the-world.md)** - PageRank again (now with the graph lens), network routing, recommendation engines, and the builder's guide to seeing graphs everywhere. > This builds on [Sets, Relations, and Functions](/guides/sets-relations-and-functions) (relations are graphs) and [Counting & Combinatorics](/guides/counting-and-combinatorics) (dimensions as choices). It is the discrete structure behind most modern systems. --- # Nodes, Edges, and the Graphs You Already Use ## The group chat that taught me everything Picture a group chat with four people: Alice, Bob, Cara, and Dave. Alice can message everyone. Bob can message Alice and Cara. Cara can message everyone. Dave can only message Alice. If you draw a dot for each person and a line between any two people who can message each other, you have drawn a graph. The dots are **nodes** (or vertices). The lines are **edges**. That is all a graph is. Nodes and edges. Everything else in graph theory is asking questions about that picture. ## What a graph is A **graph** is a set of nodes plus a set of edges that connect pairs of nodes. ``` Nodes: {Alice, Bob, Cara, Dave} Edges: {(Alice, Bob), (Alice, Cara), (Alice, Dave), (Bob, Cara), (Cara, Dave)} ``` Each edge says "these two nodes are connected." The order of the pair does not matter in this example, because messaging is symmetric: if Alice can message Bob, Bob can message Alice. That makes this an **undirected graph**. ## Directed graphs: when direction matters Now change the story. Suppose these are not messages but Twitter follows. Alice follows Bob, but Bob does not follow Alice. Now the direction matters. ``` Edges: {(Alice -> Bob), (Alice -> Cara), (Alice -> Dave), (Bob -> Cara), (Cara -> Dave)} ``` The arrows show who follows whom. This is a **directed graph**. The edge from Alice to Bob is not the same as the edge from Bob to Alice. In a directed graph, each edge has a source and a target. ## Weighted graphs: not all connections are equal Sometimes an edge carries extra information. In a road map, the edge between two cities might represent the driving time between them. In a social network, the edge might represent how often two people interact. When edges have numbers attached, the graph is **weighted**. The number is the **weight** of the edge. ``` Cities: {A, B, C} Edges: {(A, B, 4), (B, C, 2), (A, C, 7)} ``` The weight from A to B is 4 (maybe 4 hours of driving). The weight from A to C is 7. The shortest path from A to C is not the direct edge of weight 7. It is A -> B -> C, with total weight 4 + 2 = 6. ## Representing a graph in code There are two common ways to store a graph in code. An **adjacency list** stores, for each node, the list of nodes it connects to: ```python graph = { "Alice": ["Bob", "Cara", "Dave"], "Bob": ["Alice", "Cara"], "Cara": ["Alice", "Bob", "Dave"], "Dave": ["Alice"] } ``` An **adjacency matrix** stores a grid where the cell at row i, column j says whether node i connects to node j: ```python # A B C D # A [0, 1, 1, 1] # B [1, 0, 1, 0] # C [1, 1, 0, 1] # D [1, 0, 1, 0] ``` For sparse graphs (most nodes are not connected to most other nodes), the adjacency list is usually faster and uses less memory. For dense graphs, the matrix can be simpler to work with. ## See it run Here is a tiny graph represented as an adjacency list, with a function that counts the total number of edges. ```python runnable # An undirected graph as an adjacency list graph = { "Alice": ["Bob", "Cara", "Dave"], "Bob": ["Alice", "Cara"], "Cara": ["Alice", "Bob", "Dave"], "Dave": ["Alice", "Cara"] } def count_edges(graph): # Each edge appears twice in an undirected adjacency list (once for each endpoint) total = sum(len(neighbors) for neighbors in graph.values()) return total // 2 print("Nodes:", list(graph.keys())) print("Edges:", count_edges(graph)) print("Alice's neighbors:", graph["Alice"]) print("Dave's neighbors:", graph["Dave"]) ``` *What just happened:* The graph has four nodes. The `count_edges` function adds up all the neighbor counts and divides by two, because each undirected edge is stored twice (once for each endpoint). The result is 5 edges: Alice-Bob, Alice-Cara, Alice-Dave, Bob-Cara, Cara-Dave. Dave is only connected to Alice and Cara, which matches the story. ## For builders Graphs are not a niche math topic. They are the structure behind most of the software you touch. - **Dependency trees** - `npm install`, `pip install`, `cargo build`: all of them resolve a graph of package dependencies. A cycle in that graph (A depends on B, B depends on A) is an error. - **Social networks** - Your followers and following lists are directed edges. The "friends of friends" suggestion is a graph traversal. - **Network topology** - The internet is a graph of routers and cables. Routing protocols like OSPF and BGP are graph algorithms that find the best path. - **State machines** - A finite state machine is a directed graph where nodes are states and edges are transitions. - **Git branches** - A branch history is a directed acyclic graph. Merges create new edges. The graph structure is what makes distributed version control possible. > The key insight: any time you have things and relationships between them, you have a graph. The moment you can draw it as dots and lines, you can apply graph algorithms to it. ## What we have built - A **graph** is a set of nodes connected by edges. - An **undirected graph** has edges with no direction (symmetric). - A **directed graph** has edges with direction (asymmetric). - A **weighted graph** has numbers attached to edges. - An **adjacency list** stores, for each node, the list of its neighbors. - An **adjacency matrix** stores a grid of connections. - In code, dependency trees, social networks, and network topologies are all graphs. A quick check before you move on: ```quiz [ { "q": "In a graph representing Twitter follows, if Alice follows Bob but Bob does not follow Alice, what kind of graph is this?", "choices": ["Undirected", "Directed", "Weighted", "Empty"], "answer": 1, "explain": "The relationship is not symmetric, so the edges have direction. That makes it a directed graph. An undirected graph would require the connection to work both ways." }, { "q": "What does a weighted edge represent?", "choices": ["The color of the connection", "A number attached to the edge, such as distance, cost, or time", "The direction of the connection", "The number of nodes in the graph"], "answer": 1, "explain": "A weight is a number attached to an edge. In a road map it might be driving time. In a social network it might be interaction frequency. It quantifies the connection." }, { "q": "Which representation is usually better for a sparse graph (most nodes are not connected to most others)?", "choices": ["Adjacency matrix", "Adjacency list", "Both are equally good", "Neither works for sparse graphs"], "answer": 1, "explain": "An adjacency list stores only the connections that exist, so it uses less memory and is faster to iterate for sparse graphs. An adjacency matrix stores every possible pair, which wastes space when most pairs are not connected." } ] ``` --- # Finding the Shortest Path and Detecting Cycles ## The question a GPS asks every second You open a map app. You type "cafe" and your current location. The app draws a line from your position to the nearest coffee shop. That line is the **shortest path** - the route with the smallest total weight, where weight might be distance, time, or traffic. Finding that path is one of the most common graph problems in computing. The algorithm that solves it is called **Dijkstra's algorithm**, and it is one of the most useful pieces of applied mathematics ever written. But before we reach Dijkstra, we need two simpler ways to walk through a graph: BFS and DFS. ## BFS: spreading out in circles **Breadth-first search** (BFS) explores a graph by visiting all the neighbors of a node before moving on to the neighbors of those neighbors. It spreads out like a ripple in a pond. If you are one degree of separation from everyone in your network, BFS will find them in the first round. If you are two degrees away, BFS will find them in the second round. It finds the shortest path in an unweighted graph because it explores all paths of length 1, then all paths of length 2, and so on. The first time it reaches a node, it has done so by the shortest possible route. ## DFS: following one path as far as it goes **Depth-first search** (DFS) goes the opposite direction. It picks a neighbor and follows it as far as it can, backtracking only when it hits a dead end. It is a systematic way of exploring every possible path, but it does not guarantee the shortest path. DFS is useful when you want to know "is there any path at all?" or "what does the entire connected component look like?" It is also the foundation of many other algorithms, including cycle detection and topological sort. ## Dijkstra: the shortest weighted path BFS finds the shortest path when every edge has the same weight. In the real world, edges usually have different weights. A highway is faster than a side road. A direct flight is shorter than a connection. Dijkstra's algorithm handles weighted graphs. The idea is simple: always expand the node with the smallest known distance from the start. Keep a list of "tentative distances" and update them as you discover shorter routes. When you reach the destination, the tentative distance is the shortest possible. ``` Start at A. Distance to A is 0. Distance to everything else is infinity. Look at A's neighbors. Update their distances. Pick the neighbor with the smallest distance. Expand it. Repeat until you reach the target. ``` For a graph with thousands of nodes and edges, Dijkstra runs fast enough for real-time use. That is why your map app can recalculate your route while you are still driving. ## Detecting cycles: the loop that breaks everything A **cycle** is a path that starts and ends at the same node. In a social network, a cycle is a friend group. In a dependency graph, a cycle is a disaster: A depends on B, B depends on C, C depends on A. Nothing can be installed because everything is waiting for something else. Detecting a cycle is straightforward with DFS. As you walk through the graph, keep track of the nodes you are currently visiting (the "recursion stack"). If you ever reach a node that is already in the stack, you have found a cycle. This is why `npm install` or `cargo build` can tell you "circular dependency detected." It ran a cycle detection algorithm on the dependency graph and found a loop. ## Topological sort: ordering things that depend on each other Sometimes you have a directed graph where edges mean "must come before." A depends on B, so B must be built before A. A course prerequisite graph works the same way: you must take Calculus before taking Differential Equations. A **topological sort** is an ordering of the nodes where every edge points forward. If there is a cycle, no such ordering exists, and the graph is not a valid dependency structure. Topological sort is the algorithm behind build systems, task runners, and course planners. It answers: "in what order can I do all of these things, given that some of them depend on others?" ## See it run Here is BFS for shortest path in an unweighted graph, and a cycle detection function using DFS. ```python runnable from collections import deque # A directed, unweighted graph (a dependency graph) as an adjacency list graph = { "A": ["B", "C"], "B": ["D", "E"], "C": ["F"], "D": [], "E": ["F"], "F": [] } def bfs_shortest_path(graph, start, target): visited = set() queue = deque([(start, [start])]) visited.add(start) while queue: node, path = queue.popleft() if node == target: return path for neighbor in graph[node]: if neighbor not in visited: visited.add(neighbor) queue.append((neighbor, path + [neighbor])) return None def has_cycle_dfs(graph): visited = set() rec_stack = set() def dfs(node): visited.add(node) rec_stack.add(node) for neighbor in graph[node]: if neighbor not in visited: if dfs(neighbor): return True elif neighbor in rec_stack: return True rec_stack.remove(node) return False for node in graph: if node not in visited: if dfs(node): return True return False print("Shortest path from A to F:", bfs_shortest_path(graph, "A", "F")) print("Graph has cycle:", has_cycle_dfs(graph)) # Add a cycle: F connects back to A graph_cyclic = { "A": ["B", "C"], "B": ["D", "E"], "C": ["F"], "D": [], "E": ["F"], "F": ["A"] # back-edge -> cycle A -> C -> F -> A } print("Cyclic graph has cycle:", has_cycle_dfs(graph_cyclic)) ``` *What just happened:* The `bfs_shortest_path` function found the shortest path from A to F: A -> C -> F. BFS guarantees this is the shortest because it explores all paths of length 1, then length 2, and so on. The `has_cycle_dfs` function used depth-first search with a recursion stack to detect cycles. The first graph had no cycle. The second graph, with the added edge F -> A, created a cycle A -> C -> F -> A, and the function detected it. ## The same walk, in other languages Here is that BFS shortest-path walk on its own, in seven languages. The shape is always the same: a queue of paths, a set of visited nodes, and the first arrival at the target wins because BFS reaches every node by its shortest route first. [[codegroup BFS Shortest Path]] ```python from collections import deque def bfs_shortest_path(graph, start, target): visited = {start} queue = deque([(start, [start])]) while queue: node, path = queue.popleft() if node == target: return path for neighbor in graph[node]: if neighbor not in visited: visited.add(neighbor) queue.append((neighbor, path + [neighbor])) return None ``` ```javascript function bfsShortestPath(graph, start, target) { const visited = new Set([start]); const queue = [[start, [start]]]; while (queue.length) { const [node, path] = queue.shift(); if (node === target) return path; for (const neighbor of graph[node]) { if (!visited.has(neighbor)) { visited.add(neighbor); queue.push([neighbor, [...path, neighbor]]); } } } return null; } ``` ```typescript type Graph = Record; function bfsShortestPath(graph: Graph, start: string, target: string): string[] | null { const visited = new Set([start]); const queue: [string, string[]][] = [[start, [start]]]; while (queue.length) { const [node, path] = queue.shift()!; if (node === target) return path; for (const neighbor of graph[node]) { if (!visited.has(neighbor)) { visited.add(neighbor); queue.push([neighbor, [...path, neighbor]]); } } } return null; } ``` ```java static List bfsShortestPath(Map> graph, String start, String target) { Set visited = new HashSet<>(List.of(start)); Queue> queue = new ArrayDeque<>(); queue.add(List.of(start)); while (!queue.isEmpty()) { List path = queue.poll(); String node = path.get(path.size() - 1); if (node.equals(target)) return path; for (String neighbor : graph.get(node)) { if (!visited.contains(neighbor)) { visited.add(neighbor); List next = new ArrayList<>(path); next.add(neighbor); queue.add(next); } } } return null; } ``` ```cpp std::vector bfs_shortest_path( std::map>& graph, const std::string& start, const std::string& target) { std::set visited{start}; std::queue> queue; queue.push({start}); while (!queue.empty()) { auto path = queue.front(); queue.pop(); const std::string& node = path.back(); if (node == target) return path; for (const auto& neighbor : graph[node]) { if (!visited.count(neighbor)) { visited.insert(neighbor); auto next = path; next.push_back(neighbor); queue.push(next); } } } return {}; } ``` ```go func bfsShortestPath(graph map[string][]string, start, target string) []string { visited := map[string]bool{start: true} queue := [][]string{{start}} for len(queue) > 0 { path := queue[0] queue = queue[1:] node := path[len(path)-1] if node == target { return path } for _, neighbor := range graph[node] { if !visited[neighbor] { visited[neighbor] = true next := append(append([]string{}, path...), neighbor) queue = append(queue, next) } } } return nil } ``` ```rust use std::collections::{HashMap, HashSet, VecDeque}; fn bfs_shortest_path( graph: &HashMap<&str, Vec<&str>>, start: &str, target: &str, ) -> Option> { let mut visited: HashSet<&str> = HashSet::from([start]); let mut queue: VecDeque> = VecDeque::from([vec![start.to_string()]]); while let Some(path) = queue.pop_front() { let node = path.last().unwrap().as_str(); if node == target { return Some(path); } for &neighbor in &graph[node] { if visited.insert(neighbor) { let mut next = path.clone(); next.push(neighbor.to_string()); queue.push_back(next); } } } None } ``` [[/codegroup]] ## For builders Graph algorithms are not academic exercises. They are the reason your software works. - **Package managers** - `npm`, `pip`, `cargo` all resolve dependency graphs. A cycle in that graph is an error. A topological sort gives the installation order. - **Social networks** - "People you may know" is often a graph traversal. "Friends of friends" is BFS with depth 2. - **Network routing** - OSPF and other routing protocols use variants of Dijkstra to find the fastest path through a network of routers. - **Build systems** - `make`, `bazel`, and `gradle` all use topological sort to decide which files to compile first. - **Game AI** - Pathfinding in games uses A-star, a variant of Dijkstra that uses a heuristic to explore promising paths first. > The key insight: any time you have things and prerequisites or connections between them, you have a graph. The moment you can draw it, you can run algorithms on it to find shortest paths, detect cycles, or order the nodes. ## What we have built - A **graph** is nodes connected by edges. - An **undirected graph** has symmetric edges. A **directed graph** has asymmetric edges with direction. - A **weighted graph** has numbers attached to edges. - **BFS** explores level by level and finds the shortest path in an unweighted graph. - **DFS** follows one path as far as it can go, then backtracks. - **Dijkstra's algorithm** finds the shortest weighted path by always expanding the closest unvisited node. - **Cycle detection** uses DFS with a recursion stack to find loops. - **Topological sort** orders nodes so that every edge points forward, or reports that no such order exists. A quick check before you move on: ```quiz [ { "q": "In an unweighted graph, which algorithm guarantees the shortest path?", "choices": ["DFS", "BFS", "Dijkstra", "Topological sort"], "answer": 1, "explain": "BFS explores all nodes at distance 1, then distance 2, and so on. The first time it reaches a node, it has done so by the shortest possible path. DFS does not guarantee shortest path." }, { "q": "What does it mean if a directed graph has a cycle?", "choices": ["The graph is empty", "There is a path that starts and ends at the same node", "All nodes are connected to each other", "The graph has no edges"], "answer": 1, "explain": "A cycle is a path that starts and ends at the same node. In a dependency graph, a cycle means A depends on B, B depends on C, and C depends on A - nothing can be resolved." }, { "q": "When would you use Dijkstra's algorithm instead of BFS?", "choices": ["When the graph has no edges", "When the graph is directed", "When edges have different weights and you need the shortest weighted path", "When you want to detect cycles"], "answer": 2, "explain": "BFS finds the shortest path when every edge has the same weight. Dijkstra handles weighted edges by always expanding the node with the smallest known distance from the start." } ] ``` --- # Graphs That Run the World ## The pattern you already know In Phase 1 you learned that a graph is nodes and edges. In Phase 2 you learned to walk through graphs, find shortest paths, and detect cycles. Now you are going to see those same nodes and edges running the world. The pattern is always the same: 1. Identify the things (people, web pages, packages, routers). 2. Identify the connections between them (follows, links, dependencies, cables). 3. Draw it as a graph. 4. Run graph algorithms on it to find something useful. That is Google search. That is your package manager resolving dependencies. That is the internet routing your email. That is the social network suggesting who to follow. ## PageRank: the graph that made Google In the late 1990s, the web was a mess of pages linking to other pages. The question was: which pages are important? Larry Page and Sergey Brin realized that a link from one page to another is a vote. But not all votes are equal. A vote from an important page should count more than a vote from an unimportant one. So they built a graph. Each web page is a node. Each link is a directed edge from the linking page to the linked page. Then they assigned an importance score to each node and let the scores flow along the edges. The rule is simple: a page's importance is the sum of the importance of all pages that link to it, divided by the number of links on each of those pages. A link from a page with high importance and few outgoing links is worth more than a link from a page with low importance and many outgoing links. Run that rule over and over, like water flowing through pipes, and the scores settle down. The result is PageRank. The math is graph theory: a directed graph of links, and an iterative transformation that redistributes importance along the edges. You do not need to implement PageRank to use the insight. Every time you search for something and the "right" answer appears near the top, you are seeing graph theory at work. ## Social networks: the graph of who knows whom Your social network is a graph. You are a node. Your friends are nodes connected to you by edges. Their friends are nodes connected to them. The whole structure stretches out to billions of nodes and trillions of edges. When a social network suggests "people you may know," it is running a graph algorithm. The most common approach is something like: "you have 12 friends in common, and none of them are connected to each other." That is a graph pattern: two nodes with many common neighbors and no direct edge. When a feed algorithm decides what to show you, it is traversing the graph of your interactions. The posts from nodes you interact with most heavily are weighted more. The graph structure determines what you see. ## Package managers: the dependency graph When you run `npm install` or `pip install`, the tool is solving a graph problem. Each package is a node. Each dependency is a directed edge: "this package needs that package." The tool must find an ordering of the nodes where every edge points forward - a topological sort. If the graph has a cycle, the tool cannot proceed. Package A needs B, B needs C, and C needs A. Nothing can be installed because everything is waiting for something else. The error message "circular dependency detected" is a graph algorithm telling you that the dependency graph is not a valid partial order. This is why lock files exist. They record the exact version of every package that was chosen when the graph was solved. If you delete the lock file and reinstall, you might get a different solution, because the graph has multiple valid orderings. ## Network routing: the graph of the internet The internet is a graph. The nodes are routers. The edges are the cables and wireless links between them. When you send a packet from your computer to a server, the packet travels through a sequence of routers. The path it takes is determined by routing protocols that run graph algorithms in real time. OSPF (Open Shortest Path First) is a protocol where each router knows the weight of its own edges (usually based on speed or cost) and shares that information with its neighbors. Each router then runs Dijkstra's algorithm to compute the shortest path to every destination. The result is a routing table: for every possible destination, the next hop to send the packet toward. This happens millions of times per second across the globe. The internet works because every router is running a graph algorithm, all the time. ## For builders This is the part where graph theory stops being abstract and starts being the reason your software works. - **Dependency resolution** - Every build system, package manager, and container orchestrator solves a graph problem. Understanding the graph structure helps you debug "why is this taking so long" and "why did this cycle appear." - **Social features** - "Friends of friends," "suggested connections," "community detection" are all graph algorithms. If you are building any feature that involves relationships between users, you are building a graph feature. - **Data pipelines** - A data pipeline with branching and merging is a directed acyclic graph. Tools like Airflow and Prefect let you define pipelines as DAGs (directed acyclic graphs) and execute them in the correct order. - **Recommendation systems** - Collaborative filtering often builds a bipartite graph of users and items, then uses graph algorithms to find similar nodes. - **Infrastructure** - Your network topology, your service mesh, your deployment pipeline: all graphs. Understanding the graph structure helps you reason about failure modes, bottlenecks, and blast radius. > The key insight: any time you have things and relationships between them, you have a graph. The moment you can draw it as dots and lines, you can apply graph algorithms to find shortest paths, detect cycles, rank nodes, or order tasks. ## What we have built - A **graph** is nodes connected by edges, representing relationships between things. - **BFS** explores level by level and finds the shortest path in an unweighted graph. - **DFS** follows one path as far as it can go, then backtracks. - **Dijkstra's algorithm** finds the shortest weighted path by always expanding the closest node. - **Cycle detection** finds loops in a graph, which is essential for dependency validation. - **Topological sort** orders nodes so that every edge points forward, or reports that no such order exists. - **PageRank** uses a directed graph of links and iterative importance flow to rank web pages. - **Social networks** use graph traversal to suggest connections and rank content. - **Package managers** use topological sort to resolve dependencies and detect cycles. - **Network routing** uses Dijkstra's algorithm to compute shortest paths across the internet. You started this guide with a simple question: "what is connected to what?" You ended with the algorithms that run Google, npm, the internet, and your social feed. The same dots and lines you drew on a whiteboard in Phase 1 are the structure behind most of the digital world. A quick check before you go: ```quiz [ { "q": "PageRank treats the web as what kind of graph?", "choices": ["An undirected graph of web pages", "A directed graph where edges are links from one page to another", "A weighted graph where weights are page sizes", "A tree structure of categories"], "answer": 1, "explain": "PageRank models the web as a directed graph. Each web page is a node, and each hyperlink is a directed edge from the linking page to the linked page. Importance flows along these directed edges." }, { "q": "Why does a package manager need to detect cycles in the dependency graph?", "choices": ["Cycles make the graph look messy", "A cycle means A depends on B, B depends on C, and C depends on A, so nothing can be installed", "Cycles slow down the installation", "Cycles are not a problem; they are ignored"], "answer": 1, "explain": "A circular dependency means every package in the cycle is waiting for another package in the same cycle. Nothing can be resolved until the cycle is broken, so the package manager reports an error." }, { "q": "What algorithm do most internet routers use to compute the shortest path to every destination?", "choices": ["BFS", "DFS", "Dijkstra's algorithm", "Topological sort"], "answer": 2, "explain": "Routers run Dijkstra's algorithm (or a variant) on the network graph, where edge weights represent cost, speed, or delay. The result is a routing table that tells each router where to send packets next." } ] ```