Coping with the Challenges

Graph for modeling the road network

To model the roads all around the world, we can use the concept of graphs as we have a network of roads. We will be using directed graphs so as to provide a solution that works on one-way roads too.

Let’s assume endpoints of a road or road junctions as vertices and the road connecting those vertices as an edge.

The weight on edge(road) is the ETA that includes:

• Length of the road
• A measure of traffic jam
• Probability of a traffic accident
• A measure of weather condition
• A measure of road condition
• Speeds of different vehicle choices

In a road network graph, we have positive weights on the edges, and the graph is directed because we have to cover the one-way roads too.

Now that we have a large directed graph with positive weights, we have to find the path between two points.

Finding the path

There are a lot of algorithms to find the shortest path in a graph. The most common is the Dijkstra’s algorithm. Dijkstra finds the shortest path from a single source to all the destinations in $O(E + VlogV)$.

If we have to find all-pairs shortest paths we need to run Dijkstra ...