How it works...

Dijkstra's algorithm works in a similar way to BFS, but considers non-negative edge costs in order to build the best route from the source vertex to every other vertex. That's why we have an array for storing what the previous vertex is.