Algoritmos (Cheat Sheet)

Algoritmo	Complexidade
DFS*	$O(V + E)$
SCCs (algoritmo abordado)	$O(V+E)$
Dijkstra	$O((V+E)\log V)$
Bellman-Ford	$O(VE)$
Johnson (Bellman-Ford + $V$ aplicações de Dijkstra)	$O(VE + V(V + E)\log V) \in O(V(V + E)\log V)$
Prim	$O((V + E)\log V)$
Kruskal	$O(E\log V)$
Método* Ford Fulkerson	$O(\vert f^*\vert E)$
Edmonds-Karp	$\min(O(VE^2), O(\vert f^*\vert E))$ *
Push-Relabel	$O(V^2E)$
Relabel-to-Front	$O(V^3)$

* A DFS pode ser diretamente aplicada para encontrar uma ordenação topológica num dado grafo.
* Não é verdadeiramente um algoritmo - não indica como escolher o caminho.
* Edmonds-Karp corresponde a uma implementação do Método Ford-Fulkerson, preservando portanto a sua upper-bound: o majorante relevante será aqui o menor, claro.