(b) (13 points) Shortest paths through a vertex: You are given a strongly connec
ID: 3709301 • Letter: #
Question
(b) (13 points) Shortest paths through a vertex: You are given a strongly connected directed graph G-(V, E) with positive edge weights, along with a particular node vo E V. Give an efficient algorithm for finding shortest paths between all pairs of nodes in G, with the one restriction that these paths must all pass through vo- (Note technically the algorithm may return a walk, i.e. an edge may be occur once before and once after the vertex vo.) Noi e that listing all these pailu; 4xpliciily is expensive, both m i,(rins ofnu? inno aud storage, as there are O(n2) pairs of vertices (where n = VI). Thus instead you should output some structure with O(n) size such that given a query pair (s,t), where s,t EV, the structure can be used to output the shortest path from s to t which passes through vo, and do so in time proportional to the length of the path.Explanation / Answer
create a new vertex s for every vertex v
w(sv) ? 0
w(vs) ? ?
dist[s,·] ? Shimbel(V, E, w,s)
if Shimbel found a negative cycle fail gracefully for every edge (u, v) ? E w 0 (uv) ? dist[s, u] + w(uv) ? dist[s, v]
for every vertex u
dist[u,·] ? Dijkstra(V, E, w 0 , u)
for every vertex v dist[u, v] ? dist[u, v] ? dist[s, u] + dist[s, v]
Algo through Dynamic Programming :-
DynamicProgramming
APSP(V, E, w): for all vertices u for all vertices v if u = v dist[u, v, 0] ? 0 else dist[u, v, 0] ? ? for k ? 1 to V ? 1 for all vertices u dist[u, u, k] ? 0 for all vertices v 6= u dist[u, v, k] ? ? for all edges xv if dist[u, v, k] > dist[u, x, k ? 1] + w(xv) dist[u, v, k] ? dist[u, x, k ? 1] + w(xv)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.