Question

Given a directed graph with positive edge lengths and a specified vertex v in the graph, the "all-pairs" v-constrained shortest path problem" is the problem of computing for each pair of vertices i and j the shortest path from i to j that goes through the vertex v. If no such path exists, the answer is $\infty$ . Describe an algorithm that takes a graph G= (V; E) and vertex v as input parameters and computes values L(i; j) that represent the length of v-constrained shortest path from i to j for all $1 \leq i, j\leq |V|, i\neq v, j\neq v$ . Prove your algorithm correct. Your algorithm should have a running time in $O(|V|^2)$

Answer 1

plzzzzzzzzz Upvote...

Algorithm is very simple, we have to find the shortest path from all the vertex to vertex v and then shortest path from vertex v to every other vertex. So then in order to get shortest path from say v1 to v2, we will use shortest path from v1 to v and then combine shortest path from v to v2 to get the entire path.

Below is the algorithm we follow:-

1. In order to get shortest path from vertex v to every other vertices, perform the Dijkstra algorithm with vertex v as the source vertex.

2. In order to get shortest path from every vertex to vertex v, reverse the direction of all the edges in the graph G to make it graph G'

3. Now compute shortest path from vertex v to every vertex in graph G' such that by reversing all the edges in shortest path tree, we will get the shortest path from every vertex to vertex v in the original graph.

4. Thus shortest path from v1 to v2 i.e. L(v1,v2) = L(v1,v) + L(v,v2).

5. Return

So in the above algorithm we run Dijkstra algorithm 2 times which run in O(E log V) and we modify the edges of the graph in O(E) time, and then finally computed shortest path between every pair of vertex in O(|V|²) time.

So total complexity = O(|V|²)

Please comment for any clarification.