|
Project Information
|
Algoritmo que percorre um grafo e encontra o menor caminho entre o vértice raíz e o vértice anti-raíz. Como saída, o programa informa o caminho e o custo associado. Requisitos para execução: Java SE Runtime Environment 7 (JRE) Informações para download: http://www.oracle.com/technetwork/java/javase/downloads/index.html Execução (exemplo): $ java -jar dijkstra.jar /tmp/grafo.txt Onde o argumento deverá ser o nome do arquivo texto com as informações do grafo, incluindo o caminho de diretórios completo onde se encontra o arquivo. Critérios de aceitação do programa: - O grafo deve ser lido de um arquivo texto. O arquivo conterá, na sua primeira linha, o número de vértices que o grafo contém. Na sequência, cada linha corresponde a um arco ligando dois vértices: este arco é informado com três valores inteiros, significando, respectivamente, o vértice origem do arco, o vértice destino e o custo associado.
- O grafo pode não ter um vértice raíz, mas vértices base: neste caso o programa deve encontrar os vértices base e criar um vértice raíz com arestas dirigidas aos vértices originais com custo 0 (zero).
- O grafo pode não ter um vértice anti-raíz, mas vértices anti-base: neste caso o programa deve encontrar os vértices anti-base e criar um vértice anti-raíz com arestas dirigidas partindo dos vértices originais com custo 0 (zero).
- Exemplo com vértices raíz (1) e anti-raíz (14)
14
1 2 4
1 3 4
2 4 3
2 5 2
3 6 6
3 7 1
4 5 1
4 10 3
5 8 0
6 8 2
7 6 2
7 10 1
7 9 4
8 11 5
8 12 2
9 11 2
9 12 1
10 14 3
11 13 1
12 13 2
13 14 4
- Exemplo com vértices base (1, 2 e 3) e anti-base (7 e 9)
9
1 4 3
2 4 4
3 6 2
4 7 3
4 6 2
4 5 0
5 8 4
6 7 2
6 8 1
8 9 2
|