An optimal algorithm
to find the shortest path in the graph
Introduction:
Many
real-life solutions rely on shortest path algorithms, especially games rely on
them! If a graphic game character traces your moves along a complicated path
and finds you, then it is obvious that the game implemented a graph algorithm
to find the shortest path to approach you. Is it really that easy to find an
optimal path to reach a point in a graph? No not exactly, as the upper bound of
the Dijkstra’s algorithm is $O(|V|^2)$. If we assume your game
map to be a big grid, then the number of cells in the grid is equal to the
number $|V|$. But this is still the worst case, and for most times we don’t need
to consider the worst case. Let me describe the Dijkstra’s algorithm.
