Shortest path algorithms (BFS/Dijkstra conceptually) - Discrete Math

In a BFS tree rooted at vertex $r$ , you observe that vertex $x$ is at level $4$ and vertex $y$ is at level $6$ . The original graph contains edges $(x,y)$ and $(y,x)$ (since the graph is undirected). During the BFS traversal, when are these edges examined?
Answer: The edge is examined twice: once when $x$ is processed and once when $y$ is processed In BFS on an undirected graph, each undirected edge {x,y} is represented in the adjacency structure as two directed edges: (x,y) in x's adjacency list and (y,x) in y's adjacency list. When BFS processes vertex x (level 4), it examines edge (x,y) and finds y already discovered at level 6. Later, when BFS processes vertex y (level 6), it examines edge (y,x) and finds x already processed. So the same undirected edge is examined from both endpoints. A and D are correct about examining twice, but A incorrectly treats them as different edges. B and C are wrong because the edge is examined from both vertices.
In a weighted graph, you run Dijkstra's algorithm and find that the shortest path from source $s$ to target $t$ has length $25$ and passes through vertices $s \to u \to v \to t$ . If you increase the weight of edge $(u,v)$ by $5$ , what can you determine about the new shortest path distance from $s$ to $t$ ?
Answer: The new distance is at least $25$ since shortest paths cannot decrease when weights increase When edge weights increase, shortest path distances can only stay the same or increase - they cannot decrease. The original shortest path distance was 25. After increasing edge (u,v) by 5, the path s→u→v→t now has length 30. However, there might be alternative paths from s to t that don't use edge (u,v), and these paths maintain their original lengths. The new shortest path will be the minimum among all possible paths, which is at least 25 (the original distance). A is wrong because alternative paths might be shorter than 30. B gives an upper bound but the question asks what we can determine definitively. D is impossible since increasing weights cannot improve shortest paths.
Consider a weighted graph where Dijkstra's algorithm is running. At some iteration, vertex $w$ is about to be processed (extracted from priority queue with distance $d$ ). You notice that $w$ has an incoming edge from vertex $z$ with weight $c$ , where $z$ was processed earlier with distance $d_z$ . What constraint must hold for the algorithm's correctness?
Answer: $d \leq d_z + c$ to ensure the shortest path property is maintained For Dijkstra's correctness, when a vertex w is processed with distance d, this must be the shortest path distance. Since z was processed earlier with distance $d_z$ , and there's an edge (z,w) with weight c, one possible path to w has length $d_z$ + c. The actual shortest path to w (which is d) cannot be longer than any path, so d ≤ $d_z$ + c. B is wrong because w might have been discovered through a different vertex. C is wrong because d could be less than $d_z$ + c if a shorter path exists. D is wrong because the inequality direction is incorrect.
During BFS execution on a graph, the queue at some moment contains vertices $[S, T, U]$ in that order, where $S$ is at the front. When you dequeue and process $S$ , you discover that $S$ has edges to vertices $V$ (undiscovered) and $W$ (undiscovered). What will be the state of the queue immediately after processing $S$ ?
Answer: $[T, U, V, W]$ with new vertices added to the rear BFS uses a FIFO queue where vertices are added to the rear when discovered and removed from the front when processed. After dequeuing S, the queue has [T, U]. When S is processed and discovers V and W, these are added to the rear in the order they're discovered, resulting in [T, U, V, W]. B is wrong because BFS is not a stack (LIFO). C is wrong because discovered vertices are queued for later processing, not processed immediately. D is wrong because new vertices are added to the rear, not interleaved.
Consider running BFS on a graph starting from vertex $A$ . At some point during execution, the queue contains vertices $[P, Q, R]$ where $P$ is at the front. You know that $P$ and $Q$ are both at distance $3$ from $A$ , while $R$ is at distance $4$ . What can you conclude about the next vertex to be processed after $P$ ?
Answer: The next vertex processed must be $Q$ since it's next in the queue When analyzing BFS execution, focus on how the queue operates and what "processing" means. BFS uses a first-in-first-out queue where vertices are added to the back and removed from the front for processing. The correct answer is D because BFS strictly follows queue order. When the queue contains $[P, Q, R]$ with $P$ at the front, processing $P$ means removing it from the queue, leaving $[Q, R]$ . The next vertex to be processed is always the new front of the queue, which is $Q$ . This is fundamental to how BFS works - it's a queue-driven algorithm. Option A is incorrect because adjacency list ordering affects which vertices $P$ discovers and enqueues, but doesn't change that $Q$ is next to be processed. Option B misunderstands BFS behavior - while BFS does explore by distance layers, it doesn't skip vertices in the queue to process higher-distance vertices first. $R$ at distance 4 will eventually be processed, but only after all distance-3 vertices currently in the queue. Option C confuses "processing" with "enqueuing." Any vertices that $P$ discovers will be added to the back of the queue (after $R$ ), but the next vertex to be processed is still $Q$ . Remember that BFS has two distinct phases: processing a vertex (removing it from the queue front) and discovering new vertices (adding them to the queue back). Always distinguish between these operations when analyzing BFS execution order.
A modified version of Dijkstra's algorithm is run on a graph where instead of selecting the vertex with minimum distance, we select the vertex with maximum distance among all unprocessed vertices with finite distance. If the graph has edge weights 1, 2, 3, 5, 8 and we start from vertex $S$ , what property does this modified algorithm guarantee about the paths it finds?
Answer: It finds some path from $S$ to each vertex, but with no optimality guarantee The modified algorithm breaks the fundamental property of Dijkstra's algorithm. In standard Dijkstra's, we select the minimum distance vertex because once a vertex is processed, we're guaranteed to have found its shortest path (no unprocessed vertex can provide a shorter route). By selecting the maximum distance vertex, we lose this guarantee. The algorithm will still find paths to all reachable vertices, but these paths are not guaranteed to be optimal in any meaningful sense. Choice A is wrong because shortest path optimality is lost. Choice B is wrong because longest simple path is NP-hard and this greedy approach won't solve it. Choice D describes a different optimization criterion not achieved by this modification.
In a weighted graph with positive edge weights, you run Dijkstra's algorithm starting from vertex $s$ . After the algorithm terminates, you discover that vertex $v$ has distance $d(v) = 15$ . Later, you add a new edge $(u,v)$ with weight $3$ to the graph, where $u$ had distance $d(u) = 10$ in the original run. What can you conclude about the shortest path distance from $s$ to $v$ in the new graph?
Answer: The new shortest path distance is at most $13$ Adding edge (u,v) with weight 3 creates a potential path from s to v with total distance d(u) + 3 = 10 + 3 = 13. Since shortest paths can only decrease or stay the same when edges are added, the new distance is min(15, 13) = 13 at most. However, there might be an even shorter path through other vertices that we haven't considered. A is wrong because we can't guarantee it's exactly 13. C is wrong because the path s→u→v gives distance 13 < 15. D is wrong because we have no information suggesting a path of length 12.
You are implementing Dijkstra's algorithm and need to choose between different priority queue implementations. Your graph has $V$ vertices and $E$ edges. You perform $V$ extract-min operations and up to $E$ decrease-key operations. If you use a binary heap, what is the total time complexity of the priority queue operations?
Answer: $O(V \log V + E \log V)$ for extract-min and decrease-key operations combined In a binary heap, extract-min takes O(log V) time and there are V such operations, giving O(V log V). Decrease-key also takes O(log V) time and there are up to E such operations, giving O(E log V). Total time is O(V log V + E log V). A is wrong because decrease-key is not O(1) in binary heaps. C misses the extract-min contribution. D is wrong about both complexities - extract-min is O(log V) per operation, not O(V), and decrease-key is O(log V), not O(1).
Consider two implementations of shortest path algorithms on the same weighted graph: Algorithm X processes vertices in order of increasing distance (like Dijkstra), while Algorithm Y processes vertices in decreasing order of their degree (number of neighbors). Both algorithms start from the same source vertex $s$ . Under what conditions will both algorithms produce the same shortest path tree?
Answer: When the graph is a tree (no cycles) In a tree, there is exactly one path between any pair of vertices, so this unique path is automatically the shortest path. Since there are no cycles, the order in which vertices are processed doesn't affect the final shortest path tree - there's only one possible tree connecting all vertices. Algorithm X (Dijkstra-like) will find shortest paths, and Algorithm Y will also find the same paths because there are no alternative routes to consider. Choice A is wrong because even with unit weights, the processing order matters in graphs with cycles. Choice C is not sufficient because degree-distance correlation doesn't guarantee same results. Choice D is wrong because having unique shortest paths doesn't mean different processing orders will discover them in the same tree structure.
Consider running Dijkstra's algorithm on a graph where all edge weights are positive integers. At some point during execution, vertex $u$ has tentative distance 10 and vertex $v$ has tentative distance 15. If there's an edge $(u,v)$ with weight 3, under what condition would this edge NOT cause an update to $v$ 's distance when $u$ is processed?
Answer: When $v$ has already been processed by the algorithm In Dijkstra's algorithm, when vertex u is processed, we examine all edges (u,v) and potentially update d(v) = min(d(v), d(u) + weight(u,v)). Here, d(u) + weight(u,v) = 10 + 3 = 13 < 15 = d(v), so normally v's distance would be updated to 13. The only reason this update wouldn't occur is if v has already been processed (finalized) by the algorithm. Once a vertex is processed in Dijkstra's algorithm, its distance is final and never updated again. Choice B is incorrect because even if shorter paths exist, the relaxation step would still be performed. Choice C is irrelevant since all weights are positive. Choice D is unrelated to the relaxation process.
Consider a graph where BFS is performed starting from vertex $s$ . The algorithm discovers vertices in this order: $s, a, b, c, d, e$ . You know that $a$ and $b$ are both at distance $1$ from $s$ , and $c, d, e$ are all at distance $2$ . Which statement about the graph structure must be true?
Answer: Each of $c, d, e$ is adjacent to at least one vertex in $\{s, a, b\}$ In BFS, vertices at distance k are discovered by exploring edges from vertices at distance k-1. Since c, d, e are at distance 2, each must be reachable from some vertex at distance 1 or 0. The vertices at distance ≤ 1 are {s, a, b}, so each of c, d, e must be adjacent to at least one of these. A is wrong because vertices at the same level need not be adjacent. B is wrong because the discovery order among vertices at the same level depends on which vertex processed them, not direct adjacency. D is correct that d and e are not adjacent to s (since they're at distance 2), but this doesn't contradict C.
In a BFS traversal of an unweighted graph, you observe that vertices $P$ and $Q$ are discovered at the same level (distance $k$ from the source). Later in the traversal, when processing vertex $P$ , you discover a new vertex $R$ through edge $(P,R)$ . At what distance will $R$ be labeled?
Answer: Distance $k+1$ following the BFS level-by-level exploration property In BFS, when a vertex at distance k discovers a new vertex through an edge, the new vertex is assigned distance k+1. This maintains the level-by-level exploration property where all vertices at distance d are processed before any vertex at distance d+1. Since P is at distance k and discovers R, then R gets distance k+1. A is wrong because adjacent vertices differ by exactly 1 in distance. C is wrong because it adds an extra level. D is wrong because BFS assigns increasing distances as it moves away from the source.
In Dijkstra's algorithm, you maintain a priority queue of vertices with their tentative distances. At some point during execution, the queue contains vertices $\{B:7, C:12, D:9, E:15\}$ where the number after each vertex is its current tentative distance. When you extract the minimum and process vertex $B$ , you find it has edges to $C$ (weight $2$ ) and $D$ (weight $5$ ). What will be the state of the priority queue after processing $B$ ?
Answer: $\{C:9, D:9, E:15\}$ with a tie between $C$ and $D$ When processing B (distance 7), we examine its edges. For edge (B,C) with weight 2: new distance = 7+2 = 9 < 12, so C's distance updates to 9. For edge (B,D) with weight 5: new distance = 7+5 = 12 > 9, so D's distance stays 9. The queue becomes {C:9, D:9, E:15} with C and D tied for minimum. B is wrong because D was already at distance 9. C is wrong because D's distance doesn't change from 9. D is wrong because C's distance does improve from the new path through B.
If person $A$ starts a rumor at time 0, and the rumor reaches person $B$ at time 3, what can we conclude about adding a friendship edge between $A$ and person $C$ , who currently receives the rumor at time 5?
Answer: Adding edge $(A,C)$ would guarantee that $C$ receives the rumor at time 1 In the BFS rumor model, the time when a person receives the rumor equals their shortest path distance from the source. Person B receives the rumor at time 3, meaning the shortest path from A to B has length 3. Person C receives the rumor at time 5, meaning the shortest path from A to C has length 5. If we add a direct edge (A,C), then C would be directly connected to A, creating a path of length 1 from A to C. Since BFS finds shortest paths and this new edge creates a shorter path than any existing path, C would receive the rumor at time 1. Choice B is wrong because the time would be exactly 1, not 'at most 2'. Choice C is wrong because the new edge definitely creates a shorter path. Choice D is wrong because adding edges cannot increase shortest path distances.

Start this quiz