Implementação em C++ dos algoritmos de Dijkstra, Kruskal, Prim, Kosaraju e Bellman-Ford para resolução dos problemas da árvore geradora mínima, caminho mínimo e componentes fortemente conexas.
Para compilar, é necessário executar o comando make
na pasta do algoritmo escolhido.
A pasta Bat1
contém uma bateria de testes para cada problema, incluindo as instâncias, o gabarito e o script de execução Bat1.sh
. As instâncias do algoritmo de Bellman-Ford podem ser encontradas em Bat1/instances_bm
, e seu respectivo gabarito em Bat1/answer_bm
. O script de bateria de testes do algoritmo de Bellman-Ford pode ser encontrado em Bat1/BatBm.sh
As instâncias escolhidas para execução devem ser indexadas a partir do 1. Se a flag -i
não for utilizada no momento de execução do binário, o vértice inicial padrão escolhido será 1. Caso a entrada do algoritmo de Bellman-Ford seja um digrafo, é necessário que o número de arestas seja acompanhado de um número negativo, para identificação.
A entrada segue o formato:
- Na primeira linha é dado o número de vértices e de arestas. Se o grafo é direcionado, o número de arestas deve ser enviado como negativo.
- As próximas linhas correspondem às arestas do grafo. Cada linha contém três inteiros u, v e w, onde w corresponde ao peso da aresta entre u e v.
- As instâncias do Korasaju são grafos não ponderados, logo as linhas de entrada contém apenas os inteiros u e v.
Soluciona o problema do caminho mínimo.
Execução:
./dijkstra.bin {opções}
Opções de flag:
- -h : mostra o help
- -o : redireciona a saída para o
- -f : indica o "arquivo" que contém o grafo de entrada
- -i: vértice inicial
Soluciona o problema da árvore geradora mínima.
Execução:
./kruskal.bin {opções}
Opções de flag:
- -h : mostra o help
- -o : redireciona a saída para o
- -f : indica o "arquivo" que contém o grafo de entrada
- -s: mostra as arestas que compõem a solução
Soluciona o problema da árvore geradora mínima.
Execução:
./prim.bin {opções}
Opções de flag:
- -h : mostra o help
- -o : redireciona a saída para o
- -f : indica o "arquivo" que contém o grafo de entrada
- -i: vértice inicial
- -s: mostra as arestas que compõem a solução
Calcula as componentes fortemente conexas de um grafo.
Execução:
./kosaraju.bin {opções}
Opções de flag:
- -h : mostra o help
- -o : redireciona a saída para o
- -f : indica o "arquivo" que contém o grafo de entrada
Soluciona o problema do caminho mínimo.
Execução:
./bellman_ford.bin {opções}
Opções de flag:
- -h : mostra o help
- -o : redireciona a saída para o
- -f : indica o "arquivo" que contém o grafo de entrada
- -i: vértice inicial