Bellman-Ford

Find the shortest walk with negative weighted edges, but not cycle.

Pseudo-code

\begin{algorithm}
\caption{BellmanFord}
\begin{algorithmic}
	\Procedure{BellmanFord}{$s$}
		\For{$i \gets 1$ \To $V - 1$}
			\ForAll{edge $u \to v$}
				\If{$u \to v$ is tense}
					\State \Call{relax}{$u \to v$}
                \EndIf
            \EndFor
        \EndFor
        \State \\
        \ForAll{edge $u \to v$}
	        \If{$u \to v$ is tense}
		        \State Fail \Comment{Negative cycle detected}
            \EndIf
        \EndFor
    \EndProcedure
\end{algorithmic}
\end{algorithm}

Runtime

$$O(|V||E|)$$