MO417 - Questão para a prova oral

Número: 2010-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. Construa 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)|, onde |P(s,v)| é o número de arestas do caminho P(s,v).

Sobre este algoritmo, é possível afirmar que:

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, o valor δ (s,v) é o peso de um caminho mínimo entre s e v.
4. Se o grafo G possui ciclos negativos, G' também terá ciclos negativos.
5. NDA

Ideia original de: Daniel Cason