MO417 - Questão para a prova oral

Número: 080

Enunciado:

Seja G = (V, E, ω), um grafo orientado ponderado, onde ω é uma função que associa um peso a cada aresta do grafo. Considere o seguinte algoritmo para determinar caminhos mínimos de fonte única s em G:

1. Defina G' = (V, E, ω'), onde ω' (uv) = ω (uv) + |min(0,W)| para toda aresta uv de E, sendo W = min_{uv ∈ E} ω (uv).
2. Rode o algoritmo de Dijkstra para caminhos mínimos de fonte única em G' com origem s, obtendo caminhos mínimos P' (s,u) e distâncias δ' (s,v) para todo v ∈ V.
3. Retorne δ (s,v) = δ' (s,v) - |P(s,v)|.|min(0,W)|.

1. A complexidade do algoritmo acima é O(|V|.|E|).
2. Cada caminho P(s,v) é um caminho entre s e v em G com custo δ (s,v), porém este caminho poderá não ser mínimo, mesmo que G não possua ciclos negativos.
3. Para qualquer grafo G, δ (s,v) é o peso de um caminho entre s e v com peso mínimo.
4. Se o grafo G possui ciclos negativos, G' também terá ciclos negativos.
5. NDA

Autor(a): Daniel Cason