1. EXERCÍCIO [Cormen 2a edição, 24.3-6]: Modifique o algoritmo de Dijkstra para calcular caminhos mínimos num grafo de arestas ponderadas por pesos inteiros de zero a W, e de forma a executar em tempo O(W*|V| + |E|).

=================================================================
-------------------- RESPOSTA DO EXERCÍCIO 1 --------------------

Considere o algoritmo abaixo:

=============================================================
Algoritmo: Dijkstra_modificado
Entrada: grafo direcionado G = (V,E), vértice "o", natural W.
Saída: dados "d" e "pai" para cada v \in V.
-------------------------------------------------------------
01. PARA cada v \in V
02.  | d[v] := infinito
03.  | pai[v] := nulo
04.  | noh[v] := nulo
05. tmax := W*(|V|-1)
06. PARA i de 0 a tmax
07. | L[i] := lista duplamente encadeada vazia
08. d[o] := 0
09. noh[o] := insira "o" em L[0]
10. PARA i de 0 a tmax
11. | ENQUANTO L[i] não estiver vazia
12. | | u := remova um vértice de L[i]
13. | | PARA cada v tal que (u,v) \in E
14. | | | SE d[v] > d[u] + w(u,v)
15. | | | | d[v] := d[u] + w(u,v)
16. | | | | pai[v] := u
17. | | | | SE noh[v] != nulo
18. | | | | | remova "v" da lista à qual noh[v] pertence
19. | | | | noh[v] := insira "v" em L[d[v]]
20. retorne "d" e "pai".
=============================================================

O algoritmo acima faz uso do fato de que, em qualquer grafo com a propriedade dada, o tamanho (ponderado) de um caminho mínimo a partir de "o" é no máximo "tmax". Assim sendo, ao invés de utilizar uma lista de prioridades, o algoritmo mantém, para cada "i" de 0 a "tmax", uma lista contendo os vértices ainda não visitados cujo valor d[v] vale "i".

O tempo total de execução das linhas do algoritmo é:
-------
- Linhas 01 a 04: O(n), sendo n = |V|.
- Linhas 05 a 07: O(tmax) = O(n*W).
- Linhas 08, 09 e 20: O(1).
- Linhas 10 e 11: O(tmax) = (n*W).
- Linha 12: O(n) (cada vértice é removido no máximo 1 vez).
- Linhas 13 a 19: O(m), sendo m = |E| (a vizinhança de saída de cada vértice é percorrida no máximo uma vez).
-------
Logo, o custo total do algoritmo é O(n*W + m), CQD.

-------------------- RESPOSTA DO EXERCÍCIO 1 --------------------
=================================================================