Dijkstra

For shortest walk in weighted DAG.

Pseudo-code

Runtime

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

or worst cases(dense graph) and