Dijkstra's algorithm finds the shortest path from a source vertex to all others in a graph with non-negative edge weights. It maintains a tentative distance for each vertex and repeatedly settles the unsettled vertex with the smallest tentative distance, then relaxes its edges.
Dijkstra repeatedly relaxes the closest unvisited vertexThe correctness relies on the greedy property: once a vertex is settled, no shorter path can be found later, because all remaining paths pass through vertices that are at least as far away. The priority queue gives an O((V + E) log V) implementation.