Dijkstra's Algorithm is a method used to find the shortest path between two points in a graph, where the edges have non-negative weights. It starts by setting the distance to the starting point as 0 and the distances to all other points as infinity. Then, it repeatedly selects the point with the smallest known distance, updates the distances to its neighboring points, and marks it as "visited." This process continues until the algorithm has found the shortest path to every point. Dijkstra’s Algorithm is widely used in navigation systems, like GPS, and for network routing.
Set(s) = 0, t(x) = ∞ for x ≠ s and S = ∅.
while there exists an x ∈ V \ S with t(x) ≠ ∞:
pick u ∈ V \ S with minimum t, add u to S
for all z ∈ N(u) \ S:
t(z) = min(t(z), t(u) + w(uz))
return t