question is complete

E You are traveling with a rented car and you are given a map modelled by a weighted graph with it nodes and medges. where the weights correspond to the time taken to travel between two cities. The edges are used to model ordinary roads and roads where you can change car and perhaps travel fuster along that road. Your goal is to reach your destination as fast as possible with one restriction. You can switch a car at most once. When you switch, the time to travel along that road (but not the rest) reduces to half. See the graph alongside for an example. What is the best path from A to nodes and D when you are allowed to switch car once? The problem can be solved using Dijkstra's algorithm, PROVIDED you model the problem appropriately. So, explain how to modify the graph to capture the problems constraints and directly use Dijkstra's algorithm. The more elegant your solution, the more points you will get Notice that you are NOT allowed to motif Dijkstra's algorithm in any way a) (5 pts) Explain how to solve the problem using Dijkstra's algorithm many times. What is the running time in this case? b) (10 pts) Show how to solve the problem using Dijkstra's algorithm only ONCE! What is the running time in this case? Give details about your construction and explain how the problem can be solved. Hint: You need to create a graph with 2 nodes and appropriate edges... c) (5 pts) Show your construction in part (b) for the example graph