Assignment 3 (July 3)
Completion requirements
Opened: Wednesday, 7 November 2018, 12:00 AM
Due: Wednesday, 3 July 2019, 11:59 PM
Model the shortest path problem like given in the lecture with the difference that A and B are not vertices in the graph but arbitrary points on some edge of the graph. (Like routing from address A to address B, where A and B are typically not on a crossing of two streets but they are somewhere on some street segment.)
It is not allowed to add new vertices to the graph, rather modify the definition of the cost function appropriately. Also think about how the A and B need to be given.
How about a solution for this modified shortest path problem? Try to come up with some algorithm based on the known algorithm by Dijkstra.