Class AcyclicSP

java.lang.Object

AcyclicSP

public class AcyclicSP
extends java.lang.Object

Esta classe implementa um ADT para resolver o problema dos caminhos de peso mínimo em um dag (digrafo acíclico) com pesos nos arcos. Todos os caminhos começam num dado vértice s. (O sufixo "SP" é uma abreviatura de Shortest Path.) Os pesos dos arcos são números reais arbitrários (positivos, negativos ou nulos).

Esta implementação usa um algoritmo de ordenação topológica para realizar a tarefa. O construtor consome tempo proporcional a V + E, sendo V o número de vértices e E o número de arcos do digrafo. Depois, os métodos distTo() e hasPathTo() consomem tempo constante e o método pathTo() consome tempo proporcional ao número de acos do caminho devolvido.

(Esta implementação depende das classes EdgeWeightedDigraph.java, DirectedEdge.java, Topological.java.)

Documentação adicional: veja Section 4.4 do livro Algorithms, 4th Edition, de Robert Sedgewick e Kevin Wayne.

Constructor Summary

Constructors

Constructor and Description
AcyclicSP(EdgeWeightedDigraph G, int s) Apartir da raiz s, calcula uma arborescência de caminhos de peso mínimo no dag G.

Method Summary

Methods

Modifier and Type	Method and Description
double	distTo(int v) Devolve o comprimento de um caminho de peso mínimo do vértice s ao vértice v.
boolean	hasPathTo(int v) Existe caminho do vértice s ao vértice v?
static void	main(java.lang.String[] args) Teste de unidade.
java.lang.Iterable<DirectedEdge>	pathTo(int v) Devolve a sequência de vértices de um caminho de peso mínimo do vértice s ao vértice v.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

AcyclicSP

public AcyclicSP(EdgeWeightedDigraph G,
         int s)

Apartir da raiz s, calcula uma arborescência de caminhos de peso mínimo no dag G. (Para cada vértice v, essa arborescência contém um caminho de peso mínimo de s a v.)

Throws:

java.lang.IllegalArgumentException - se o digrafo G não for um dag.

java.lang.IllegalArgumentException - se s não for um vértice válido ou seja, se não estiver em 0..V-1.

Method Detail

distTo

public double distTo(int v)

Devolve o comprimento de um caminho de peso mínimo do vértice s ao vértice v. Devolve +infinito se não existe caminho de s a v.

hasPathTo

public boolean hasPathTo(int v)

Existe caminho do vértice s ao vértice v?

pathTo

public java.lang.Iterable<DirectedEdge> pathTo(int v)

Devolve a sequência de vértices de um caminho de peso mínimo do vértice s ao vértice v. O caminho é devolvido como um Iterable de arcos.

main

public static void main(java.lang.String[] args)

Teste de unidade. Testa o funcionamento da ADT AcyclicSP. Recebe na linha de comando um vértice s e o nome de arquivo que descreve um dag com pesos nos arcos (A primeira linha do arquivo é o número de vértices do dag; a segunda linha é o número de arcos do dag; cada uma das linhas seguintes tem um par v w de inteiros seguido de um número real p arbitrário, o que representa um arco v-w com peso p.) Para cada vértice v, calcula e imprime um caminho de peso mínimo de s a v. Como arquivo de entrada, você pode usar http://algs4.cs.princeton.edu/44sp/tinyEWDAG.txt.