Suppose there is a strongly connected directed graph G = (V, E) with positive ed

Question

Suppose there is a strongly connected directed graph G = (V, E) with positive edge weights. It contains a specific edge eo E. Modifying Dijkstra's algorithm below, give an algorithm pseudocode for finding shortest paths between all pairs of nodes, with a restriction that all these paths must contain the edge eo. Your algorithm should at the most take O((|V | + |E|)log|V |) time.

Dijkstras Algorithm:-

procedure dijkstra(G, l, s)

Input: Graph G = (V, E), directed or undirected; positive edge lengths {le : e E}; vertex s V

Output: For all vertices u reachable from s, dist(u) is set to the distance from s to u.

for all u V :

dist(u) =

prev(u) = nil

dist(s) = 0

H = makequeue(V ) (using dist-values as keys)

while H is not empty:

u = deletemin(H)

for all edges (u, v) E:

if dist(v) > dist(u) + l(u, v):

dist(v) = dist(u) + l(u, v)

prev(v) = u

decreasekey(H, v)

Explanation / Answer

I need to modify Dijkstra's Algorithm to return the shortest path between a vertex S (source) and a vertex X (destination). I think I've figured out what to do, but I'd like some help. Here is the pseudocode I have modified.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.