This course immerses the learner into the design of systems and makes them ready for any new design problems.

sys-design.tar.gz

basic

This course provides an alternate perspective to system design where we learn about building blocs first and then use them to build bigger, more capable systems.

Copy-System Design-The Missing Pieces

# 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 for each vertex that costs much. Also, It explores all possible paths to find the shortest path that makes query time much slower, and query time increases with the size of the graph. So, this is not efficient for large road networks with continuously changing weights on the edges due to factors like traffic jams.

> We have to decide whether to find the **shortest path** or the **optimal path**. 

The traditional Dijkstra performs a guided search to find the shortest path that is actually the shortest. But It comes with the cost of an increased query time.

We have to set a limit on the query time because we wouldn't want the user to wait long to get the results. So, we will go with finding the *optimal path* that is a good path within the given cost. 

**A*** is an extension of the Dijkstra algorithm that uses heuristics to guide its search. Instead of finding the shortest path, A* finds the optimal path that is calculated by minimizing the following function.

$f(n)=g(n)+h(n)$

where $n$ is the next node on the path, $g(n)$ is the cost of the path from the start node to $n$, and $h(n)$ is a heuristic function that estimates the cost of the cheapest path from $n$ to the goal.

In literature, there are some algorithms that are specifically designed for road networks that focus on achieving less query time. These algorithms are [A*](https://arxiv.org/pdf/1603.01607.pdf), [Arc flags](http://www.diag.uniroma1.it/challenge9/papers/kohler.pdf), [Contraction hierarchies](https://en.wikipedia.org/wiki/Contraction_hierarchies), [Transit node routing](https://www.researchgate.net/publication/6366597_Fast_Routing_in_Road_Networks_with_Transit_Nodes), [Reach-based routing](https://archive.siam.org/meetings/alenex04/abstacts/rgutman1.pdf), and [Hub labeling](https://www.microsoft.com/en-us/research/wp-content/uploads/2010/12/HL-TR.pdf).

We can use any of the above algorithms to find the shortest path based on our requirements. 

Now that we have modeled the large road network with a graph and we have good algorithms to find the optimal path between two points, it's good to ask the following question. 

❓ Is it wise to model the whole world road network with a single large graph?



Coping with the Challenges

Graph for modeling the road network