T06
Os DAG de interesse . Dado um inteiro positivo $k$, o programa Example.java abaixo gera um certo DAG $G_k$ com custos nas arestas. 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.
Pergunta 1. Como parecem crescer os tempos de execução dos três programas acima conforme aumentamos $k$?
Pergunta 2. 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 Perguntas 1 e 2 acima.
- 15 julho 2021, 16:27 PM
- 15 julho 2021, 16:27 PM