## 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...