Discrete Math Quiz: Shortest Path Algorithms

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?

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?

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?

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$?

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$?

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?

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$?

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?

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$?

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?

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?

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?

A social network is modeled as an unweighted graph where each vertex represents a person and each edge represents a friendship. The network has the property that any two people are connected by at most 4 intermediate friends (i.e., the diameter is at most 6). A rumor spreading algorithm uses BFS to model how information spreads, where each person tells the rumor to all their friends simultaneously in discrete time steps.

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?

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?