Q$4$

Driving Directions

Assume you want to build your own driving directions application benefiting from Google Roads Updates services. Your application will not ask the user to select among routes and will always select the shortest route possible.

Assume we have a map of locations and roads that connect them. Roads are two$-$way roads but you cannot turn in the middle of the road. Every road has a distance measured in km$.$ Also, Google Roads updates service provides information related to the traffic on each road and the driving speed on that road at the time of the update. Updates from Google come periodically with a timestamp and include the new status of roads related to your area.

Your goal is to use the driving directions that will get you the shortest time possible according to the received updates.

Example:

Consider the following locations.

Assume you want to travel from location $0$ to location $4.$

Also, assume that the initial speeds are

For the sake of simplicity, assume the speed numbers represent the speed for both directions for each road.

The goal is to get from source to destination as soon as possible.

Assume that your application receives the following updates from the journey start:

Update $1$ at Minute $1$:

road $0-2$ new speed is $30$ km$/$hour

Update $2$ at Minute $2$:

road $2-1$ new speed is $3$ km$/$hour

what is the soonest to arrive at the destination? and which route is used?

Answer:

The goal is to get from source to destination as soon as possible.

There are several routes:

$0-2-1-4$

$0-3-5-4$

$0-3-2-1-4$

$0-2-3-5-4$

According to the initial speeds given, here is how much time each route takes $($if the speed does not change$)$:

For $0-2-1-4,$ the time will be $2+4+4=10$ minutes

For $0-3-5-4,$ the time will be $5+4+6=15$ minutes

For $0-3-2-1-4,$ the time will be $5+10+4+4=23$ minutes

For $0-2-3-5-4,$ the time will be $2+10+4+6=22$ minutes

Accordingly, your application should select the first route and start.

After you start driving, upgrades start arriving from Google service:

The first update at Minute $1$:

road $0-2$ new speed is $30$ km$/$hour

road $0-2$ was supposed to take $2$ minutes according to the previous speed, but now at minute $1,$ the road speed changed from $60$ to $30.$

At minute $1,$ the car already crossed $1$ km of distance from road $0-2.$ What is left is $1$ km but it will use the new speed, $30$ km$/$hour will take $2$ minutes to complete the road. $($so the total number of minutes to get from $0$ to $2$ is $1+2=3$ minutes

The second update at Minute $2$:

road $2-1$ new speed is $3$ km$/$hour

When the car arrives at location $2,$ it will recalculate the shortest path according to received updates.

road $2-1$ new speed is $3$ km$/$hour means that road $2-1$ will take $40$ minutes. $($ this is how to calculate time$=$ distance $/$speed $=2/3$ hours $=40$ minutes$)$

Since our final destination is $4,$ and we are at location $2$ now, from $2$ to $4,$ route $2-1-4$ is no longer the best $(40+4=44$ minutes$)$

route $2-3-5-4$ will be more efficient $(10+4+6=20$ minutes$)$

Assume no more updates during the trip,

The shortest time is $23$ minutes by going through the path $0-2-3-5-4.$

Write the implementation of DrivingDirections function which takes as input the following

The number of locations

The number of connections connecting them,

Four arrays, two integer arrays to indicate the from and to for each connection, a double array indicates the distance of each road, and a double array indicates the initial speed on each road.

The number of updates

An array of update objects, where each update contains minute, from, to$,$ and new speed

source and destination

Output:

Shortest time

Route used#include

#include

#include

#include

#include $//$ Include for DBL$\_$MAX

#include "GoogleUpdate.h$"$

using namespace std;

void updateSpeed$($vector$>$& updatedSpeed, int from, int to$,$ double newSpeed$)\{$

updatedSpeed$[$from$][$to$]=$ newSpeed;

updatedSpeed$[$to$][$from$]=$ newSpeed;

$\}$

void Dijkstra$($int source, vector$>>$& graph, vector& initialSpeed,

vector$>$& updatedSpeed, vector& path, vector& time$)\{$

int n $=$ graph.size$()$;

priority$\_$queue, vector$>,$ greater$>>$ pq;

vector visited$($n$,$ false$)$;

pq$.$push$(\{0\mathrm{.}0,$ source$\})$;

time$[$source$]=0\mathrm{.}0$;

while $(!$pq$.$empty$())\{$

int u $=$ pq$.$top$().$second;

pq$.$pop$()$;

if $($visited$[$u$])$ continue;

visited$[$u$]=$ true;

for $($auto& neighbor : graph$[$u$])\{$

int v $=$ neighbor.first;

double roadDistance $=$ neighbor.second;

double currentSpeed $=($updatedSpeed$[$u$][$v$]!=-1)?$ updatedSpeed$[$u$][$v$]$ : initialSpeed$[$u$]$;