Dijkstra's Algorithm

Dijkstra's algorithm can be used in weighted graphs to compute the shortest distance from a vertex to all other vertices in the graph.

Suppose our vertices are $v_1,\dots,v_n$. Suppose we want to calculate the shortest distances from $v_1$ to all others. We will keep track of a set $S$ of solved vertices for those which we know the shortest distance. We will call this shortest distance $d(v)$ for any $v\in S$ once we calculate it.

Initially let $S$ just contain $v_1$, and $d(v_1)=0$. Now we iteratively add elements to $S$, until we can no longer, by the following step:

For each vertex $u\in S$, find its neighbor $v\not\in S$ with the minimum weight $w$. Among all $u\in S$, we add the one that minimizes $d(u)+w$ to $S$, and its distance is $d(u)+w$.

This is a complicated algorithm, so be sure to visit this interactive demonstration.