Project ForgeConsider a graph with vertices a,b,c,d,e,h,f,g and edges a→b(1), a→d(2), b→c(2), c→d(3), b→e(-3), c→h(-5), d→a(2), d→g(2), h→e(1), h→g(2), g→f(3), f→e(2). Dijkstra's single source shortest path algorithm when run from vertex a in this graph computes the correct shortest path distance to
- Aonly vertex a
- Bonly vertices a, e, f, g, h
- Conly vertices a, b, c, d
- all the vertices
Explanation
Tracing standard Dijkstra from a: finalizes a=0, b=1, e=-2 (via b, -3), c=3, h=-2 (via c, -5), g=0 (via h), f=3 (via g), d=6 (via c). Independently computing TRUE shortest distances (allowing negative edges properly): a=0, b=1, c=3, d=6 (unaffected by negative edges downstream), e=min(-2 via b, -1 via h, 5 via f)=-2, h=-2, g=0, f=3 — identical to Dijkstra's results in every case. The negative edges here only lead into a subgraph with no path back to a/b/c/d, so despite their presence, Dijkstra happens to compute every vertex correctly.
Source: GATE CS 2008 (2008)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.