Search This Blog

Simplicity is the ultimate sophistication.” — Leonardo da Vinci
Contact me: sreramk360@gmail.com

Monday 27 July 2015

An optimal algorithm for the shortest path in the graph


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. 

Featured post

Why increasing complexity is not good?

“ Simplicity is the ultimate sophistication.” — Leonardo da Vinci Why is complicating things wrong ? - K Sr...