Dijkstra a little more complex version (part 2)
In the last part, we have discussed a simple version and how the Dijkstra algorithm worked. Let’s meet a more complex version (that can be pretty similar to your school route):
From X there are two direct routes (to R and to U), we can mark 1 on R and 5 on U. Other points can be marked “infinity”. From R there are 2 direct routes: to U and to T. U is already marked “5” and 1+7>5 so 5 is the best route to U. T is marked infinity, which is much larger than 1+12 so “13” is marked next to T.
From U there are 2 direct routes: to R and to T. To R is an easy one as we all can see 1 is the shortest route. However, the route to T only takes 5+7=12<13. So 13 is crossed and 12 is now marked. Similarly, the procedure continues to Y and we can calculate the shortest route without missing any vertices. And so, if |V|=n represents the number of vertices, the worst case scenario is n square tries.
