T12 Pesos negativos
Encontrar caminhos mínimos em grafos dirigidos com custos nos arcos torna-se mais difícil quando há arcos com custos negativos. Desde que não haja circuitos negativos, há soluções eficientes mesmo nesse caso: podemos, por exemplo, usar o algoritmo de Bellman-Ford. É um fato que podemos até usar o algoritmo de Dijkstra, desde que não haja circuitos negativos, mas o tempo de execução poderá ser grande (muito maior que \(O(E\log V)\), como garantido no caso de custos não-negativos). Este exercício ilustra esta característica do algoritmo de Dijkstra.
DAGs de interesse \(G_k\). Dado um inteiro não-negativo $k$, o programa Example.java abaixo gera um certo DAG $G_k$ com custos nos arcos. Experimente executar Example.java para alguns valores de $k$ e veja como é $G_k$ (veja também a figura G_k.png abaixo).
Note que $G_k$ tem $2k+1$ vértices. Estamos interessados em descobrir a distância de $2k$ a $0$ em $G_k$, executando os algoritmos de caminho mínimo que vimos.
Quatro programas. Os quatro programas Distance*.java podem ser executados para encontrar a distância de $2k$ a $0$ em $G_k$. Esses programas são baseados em três algoritmos: no algoritmo específico para DAGs (baseado em ordenação topológica), no Bellman-Ford e no Dijkstra.
Exemplos de execução
$ java-algs4 Example 10 | java-algs4 DistanceAcyclic
dist(20, 0) = -2046.0
$ java-algs4 Example 10 | java-algs4 DistanceBF
dist(20, 0) = -2046.0
$ java-algs4 Example 10 | java-algs4 DistanceDijkstra
Exception in thread "main" java.lang.IllegalArgumentException: edge 20->18 -512.00 has negative weight
at edu.princeton.cs.algs4.DijkstraSP.<init>(DijkstraSP.java:72)
at DistanceDijkstra.main(DistanceDijkstra.java:26)
$
O programa DistanceDijkstra usa DijkstraSP.java, mas este programa não permite instâncias com arcos com custo negativo. Assim, obtemos a mensagem de erro acima. Podemos entretanto remover o teste para arcos negativos em DijkstraSP.java. Faça isso (não é necessário fazer mais nada) e chame esse novo programa de DijkstraSP2.java. O programa DistanceDijkstra2.java usa DijkstraSP2.java:
$ java-algs4 Example 10 | java-algs4 DistanceDijkstra2
dist(20, 0) = -2046.0
$
Fato. DijkstraSP2.java determina corretamente caminhos mínimos em grafos dirigidos com pesos arbitrários nos arcos, desde que não haja circuitos negativos.
Observação. Provar o fato acima constitui um ótimo exercício (mas isso não está sendo cobrado aqui).
Experimentos. Execute os programas DistanceAcyclic.java, DistanceBF.java e DistanceDijkstra2.java nos grafos $G_k$ para valores maiores de $k$, e veja como crescem os tempos de execução.
Questão 1. Como parecem crescer os tempos de execução dos três programas acima conforme aumentamos $k$?
Questão 2. Suponha que, na execução de DistanceDijkstra2.java, imprimimos o valor de distTo[0] toda vez que ele muda. No caso do grafo $G_0$, isto ocorre exatamente uma vez (quando o valor de distTo[0] muda de $\infty$ para $0.0$). Seja $s_k$ a sequência impressa que obtemos para o grafo $G_k$. Temos assim que $s_0 = \texttt{0.0}$, $s_1 = \texttt{-1.0}\;\texttt{-2.0}$ e $s_2 = \texttt{-3.0}\;\texttt{-4.0}\;\texttt{-5.0}\;\texttt{-6.0}$. Diga como é $s_k$ para todo $k$ e justifique sua resposta (use indução em $k$).
Questão 3. Explique, de forma convincente :-), por que o tempo de execução de DistanceDijkstra2.java cresce como você observou.
Entrega. Neste exercício, você deve entregar sua resposta às Questões 1, 2 e 3 acima.
- 13 junho 2024, 17:54 PM
- 13 junho 2024, 17:54 PM