Dijkstra and the simple version (P1)
Hello guys, today I was introduced the Graph Theory by my head teacher and it was something just similar to the map that reminded something that I believed that every student would have experienced: finding the shortest route to school.
Well this may be a simple problem as the combinations are still limited. But what if there are maybe 10, or 20, or even 50 stops. The total number of combinations may reach thousands. This might require some special algorithm so today what I want to share with you is the Dijkstra Algorithm which may help a lot in optimization problem (find the shortest route to some place🙂):
So the Dijkstra algorithm gives a procedure to get a optimal output:
Imagine there is one way to school and there is a stop “X” between your home and your school:
HOME —> X —> School
From Home to X takes 1 minutes and from X to school takes 5 minutes. Starting from your home, there is only one direct way to X and it takes 1 minute so we will write 1 on top of X. On the other hand, there is no direct way to school so we can mark “infinity” there. Next, we will calculate whether from that stop there is other shortest path to other points. In this example it takes 5 minutes from X to school so we can mark 6 on school. 6 is the shortest path from home to school. The algorithm, therefore, can be:
If d(X) + d(X,School)< d(School):
d(School)=d(X)+d(X,School)
​
As you can see, the reason we may mark infinity is because it is larger than any sums.