Given a directed graph with positive edge lengths and two distinct vertices u and v in the graph, the “all-pairs uv-constrained shortest path problem” is the problem of computing for each pair of vertices i and j the length of the shortest path from i to j that goes through the vertex u or through the vertex v. If no such path exists, the answer is ∞. Describe an algorithm that takes a graph G = (V, E) and vertices u and v as input parameters and computes values L(i, j) that represent the length of uv-constrained shortest path from i to j for all 1 ≤ i, j ≤ |V|, i ! = u, j ! = u, i != v, j ! = v. Provide clear pseudocode solution. Prove your algorithm correct. Your algorithm must have running time in O(|V| ^2).
Given a directed graph with positive edge lengths and two distinct vertices u
and v in the graph, the “all-pairs uv-constrained shortest path problem” is the problem
of computing for each pair of vertices i and j the length of the shortest path from i to
j that goes through the vertex u or through the vertex v. If no such path exists, the
answer is ∞. Describe an
input parameters and computes values L(i, j) that represent the length of uv-constrained
shortest path from i to j for all 1 ≤ i, j ≤ |V|, i ! = u, j ! = u, i != v, j ! = v. Provide clear
pseudocode solution. Prove your algorithm correct. Your algorithm must have running
time in O(|V| ^2).

Trending now
This is a popular solution!
Step by step
Solved in 3 steps









