Shortest Path Practice Questions

The weight of a shortest path of length at most $k+1$ is calculated over a set of paths that includes all paths of length at most $k$. Since $d_{k+1}(u)$ minimizes the path weight over a superset of the paths considered for $d_k(u)$, it follows that $d_{k+1}(u) \leq d_k(u)$ for all $k \geq 0$ and $u \in V$. Thus, S1 is true.

For S2, consider a graph with vertices $\{s, u, v\}$ and edges $(s, u)$ with weight $0$ and $(u, v)$ with weight $-10$. The edge $(u, v)$ is part of the shortest path from $s$ to $v$. For $k=2$, the shortest path from $s$ to $u$ has weight $d_2(u) = 0$, and the shortest path from $s$ to $v$ has weight $d_2(v) = 0 + (-10) = -10$. Since $0 \not\leq -10$, the condition $d_k(u) \leq d_k(v)$ fails. Thus, S2 is false.

To find the lengths of shortest paths from a source vertex $s$ in a weighted Directed Acyclic Graph (DAG), the most efficient algorithm uses topological sorting.

First, perform a topological sort on the vertices. This orders the vertices such that for any edge $(u, v)$, $u$ appears before $v$. This step takes $\Theta(n + m)$ time, where $n$ is the number of vertices and $m$ is the number of edges.

Next, initialize the distance to the source vertex $s$ as $dist(s) = 0$ and all other vertices as $dist(v) = \infty$. Then, process vertices in the topological order. For each vertex $u$, iterate through its outgoing edges $(u, v)$ and perform edge relaxation: if $dist(u) + weight(u, v) < dist(v)$, then update $dist(v) = dist(u) + weight(u, v)$. Since each vertex is processed once and each edge is relaxed once, this phase takes $\Theta(m)$ time.

The total worst-case time complexity is the sum of these steps: $\Theta(n + m) + \Theta(m) = \Theta(n + m)$.

1. When a positive constant $\alpha$ is added to every edge weight, the relative order of edge weights for Minimum Spanning Trees (MSTs) does not change.
2. If $w(e_1) < w(e_2)$ before the update, then $w(e_1) + \alpha < w(e_2) + \alpha$ after the update. Thus, MSTs remain the same.
3. For Shortest Paths (SPs), adding a constant $\alpha$ to all edge weights might change the shortest path.
4. If a path $P_1$ has $k$ edges and another path $P_2$ has $m$ edges, and $k \neq m$, their relative total weights might change.
5. Original path lengths: $L(P_1)$ and $L(P_2)$. New path lengths: $L(P_1) + k\alpha$ and $L(P_2) + m\alpha$. If $k \neq m$, $P_1$ might be shorter initially but longer after the update.

The maximum value of $d(u, v)$ in graph $G$ is 30, which means the diameter of the graph is 30.
A Breadth-First Search (BFS) tree is constructed by starting from a source vertex and exploring all its neighbors at the current depth before moving to the next depth. The edges in a BFS tree represent shortest paths from the source vertex to all other reachable vertices.
The height of a BFS tree starting from any vertex $s$ is the maximum shortest distance from $s$ to any other vertex in the graph. Since the diameter of the graph is 30, there must exist at least one pair of vertices $(u,v)$ such that $d(u,v) = 30$.
If the BFS tree is rooted at one of the vertices $u$ from this diameter-defining pair, the height of the BFS tree will be exactly $d(u,v)$, which is 30. If the BFS tree is rooted at a different vertex, its height might be less than 30, but it cannot be arbitrarily small.
However, since the diameter is 30, any BFS tree constructed must have a height that is at least half of the diameter, or possibly greater depending on the source vertex. For an unweighted graph, the height of a BFS tree is bounded by the diameter. Specifically, for any chosen root, the height of the BFS tree $T$ will be at least $\lceil \text{diameter}/2 \rceil$. Therefore, the height of $T$ must be at least $\lceil 30/2 \rceil = 15$.

The adjacency matrix $N$ for $G_2$ indicates that an edge $(i, j)$ exists in $G_2$ if there is an edge $(i, j)$ in $G$ (i.e., $M_{ij} > 0$) or if there is a path of length 2 between $i$ and $j$ in $G$ (i.e., $P_{ij} > 0$, where $P=M^2$).
This means $G_2$ will have edges connecting vertices that are at a distance of 1 or 2 in $G$.
Consequently, any path of length $k$ in $G$ will correspond to a path of length at most $\lceil k/2 \rceil$ in $G_2$.
Therefore, the diameter of $G_2$ will be less than or equal to half the diameter of $G$, specifically $diam(G_2) \leq \lceil diam(G)/2 \rceil$.
For example, if $G$ is a path graph $a-b-c-d$, $diam(G)=3$. In $G_2$, edges $(a,c)$ and $(b,d)$ are added, resulting in $diam(G_2)=2$, which satisfies $2 \leq \lceil 3/2 \rceil = 2$.

This problem describes a re-weighting of edges in a graph and asks under what conditions shortest paths are preserved. The new edge weight $w'(u,v)$ is defined as $w(u,v)+f(u)-f(v)$.

Consider any path from a source vertex $s$ to a destination vertex $t$: $s=v_0, v_1, \dots, v_k=t$.
The original path weight is $W = \sum_{i=0}^{k-1} w(v_i, v_{i+1})$.
The new path weight is $W' = \sum_{i=0}^{k-1} w'(v_i, v_{i+1}) = \sum_{i=0}^{k-1} (w(v_i, v_{i+1}) + f(v_i) - f(v_{i+1}))$.
Expanding the sum for $W'$, we get:
$W' = \sum_{i=0}^{k-1} w(v_i, v_{i+1}) + \sum_{i=0}^{k-1} (f(v_i) - f(v_{i+1}))$
The second summation is a telescoping sum:
$\sum_{i=0}^{k-1} (f(v_i) - f(v_{i+1})) = (f(v_0) - f(v_1)) + (f(v_1) - f(v_2)) + \dots + (f(v_{k-1}) - f(v_k)) = f(v_0) - f(v_k) = f(s) - f(t)$.
So, $W' = W + f(s) - f(t)$.

Since $f(s) - f(t)$ is a constant for all paths between a given $s$ and $t$, adding this constant to the path weight does not change which path is the shortest. If path A has a smaller original weight than path B ($W_A < W_B$), then $W_A + f(s) - f(t) < W_B + f(s) - f(t)$, meaning path A still has a smaller new weight. This property holds true regardless of the choice of function $f: V \rightarrow \mathbb{R}$.

Statement (I) is true. A well-known property of graphs is that if all edge weights are distinct, the Minimum Spanning Tree (MST) is unique. This is because algorithms like Kruskal's or Prim's will have a unique choice for the next edge to add at every step.

Statement (II) is false. The shortest path between two vertices is not necessarily unique, even if all edge weights are distinct. The provided PDF solution gives a counterexample where two different paths, B-A-C and B-C, have the same total weight of 3, demonstrating that multiple shortest paths can exist.

The solution in the provided PDF is 11. This can be derived by finding the condition under which the edge with weight x becomes part of a unique shortest path.

Let the vertices be 1, 2, 3, and 4. The edge in question is (3, 4) with weight x. To determine if this edge is on a shortest path, we compare its weight to the shortest alternative path between vertices 3 and 4.

The alternative paths between 3 and 4 are:

• 3-1-4: weight 8 + 5 = 13
• 3-2-4: weight 5 + 8 = 13
• 3-2-1-4: weight 5 + 2 + 5 = 12

The shortest alternative path has a weight of 12. For the direct edge (3, 4) to be the unique shortest path, its weight x must be strictly less than the weight of any other path. Therefore, we must have $x < 12$. The largest integer value of x that satisfies this condition is 11.

Statement P is true. The Minimum Spanning Tree (MST) is determined by the relative order of edge weights. Adding a constant value to every edge does not change this relative order, so algorithms like Kruskal's or Prim's will select the same set of edges, resulting in the same MST.

Statement Q is false. The shortest path can change because adding a constant penalizes paths with more edges. A path that was originally shorter but had more edges might become longer than a path with fewer edges after the weights are increased.

For any edge $(u, v)$ in a graph $G$, the shortest path distances $d(u)$ and $d(v)$ from a source $s$ must satisfy the triangle inequality $d(u) \le d(v) + 1$ and $d(v) \le d(u) + 1$.
Rearranging these inequalities yields $|d(u) - d(v)| \le 1$.
Consequently, the difference $d(u) - d(v)$ can only take values in the set $\{-1, 0, 1\}$.
Since $|d(u) - d(v)|$ cannot exceed 1 for any edge $(u, v)$ in $G$, the value 2 is impossible, regardless of whether the edge is in the BFS tree $T$.
Therefore, $d(u) - d(v)$ cannot be 2.

A Breadth-First Search (BFS) traversal explores a graph layer by layer, starting from a given source node. In an unweighted graph, BFS guarantees that the first time a node is discovered, it is reached via the shortest possible path from the source. The tree formed by the BFS traversal, known as the BFS tree, consists of edges that constitute these shortest paths. Therefore, the BFS tree effectively represents the shortest paths from the source node W to all other reachable vertices in the graph.

The Bellman-Ford algorithm's time complexity is given by $O(|V| \cdot |E|)$, where $|V|$ is the number of vertices and $|E|$ is the number of edges.
For a complete graph with $n$ vertices, the number of vertices $|V| = n$.
The number of edges in a complete graph with $n$ vertices is given by $|E| = \frac{n(n-1)}{2}$.
Substituting these values into the time complexity formula:
$O(|V| \cdot |E|) = O(n \cdot \frac{n(n-1)}{2}) = O(n^3)$
Therefore, the time complexity for Bellman-Ford on a complete graph is $\Theta(n^3)$.

Dijkstra's algorithm finds the shortest path by iteratively selecting the unvisited vertex with the smallest known distance from the source. The path chosen is determined by the order in which vertices are finalized.

1. Initialization: Start at S with distance 0. All other vertices have infinite distance.
2. Iteration 1 (S): Update distances for neighbors: d(A)=4, d(B)=3, d(D)=7.
3. Iteration 2 (B): Select B (min distance=3). Update neighbors: d(C)=d(B)+2=5, d(D) remains 7 (3+4 is not shorter).
4. Iteration 3 (A): Select A (min distance=4). Update neighbors: d(C)=min(5, d(A)+1)=5.
5. Iteration 4 (C): Select C (min distance=5). Update neighbors: d(E)=d(C)+1=6.
6. Iteration 5 (E): Select E (min distance=6). Update neighbors: d(G)=d(E)+2=8, d(T)=d(E)+4=10.
7. Iteration 6 (D): Select D (min distance=7). Update neighbors: d(F)=d(D)+5=12, d(T)=min(10, d(D)+3)=10.
8. Iteration 7 (G): Select G (min distance=8). Update neighbors: d(F)=min(12, d(G)+5)=12.
9. Iteration 8 (T): Select T (min distance=10). Path to T is SACET.

To find the minimum path weight from vertex $1$ to vertex $2$ with at most $3$ edges, we examine paths of length $1$, $2$, and $3$:

1. 1-edge path: $1 \rightarrow 2$, with weight $W_{1,2} = 12$.
2. 2-edge paths: $1 \rightarrow 0 \rightarrow 2$ has weight $W_{1,0} + W_{0,2} = 1 + 8 = 9$.
3. 3-edge paths: The path $1 \rightarrow 0 \rightarrow 4 \rightarrow 2$ has weight $W_{1,0} + W_{0,4} + W_{4,2} = 1 + 4 + 3 = 8$. Other paths, such as $1 \rightarrow 3 \rightarrow 4 \rightarrow 2$ ($4 + 2 + 3 = 9$) or $1 \rightarrow 0 \rightarrow 3 \rightarrow 2$ ($1 + 1 + 7 = 9$), have higher weights.

Comparing these results, the minimum possible weight for a path from $1$ to $2$ with at most $3$ edges is $8$.

The Bellman-Ford algorithm works by iteratively relaxing edges.
P. Statement P is incorrect. Bellman-Ford detects a negative cycle only if it is reachable from the source node. If a negative cycle exists in the graph but is not reachable from the source, the algorithm will not detect it.
Q. Statement Q is correct. The algorithm runs for $V-1$ iterations to find shortest paths. A final $V$-th iteration is performed to check for negative cycles. If any edge can still be relaxed in the $V$-th iteration, it means there is a negative cycle reachable from the source, as path lengths would continue to decrease indefinitely.

Dijkstra's algorithm uses a greedy approach where a vertex $u$ is marked as visited once it is extracted with the smallest tentative distance. Although negative edge weights ($b \to e$ with weight $-3$, $c \to h$ with weight $-5$) are present, they do not violate the greedy property in this specific graph because no path through these edges can improve the distance of an already visited vertex. Tracing the algorithm: the shortest paths to $a$ ($0$), $b$ ($1$), $e$ ($-2$), $f$ ($0$), $c$ ($3$), $h$ ($-2$), $g$ ($3$), and $d$ ($6$) are correctly determined in the order of extraction. Since no negative edge creates a shortcut to a previously visited node, the computed distances are optimal for all vertices.

In an unweighted graph, the shortest path between two nodes is defined by the minimum number of edges.
Breadth-First Search (BFS) inherently explores the graph level by level, guaranteeing that it finds the path with the fewest edges from the starting node $S$ to every other reachable node.
The time complexity of BFS is $O(V+E)$, where $V$ is the number of vertices and $E$ is the number of edges, which is optimal for traversing the graph.
Dijkstra's algorithm, while general for weighted graphs, has a higher typical complexity ($O(E \log V)$ or $O(E+V \log V)$ with a priority queue) than BFS for unweighted graphs. Warshall's algorithm computes all-pairs shortest paths in $O(V^3)$, which is inefficient for single-source. DFS does not guarantee shortest paths.

Let $d(s, x)$ denote the shortest path distance from source $s$ to vertex $x$. By the triangle inequality property inherent to shortest paths, for any edge $(u, v)$ in the graph, the shortest path to $v$ must satisfy $d(s, v) \leq d(s, u) + w(u, v)$. Given the values $d(s, u) = 53$ and $d(s, v) = 65$, we substitute them into the inequality: $65 \leq 53 + w(u, v)$. Solving for the edge weight, we get $w(u, v) \geq 65 - 53$, which simplifies to $w(u, v) \geq 12$. Therefore, the weight of the edge $(u, v)$ must be at least $12$.

Dijkstra's algorithm is a fundamental shortest-path algorithm used in link-state routing protocols like OSPF to determine the most efficient paths through a network. Routers utilize the collected Link State Database (LSDB) to model the network topology as a weighted graph $G = (V, E)$, where $V$ represents nodes (routers) and $E$ represents links with associated costs. By executing the algorithm, the router calculates the minimum cost path from itself to all other destinations in the network. These computed shortest paths are then installed into the router's routing table to facilitate optimal packet forwarding. Thus, the algorithm's primary role is to derive the entries for the routing tables.

In an unweighted graph, all edges have equal weight, allowing Breadth-First Search (BFS) to identify the shortest path effectively. BFS traverses nodes level by level, ensuring that the first time a node is reached, the shortest distance has been found. This process relies on a Queue to maintain a First-In-First-Out (FIFO) order, allowing enqueue and dequeue operations in $O(1)$ time. Consequently, the entire algorithm achieves a linear time complexity of $O(V + E)$, where $V$ is the number of vertices and $E$ is the number of edges. This is significantly more efficient than the $O((V + E) \log V)$ complexity incurred by using a Heap for weighted graphs.