Dijkstra's Algorithm

We want to get the shortest path starting from $s$ to other nodes.

Let $S$ be the explored nodes. For $u \in S$, $d[u] =$ length of a shortest path from $s$ to $u$.

For $x \notin S$, $d(x) = \min_{(r,x):r \in S}{d[r] + l(r,x)}$.

It requires no negative values of vertex.

Running time is $O(mn)$. Can be improved to $O(m\log n)$ via priority queue.

Cannot handle the graph with negative cycle.