O objetivo deste projeto é apresentar 4 dos algoritmos estudados na disciplina Teoria dos Grafos,
do curso Ciência da Computação pela Universidade Federal de Alagoas.
Cada pasta de cada algoritmo contém:
1. arquivo.cpp - código fonte escrito em C++;
2. exemplo_de_grafo.dat - exemplo de entrada em que na primeira linha se encontram, respectivamente, o número de vértices, o número de arestas e o vértice inicial (apenas para os algoritmos que exigem essa informação, como Dijkstra). As demais linhas apresentam as ligações existentes entre cada par de vértices e seus respectivos pesos, dispostos em três "colunas" de valores. Exemplo:
6 10 0
0 1 5
0 2 6
0 3 4
1 2 1
1 3 2
2 3 2
2 4 5
2 5 3
3 5 4
4 5 4
O grafo acima contém 6 vértices, 10 arestas e vértice inicial 0 dada a primeira linha. As demais linhas representam as ligações entre u-v e seu respectivo peso.
Obs: A utilização dos vértices pelo programa se dá pelo intervalo numérico de 0 a N vértices, logo, deve-se adotar esse padrão em arquivos de input.
3. makefile - arquivo para execução rápida no terminal.
Para executar um programa no terminal, abra a pasta do algoritmo escolhido e digite o comando make para compilar e executar o código utilizando
o grafo contido na mesma pasta como input.
Para compilar sem executar com o grafo de exemplo, digite o comando make build. Assim, fica a cargo do usuário executar o programa com a liberdade
de inserir outro grafo como input.
Para remover o arquivo gerado pela compilação, digite o comando make clean.
Bellman Ford
O Algoritmo de Bellman-Ford é um algoritmo de busca de caminho mínimo em um digrafo (grafo orientado ou dirigido)
ponderado, ou seja, cujas arestas têm peso, inclusive negativo. O Algoritmo de Dijkstra resolve o mesmo problema,
num tempo menor, porém exige que todas as arestas tenham pesos positivos.
Fonte: Algoritmo de Bellman Ford
Dijkstra
É um dos algoritmos que calcula o caminho de custo mínimo entre vértices de um grafo.
Escolhido um vértice como raiz da busca, este algoritmo calcula o custo mínimo deste vértice para todos os demais vértices do grafo.
Ele é bastante simples e com um bom nível de performance.
Ele não garante, contudo, a exatidão da solução caso haja a presença de arcos com valores negativos.
Fonte: Algoritmo de Dijkstra
Kruskal
O algoritmo de Kruskal é um algoritmo em teoria dos grafos que busca uma árvore geradora mínima para um grafo
conexo com pesos. Isto significa que ele encontra um subconjunto das
arestas que forma uma árvore que inclui todos os vértices, onde o peso total, dado pela soma dos pesos das arestas da árvore, é minimizado.
Fonte: Algoritmo de Kruskal
Prim
Na ciência da computação o algoritmo de Prim é um algoritmo guloso (greedy algorithm)
empregado para encontrar uma árvore geradora mínima (minimal spanning tree) num grafo conectado, valorado e não direcionado.
Fonte: Algoritmo de Prim