Project 4: Shortest Paths
The city has setup a radio station to broadcast the current traffic
situation to all the cars moving in the city. So the cars now intelligently
choose the shortest path to their destination by considering the current
traffic situation.
At each station, the car decides it's next hop based on it's current
shortest path
to the destination. The shortest path is computed by taking into account the
current traffic situation.
At any instant, if cars are getting off the road (leaving an edge) and getting
on the road at the same time, use the following ordering:
- All cars first get off the road.
- Then, shortest paths get computed.
-
- Then cars start getting on to the road.
This means that if two cars are starting on an edge simultaneously, they
will not count as traffic for each other while computing the shortest path.
But, one will count as traffic for the other (car with smaller ID number
will count as traffic for the car with the larger ID number) while computing
the time spent on the road.
Everything else is the same as that in Project 3. In the input, you will now
no longer be given the next-hop matrix.
Support files:
- Sample input
- Sample output (does not correspond to sample input, just tells you the syntax).
- Another sample input