Tendo como entrada um grafo acíclico dirigido ponderado G =...

aplicando a busca em largura em G, o caminho mínimo de origem única é calculado em tempo θ(V² ).

aplicando a busca em largura no grafo transposto G^T = (V, E^T ), o caminho mínimo de origem única é calculado em tempo θ(V² ).

relaxando as arestas de G de acordo com a ordenação topológica de seus vértices, o caminho mínimo de origem única é calculado em tempo θ(V + E).

aplicando a busca em profundidade no grafo transposto G^T = (V, E^T ), o caminho mínimo de origem única é calculado em tempo θ(V + E).

relaxando as arestas pela busca em profundidade no grafo de entrada G = (V, E) e, posteriormente, aplicando a busca em profundidade no grafo transposto G^T = (V, E^T ), o caminho mínimo de origem única é calculado em tempo θ(V² ).