Dijkstra

For shortest walk in weighted DAG.

Pseudo-code

\begin{algorithm}
\caption{Dijkstra}
\begin{algorithmic}
	\Function{Dijkstra}{$s$}
		\ForAll{vertices $v \in V$}
			\State $v.dist \gets \infty$
        \EndFor
		\State $q \gets$ priorityQueue($\emptyset$)
		\State $q.$\Call{Insert}{$s, 0$}
		\While{$q$ is not empty}
			\State $u \gets$ \Call{ExtractMin}{$q$} \Comment{$O(\log V)$}
			\ForAll{edges $u \to v$}
				\If{$u \to v$ is tense}
					\State \Call{Relax}{$u \to v$} \Comment{update $v.dist$}
					\If{$v \in q$}
						\State $q.$\Call{DecreaseKey}{$v, v.dist$} \Comment{$O(\log V)$ or $O(1)$ if use Fibonacci heap}
					\Else
						\State $q.$\Call{Insert}{$v, v.dist$}
                    \EndIf
                \EndIf
            \EndFor
        \EndWhile
    \EndFunction
\end{algorithmic}
\end{algorithm}

Runtime

$$O((V+E)\log V)$$

then if we use Fibonacci heap instead of binary heap in queue, it will be

$$O(V+E\log V)$$

or worst cases(dense graph) $O(V^2\log V)$ / $O(V^2)$