8. (10 pts, not hard at all after the hint) Let G be a directed graph where each edge has distance 1. Let vo be a design
Posted: Thu May 05, 2022 12:46 pm
- 8 10 Pts Not Hard At All After The Hint Let G Be A Directed Graph Where Each Edge Has Distance 1 Let Vo Be A Design 1 (101.86 KiB) Viewed 38 times
8. (10 pts, not hard at all after the hint) Let G be a directed graph where each edge has distance 1. Let vo be a designated node in G (G has many other nodes). I would like to find a shortest walk a (assuming that it exists) from vo back to vo in G such that the walk passes at least one other node in between. Notice that if you run the classic Dijkstra's shortest path algorithm on G starting from vo, it will not return such an a. Please design an efficient algorithm to find such an a by running Dijkstra's shortest path algorithm exactly once. (Hint: my way is to modify, in certain way, G with n nodes into a new graph G' with n+1 nodes and run Dijkstra's shortest path algorithm on G' only once.)