*algorithm material*

You are traveling with a rented car and you are given a map modelled by a weighted graph with nodes and edges, 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 faster 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 C and D when you are allowed to switch car once?

The problem can be solved using Dijkstras algorithm,

PROVIDED you model the problem appropriately. So, explain how to modify the graph to capture the problems constraints and directly use Dijkstras algorithm.

The more elegant your solution, the more points you will get. Notice that you are NOT allowed to modify Dijkstras algorithm in any way.

a) (5 pts) Explain how to solve the problem using Dijkstras algorithm many times. What is the running time in this case?

b) (10 pts) Show how to solve the problem using Dijkstras 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 2n nodes and appropriate edges...

c) (5 pts) Show your construction in part (b) for the example graph.

5 Problem 1 (20 points) You are traveling with a rented car and you are given a map modelled by a weighted graph with n nodes and m edges. E 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 faster 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 C 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 modify 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 2n nodes and appropriate edges... c) (5 pts) Show your construction in part (b) for the example graph