tp1caminhosmnimos-101124103000-phpapp01

Prévia do material em texto

Universidade Federal de Ouro Preto
Instituto de Ciências Exatas e Biológicas
Departamento de Computação
TEORIA DOS GRAFOS
Primeiro Trabalho Prático
Caminhos Mínimos
Johnnatan Messias P. Afonso
Kayran dos Santos
Vítor Mangaravite
Professor - Haroldo Gambini Santos
Ouro Preto
25 de outubro de 2010
Sumário
1 Introdução 1
1.1 Considerações iniciais . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Especificações da máquina . . . . . . . . . . . . . . . . . . . . . . . . 1
1.3 Especificação do problema . . . . . . . . . . . . . . . . . . . . . . . . 1
1.3.1 Material a ser entregue . . . . . . . . . . . . . . . . . . . . . . 1
1.3.2 Documentação impressa incluindo . . . . . . . . . . . . . . . . 2
1.3.3 Regras de Implementação . . . . . . . . . . . . . . . . . . . . 2
1.3.4 Problemas Teste . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3.5 Formato de Entrada e Saída e Parâmetros . . . . . . . . . . . 3
1.4 Dijkstra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.4.1 Heaps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.4.2 Aplicação do Algoritmo . . . . . . . . . . . . . . . . . . . . . 5
1.4.3 Versão Preliminar x Final . . . . . . . . . . . . . . . . . . . . 5
1.5 Floyd-Warshall . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.5.1 Aplicação do Algoritmo . . . . . . . . . . . . . . . . . . . . . 6
1.5.2 Versão Preliminar x Final . . . . . . . . . . . . . . . . . . . . 6
2 Algoritmo e estruturas de dados 7
2.1 Grafo do Dijkstra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.1.1 Função CriaGrafoPorNome . . . . . . . . . . . . . . . . . . . . 7
2.1.2 Função ConstruindoLista . . . . . . . . . . . . . . . . . . . . . 8
2.1.3 Função AddInteração . . . . . . . . . . . . . . . . . . . . . . . 9
2.2 Heap Binária . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2.1 Inicialização da heap . . . . . . . . . . . . . . . . . . . . . . . 10
2.2.2 Remove menor . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2.3 Diminui . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2.4 Tamanho . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.3 Dijkstra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.3.1 Função Dijkstra . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.3.2 Função DijkstraP . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.3.3 Função Main para o Dijkstra . . . . . . . . . . . . . . . . . . . 14
2.4 Grafo do Floyd-Warshall . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.4.1 Função CriaGrafoPorNome . . . . . . . . . . . . . . . . . . . . 16
2.4.2 Função alocaMatriz . . . . . . . . . . . . . . . . . . . . . . . . 17
2.4.3 Função iniciaMatriz . . . . . . . . . . . . . . . . . . . . . . . . 19
2.4.4 Função iniciaPred . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.5 Floyd-Warshall . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.5.1 Função floydP . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.5.2 Função floyd . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.5.3 Função floydPNeg . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.5.4 Função floydNeg . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.5.5 Função imprimirsalvar . . . . . . . . . . . . . . . . . . . . . . 23
2.5.6 Função mainF . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2
3 Testes 27
3.1 Exemplo de teste para o Floyd-Warshall . . . . . . . . . . . . . . . . 27
3.1.1 Grafo com Peso Positivo . . . . . . . . . . . . . . . . . . . . . 27
3.1.2 Grafo com Peso Negativo . . . . . . . . . . . . . . . . . . . . . 29
3.2 Testes em massa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.2.1 Floyd-Warshall . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.2.2 Dijkstra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
4 Conclusão 36
Lista de Figuras
1 Figura Repres. Alocação Matriz . . . . . . . . . . . . . . . . . . . . . 18
2 Figura Grafo com Peso Positivos . . . . . . . . . . . . . . . . . . . . 27
3 Figura Matriz Dist . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
4 Figura Matriz Pred . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
5 Figura Exemplo de Caminho . . . . . . . . . . . . . . . . . . . . . . . 28
6 Figura Grafo com Peso Negativo . . . . . . . . . . . . . . . . . . . . . 29
7 Figura Matriz Dist . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
8 Figura Matriz Pred . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
9 Figura Exemplo de Caminho Neg . . . . . . . . . . . . . . . . . . . . 30
10 Grafico para Floyd-Warshall sobre o grafo rg300_768 . . . . . . . . . 31
11 Grafico para Floyd-Warshall sobre o grafo rg300_4730 . . . . . . . . 32
12 Grafico para Floyd-Warshall sobre o grafo comp-2007-2-22c . . . . . . 33
13 Grafico para Dijkstra sobre o grafo rome99c . . . . . . . . . . . . . . 34
14 Grafico para Dijkstra sobre o grafo USA-road-d-NYc . . . . . . . . . 35
Lista de Programas
1 Algoritmo Floyd Warshall C . . . . . . . . . . . . . . . . . . . . . . . 5
2 TAD Grafo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3 Função CriaGrafoPorNome para o dijkstra . . . . . . . . . . . . . . . 7
4 Função ConstruindoLista . . . . . . . . . . . . . . . . . . . . . . . . . 8
5 Função ConstruindoLista . . . . . . . . . . . . . . . . . . . . . . . . . 9
6 TAD Grafo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
7 Criação da heap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
8 Inicialização da heap . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
9 Remove Menor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
10 Decrementa Chave . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
11 Tamanho . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
12 Fijkstra sem Impressão . . . . . . . . . . . . . . . . . . . . . . . . . . 12
13 Dijkstra com Impressão . . . . . . . . . . . . . . . . . . . . . . . . . . 13
14 Programa principal do Dijkstra . . . . . . . . . . . . . . . . . . . . . 14
15 TAD Grafo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
16 Função criagrafopornome . . . . . . . . . . . . . . . . . . . . . . . . . 16
17 Função alocaMatriz . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
18 Função iniciamatriz . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3
19 Função iniciaPred . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
20 Função floydP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
21 Função floyd . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
22 Função floydPNeg . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
23 Função floydNeg . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
24 Função imprimirsalvar . . . . . . . . . . . . . . . . . . . . . . . . . . 23
25 Função mainF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
26 Programa de Teste . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
Lista de Tabelas
1 Instâncias de teste e algoritmos a executar . . . . . . . . . . . . . . . 2
4
1 Introdução
A computação tem como base a resolução de problemas que até então não havia
soluções disponíveis bem como para soluções rápidas para o mesmo problema.
Assim, cabe ao Cientista da Computação identificar soluções para a resolução
dos problemas, principalmente, tornando-os otimizados e rápidos. Através desses
conceitos coube ao grupo utilizar os conceitos de Teoria dos Grafos para a modelagem
do trabalho.
Na teoria de grafos, o problema do caminho mínimo consiste na minimizaçãodo
custo de travessia de um grafo entre dois nós (ou vértices). Custo este dado pela
soma dos pesos de cada aresta percorrida.
Formalmente, dado um grafo valorado (ou seja, um conjunto V de vértices, um
conjunto A de arestas e uma função de peso f : A→ R) e, dado qualquer elemento
v ∈ V , encontrar um caminho P de v para cada v′ ∈ V tal que ∑p∈P f(p) é mínimo
entre todos os caminhos conectando n a n′.
1.1 Considerações iniciais
• Ambiente de desenvolvimento do código fonte: Microsoft Visual Studio C 10.0,
NetBeans 6.9.1.
• Compilador: gcc 4.4.5.
• Linguagem utilizada: Linguagem C.
• Ambiente de desenvolvimento da documentação: TeXnicCenter 1 BETA 7.50-
Editor de L
A
T
E
X, Editor dos grafos: R-2.12.0 for windows.
1.2 Especificações da máquina
• Intel Pentium IV 3.0 GHz, 64 bits
• Memória: 2 GB
• Ubuntu 10.10 AMD 64, kernel 2.6.35-22 generic
1.3 Especificação do problema
1.3.1 Material a ser entregue
Código em C, incluindo instruções para compilação. Essas instruções podem,
por exemplo, indicar opções que devem ser usadas na compilação do código em C.
(ex.: -O2 -ffast-math). Devem ser oferecidas as seguintes implementações:
• Algoritmo de Dijkstra para para computação de c.m. de uma fonte para todos
os outros vértices;
→ a fonte deve ser sorteada com a função rand a cada execução do algoritmo
de Dijkstra dentro do programa.
1
• Algoritmo Floyd-Warshall (FW) para computação dos caminhos mínimos de
todos os vértices para todos os outros do grafo;
→ a implementação de FW deve incluir um teste para a existência de ciclos de
custo negativo no grafo. Caso um seja encontrado, o algoritmo deve concluir
imediatamente sua execução e indicar o ciclo encontrado.
1.3.2 Documentação impressa incluindo
• explicação da implementação, incluindo referências bibliográficas;
• tabelas contendo os resultados dos experimentos realizados
1.3.3 Regras de Implementação
Os códigos devem ser escritos em C, sem o uso de bibliotecas adicionais, exceto
a biblioteca padrão da linguagem ou da biblioteca GNU.
Os seguintes padrões* C são aceitos:
• ANSI C 89
• ANSI C 99
• GNU C
*O compilador GCC permite a compilação com validação de códigos com a flag
-std. Ex.: (-std=c99).
Códigos com vazamento de memória ou problemas do tipo serão penalizados com
-1 pontos. Os códigos serão testados com a ferramenta valgrind.
1.3.4 Problemas Teste
Instância Vértices Arestas Testar
rome99c.gr 3.353 8.859 Dijkstra
USA-road-d.NYc.gr.bz2 264.346 730.100 Dijkstra
rg300_768.gr 300 768 Floyd-Warshall
rg300_4730.gr 300 4.730 Floyd-Warshall
comp-2007-2-22c.gr.gz 600 276.666 Floyd-Warshall
Tabela 1: Instâncias de teste e algoritmos a executar
• soluções devem ser checadas; caminhos mínimos pré-computados para rome99:
spathsRome99c.gr.bz2 (lembre-se que entre dois nós pode haver mais de um
caminho ótimo possível). outros: nspathsRg300_768.txt.bz2 .
• alguns problemas vieram da competição do DIMACS.
• os problemas teste para o algoritmo Floyd-Warshall (FW) podem incluir val-
ores negativos nos custos dos arcos. A implementação de FW, quando encon-
trar um ciclo de custo negativo, deve abortar a computação e como saída deve
somente indicar o caminho que indica o ciclo de custo negativo encontrado.
*
2
1.3.5 Formato de Entrada e Saída e Parâmetros
O programa deve receber os seguintes argumentos, quando chamado pela linha
de comando:
prog <arquivoProblema> <nrExecuções> <flagDepuração>
Onde <flagDepuração> pode receber valor 0 ou 1. Como exemplo:
prog rome99.gr 1000 1
Indica que o programa irá ler o grafo do arquivo rome99.gr, executando o algo-
ritmo de caminhos mínimos 1000 vezes e ao final irá imprimir/salvar informação de
depuração.
A informação de depuração que deve ser gerada, quando solicitada, é a seguinte:
arquivo spaths.txt
O arquivo spaths.txt deve conter todos os caminhos mínimos computados para
cada par de vértices (s,t), sendo s diferente de t . Cada linha contém a informação
sobre o caminho mínimo de um par (s,t), no formato:
[s,t](dist) n1 n2 n3 ... nn
Onde:
• s: nó fonte
• t: nó destino
• dist: distância calculada entre s e t
• n1 n2 n3 ... nn: caminho computado entre s e t, incluindo todos os nós
intermediários no formato: s n2 n3 ... t
1.4 Dijkstra
O algoritmo de dijkstra para caminhos mínimos foi feito por Edsger W. Dijkstra
em 1956 e foi publicado em 1959. Este algoritmo é um algoritmo de busca em
grafos que resolve o problema de caminhos mínimos para grafos sem ciclos de custo
negativo [5].
O algoritmo de dijkstra é um algoritmo guloso, pois toma uma decisão que
parece ser a melhor no momento. Dado um nó fonte ele calcula o caminho de
menor distancia deste nó a todos os outros. Ele funciona semelhante ao BFS, porém
trata grafos com peso. Ele trata os nós mais próximos da fonte primeiro, porém
essa proximidade se refere ao peso entre as arestas e não ao número de arestas
percorridas. Sua complexidade é O((|E|+ |V |)log|V |)[5].
Para a execução do algoritmo são utilizados dois vetores auxiliares (�dist� e
�pred�) com tamanho igual ao numero de vértices do grafo. O vetor �dist� armazenará
as distancias do nó fonte até qualquer nó do grafo. O vetor �pred� armazenará os
anteriores de cada nó no caminho da fonte até ele. Além disso é necessária uma
heap para saber a ordem de processamento dos nós.
Ao inicio da execução do algoritmo o vetor de distancias é inicializado com infinito
para todos os vértices, exceto o nó fonte s que terá distancia 0. O vetor �pred� será
todo inicializado com nulo. O algoritmo processa todos os nós da �heap�. Enquanto
ainda há nós na �heap� retira-se o menor vértice (u) e, para cada vizinho v vértice
verifica se a distancia até v passando por u é menor que a distancia até v já calculada.
Caso seja menor u é marcado como antecessor de v no vetor �pred� e a distancia
3
até v é alterada para a distancia até u mais a distancia entre u e v, atualizando a
�heap� com a nova distancia.
As operações que são mais custosas para o algoritmo do dijkstra são as operações
sobre a �heap�, portanto uma escolha errada de �heap� pode causar ineficiência do
algoritmo.
1.4.1 Heaps
Heaps são filas de prioridade implementadas baseadas em árvores. Existem ba-
sicamente dois tipos de heap, a heap de máximo, em que para cada nó x na arvore,
x tem chave maior que de todos seus filhos[2], e a heap de mínimo que é utilizada no
algoritmo de dijkstra, em que cada nó x pai sempre é menor que todos seus filhos.
As heaps para o dijkstra possuem como chave os valores de distancia do vértice
fonte até os respectivos nós. A medida que a distancia encontrada diminui para cada
nó, sua prioridade aumenta e sua vez de ser processado se aproxima, configurando
uma heap de mínimo.
As funções básicas de uma heap qualquer são:
• Inserção
• deleção de menor
• decremento da chave
Heaps de Fibonacci:
Para a versão final foi feita uma tentativa de implementação da heap de fibonacci[7].
As heaps de fibonacci são coleções de árvores ordenadas como heaps mínimos[6]. As
heaps de fibonacci são implementadas usando listas circulares duplamente encadeadas[1].
A heap é composta da lista de raízes e para cada nó da lista de raízes tem uma lista
de filhos que também pode ter seus filhos, assim em diante. A heap também tem
um ponteiro para o menor nó da lista.
A inserção na heap de fibonacci apenas insere o novo nó na lista de raízes. A
inserção verifica se o novo nó é menor que o menor atual, caso seja o menor passa a
ser o novo. Esse procedimento é executado com custo real O(1).
Na função de extração do menor nó, o nó apontado por �min� é removido da
lista de raízes e todos seus filhos são inseridos na lista de raízes. Depois a heap é
consolidada, o que significa que todas as raízes terão grau (numero de filhos na lista)
diferente.Caso haja mais de um nó com um certo grau, o maior deles vira filho do
outro. A menor das raízes passa a ser o novo �min�. O custo amortizado da função
de extração de menor é O(logn).
A diminuição da chave pode fazer com que um filho fique menor que seu pai,
ferindo a propriedade das heaps. Caso isso ocorra este nó é cortado do pai e levado
à lista de raízes. Caso o pai seja filho de outro nó e já tenha perdido um filho sendo
filho desde que virou filho de seu nó pai, ele também será cortado de seu pai e virará
raiz da heap, senão apenas será marcado para ser cortado se perder mais filhos. Se
o nó decrementado for menor que a raiz, este passará a ser o novo minimo. O custo
amortizado desta função é O(1).
As heaps de fibonacci possuem uma estrutura muito complexa, contendo listas
circulares duplamente encadeadas. Isso dificultou bastante a implementação não
permitindo que fosse encerrada a versão do dijkstra usando essas heaps em tempo
4
hábil, pois para cada nó há apontador para seu pai, seu irmão da esquerda, seu
irmão da direita e todos seus filhos. Acredita-se que essas heaps poderiam melhorar
ainda mais o algoritmo do dijkstra devido à sua boa complexidade. Com as heaps
binarias a ordem de complexidade do dijkstra se aproxima muito de O(n2logn), com
heaps de fibonacci essa complexidade aproximaria O(n2).
1.4.2 Aplicação do Algoritmo
1.4.3 Versão Preliminar x Final
Para o problema proposto a cada nó da heap é representado pelo índice de seu
vértice no grafo, índice esse que é usado para a identificação da distancia do nó no
vetor �dist�, valor este que é a chave do nó. A função diminui recebe o índice do nó
que foi alterado, porém não é conhecido seu posicionamento na heap. Para saber
qual nó da heap foi alterado de inicio foi feita uma busca linear O(n) em todo o
vetor da heap, versão que foi enviada na preliminar da competição.
Para a versão final essa busca linear foi substituída pela busca em hash que é
O(1). Como os possíveis valores da heap são conhecidos (1 até n) e também seu
tamanho máximo (n), foi possível fazer um hash mínimo perfeito. Para isso foi criado
um novo vetor �pos�, que para cada posição i deste vetor, seu valor corresponde à
posição do vértice i do grafo no vetor da heap.
1.5 Floyd-Warshall
O algoritmo de Floyd-Warshall tem como objetivo calcular a menor distância de
todos os vértices do grafo para todos os demais, recebendo, para isso, uma matriz
de adjacências representando o grafo.
Com ordem de complexidade cúbica assume que para percorrer o caminho A→ C
haverá um caminho A→ B e B → C, isto é, para qualquer par de vértices (i, j) ∈ V ,
considera-se todos os caminhos de iaj cujos vértices intermediários pertencem ao
subconjunto 1, 2, 3..., k, e p como o mais curto de todos eles.
Em resumo:
dist(i; j; k): o comprimento do caminho mais curto entre i e j tal que apenas
os nós 1, ..., k podem ser usados como intermediários.
No Programa 1 temos o algoritmo implementado em C.
void f l oyd (TGrafo∗ g , TVertice ∗∗ auxMatriz ) {
int k , i , j ;
int ∗∗ pred ;
pred = NULL;
5 pred = in i c i aP r ed ( pred ,&(g−>qtdVert ) ) ;
for ( i =0; i< g−>qtdVert ; i++)
for ( j =0; j<g−>qtdVert ; j++)
auxMatriz [ i ] [ j ] = g−>matriz [ i ] [ j ] ;
for ( k = 0 ; k < g−>qtdVert ; k++)
10 for ( i = 0 ; i < g−>qtdVert ; i++)
for ( j = 0 ; j < g−>qtdVert ; j++)
i f ( ( auxMatriz [ i ] [ k ] . peso + auxMatriz [ k ] [ j ] . peso ) <
auxMatriz [ i ] [ j ] . peso ) {
auxMatriz [ i ] [ j ] . peso = auxMatriz [ i ] [ k ] . peso +
auxMatriz [ k ] [ j ] . peso ;
pred [ i ] [ j ] = pred [ k ] [ j ] ;
15 i f ( auxMatriz [ i ] [ i ] . peso < 0) {
5
return ;
}
}
f r e e ( pred [ 0 ] ) ;
20 f r e e ( pred ) ;
}
Programa 1: Algoritmo Floyd Warshall C
1.5.1 Aplicação do Algoritmo
O algoritmo de Floyd-Warshall pode ser utilizado para os seguintes problemas:
• Caminhos mais curtos em grafos orientados (algoritmo de Floyd);
• Proximidade transitiva de grafos orientados (algoritmo de Warshall);
• Encontrar uma expressão regular denotando a linguagem regular aceita por
um autômato finito (algoritmo de Kleene);
• Inversões de matrizes de números reais (algoritmo de Gauss-Jordan);
• Roteamento otimizado. Nesta aplicação, o objetivo é encontrar o caminho
com o máximo fluxo entre dois vértices. Isto significa que, em vez de calcular
o mínimo, calcula-se o máximo;
• Testar se um grafo não-orientado é bipartido.
1.5.2 Versão Preliminar x Final
Reinicialização das Matrizes:
• Preliminar: Na versão preliminar havia um erro no algoritmo de modo que as
matrizes de distâncias e dos predecessores não eram reinicializadas quando o
usuário passava como argumento um número inteiro superior a uma execução.
Através disso as matrizes não eram reinicializadas a partir da 1 execução.
Esse problema afetava a execução do programa somente quando não havia
impressão ou quando o número de execuções fosse superior a 1 (um).
• Final: Para melhorar o desempenho bem como corrigir o problema anterior
alocamos tanto a matriz de distâncias quanto a dos predecessores antes de
chamar a função do algoritmo Floyd-Warshall e desalocando no final da ex-
ecução de todo o programa, assim possibilitou em um ganho de desempenho
quando levarmos em consideração a alocação das matrizes.
Um ponto importante a ser citado é que mesmo não alocando e desalocando a
todo execução sempre reinicializamos as duas matrizes. Isso pode ser percebido
no Programa 17
Tratamento do Ciclo Negativo:
• Preliminar: Não havia uma otimização no tratamento de ciclos negativos,
assim, em cada execução o algoritmo verificava se havia ou não ciclos negativos
no grafo.
6
• Final: Para otimizar o tratamento de ciclos negativos foi incluída na estrutura
15 do grafo uma variável ehcicloNeg que verifica na entrada de arquivos, vide
Programa 16, se no grafo continha ou não peso negativo. Através dessa veri-
ficação, para otimizar, criamos diferentes funções para o algoritmo de Floyd-
Warshall, sendo para grafos com ciclos negativos: floydPNeg, floydNeg, vide
Programas 22, 23 respectivamente .
E para positivos: floydP, floyd, vide Programas 20, 21 respectivamente. Nessas
funções não realizamos a verificação para caso haja ciclo negativo uma vez que
o grafo não contém determinado ciclo[3].
Obs.: Na Seção 2.4 explicaremos melhor esse método.
2 Algoritmo e estruturas de dados
2.1 Grafo do Dijkstra
O grafo para o algoritmo de dijkstra foi representado pela lista de adjacências
apresentada na estrutura 2
#include " s t d a f x . h"
typedef struct {
int qtdusada , ∗ r e su l t ado ;
5 } Caminho ;
typedef struct {
int ∗ v iz inhos , ∗pesos , qtdAlloc , qtdFree ;
} TVertice ;
10
typedef struct {
int qtdVert , qtdMedia ;
TVertice ∗ v ;
} TGrafo ;
15
TGrafo cria_grafo_por_nome (char∗) ;
void imprimir_salvar (Caminho∗) ;
20 void cons t ru indoL i s t a ( int ∗ , int ∗ , TGrafo ∗) ;
void addInteracao ( int ∗ , int ∗ , TGrafo ∗ , int ∗) ;
Programa 2: TAD Grafo
2.1.1 Função CriaGrafoPorNome
A Função �CriaGrafoPorNome� tem como objetivo fazer a leitura do grafo a
partir de um arquivo .txt e iniciar a lista de adjacências bem como instanciar a lista
com todos arcos do grafo de um vértice A para um vértice B.
Vide Programa 3
TGrafo cria_grafo_por_nome (char∗ nome) {
7
FILE ∗arqE ;
char ∗buf , ∗ tok ;
5 TGrafo g ;
int numArestas , numVertices , vA, vB , peso , media_qtd_arestas ;
buf = (char∗) mal loc ( s izeof (char ) ∗BUFSIZ) ;
arqE = fopen (nome , "r" ) ;
10 i f ( ! arqE ) {
p r i n t f ("Erro ao a b r i r o arqu ivo de entrada %s" , nome) ;
g . qtdVert = −1;
return ( g ) ;
}
15 while ( ! f e o f ( arqE ) ) {
buf = f g e t s ( buf , BUFSIZ , arqE ) ;
i f ( buf == NULL)
break ;
20 switch ( buf [ 0 ] ) {
case ' p ' :
tok = s t r t ok( buf , " " ) ;
tok = s t r t ok (NULL, " " ) ;
tok = s t r t ok (NULL, " " ) ;
25 numVertices = a t o i ( tok ) ;
tok = s t r t ok (NULL, " " ) ;
numArestas = a t o i ( tok ) ;
media_qtd_arestas = numArestas / numVertices + 1 ;
cons t ru indoL i s t a (&numVertices , &media_qtd_arestas , &g ) ;
30 break ;
case ' a ' :
tok = s t r t ok ( buf , " " ) ;
tok = s t r t ok (NULL, " " ) ;
vA = ato i ( tok ) ;
35 tok = s t r t ok (NULL, " " ) ;
vB = ato i ( tok ) ;
tok = s t r t ok (NULL, " " ) ;
peso = a to i ( tok ) ;
addInteracao(&vA, &vB , &g , &peso ) ;
40 break ;
default :
break ;
}
}
45 f c l o s e ( arqE ) ;
f r e e ( buf ) ;
return ( g ) ;
}
Programa 3: Função CriaGrafoPorNome para o dijkstra
2.1.2 Função ConstruindoLista
A Função �ConstruindoLista� tem como objetivo inicializar a lista de adjacências
para todos os nós. Vide Programa 4
void cons t ru indoL i s t a ( int∗ qtdV , int∗ media , TGrafo∗ g ) {
int i ;
g−>qtdMedia = ∗media ;
g−>qtdVert = ∗qtdV ;
8
5 g−>v = ( TVertice ∗) c a l l o c (∗qtdV , s izeof ( TVertice ) ) ;
for ( i = 0 ; i < ∗qtdV ; i++) {
g−>v [ i ] . qtdAl loc = 0 ;
g−>v [ i ] . qtdFree = ∗media ;
g−>v [ i ] . v i z i nho s = ( int ∗) c a l l o c (∗media , s izeof ( int ) ) ;
10 g−>v [ i ] . pesos = ( int ∗) c a l l o c (∗media , s izeof ( int ) ) ;
}
}
Programa 4: Função ConstruindoLista
2.1.3 Função AddInteração
A função �AddInteração� adiciona a interação lida do arquivo ao nó de origem
da mesma. Vide Programa 5
void addInteracao ( int∗ vA, int∗ vB , TGrafo∗ g , int∗ peso ) {
i f ( ! g−>v [ ( ∗vA) − 1 ] . qtdFree ) {
g−>v [ ( ∗vA) − 1 ] . qtdFree += g−>qtdMedia ;
g−>v [ ( ∗vA) − 1 ] . pesos = ( int ∗) r e a l l o c ( g−>v [ ( ∗vA) − 1 ] . pesos ,
s izeof ( int ) ∗( g−>v [ ( ∗vA) − 1 ] . qtdFree + g−>v [ ( ∗vA) − 1 ] .
qtdAl loc ) ) ;
5 g−>v [ ( ∗vA) − 1 ] . v i z i nho s = ( int ∗) r e a l l o c ( g−>v [ ( ∗vA) − 1 ] .
v i z inhos , s izeof ( int ) ∗( g−>v [ ( ∗vA) − 1 ] . qtdFree + g−>v [ ( ∗
vA) − 1 ] . qtdAl loc ) ) ;
}
g−>v [ ( ∗vA) − 1 ] . v i z i nho s [ g−>v [ ( ∗vA) − 1 ] . qtdAl loc ] = ( (∗vB) − 1) ;
g−>v [ ( ∗vA) − 1 ] . pesos [ g−>v [ ( ∗vA) − 1 ] . qtdAl loc++] = ∗peso ;
g−>v [ ( ∗vA) − 1 ] . qtdFree−−;
10 }
Programa 5: Função ConstruindoLista
2.2 Heap Binária
A heap binaria é representada por uma árvore binária completa ou quase com-
pleta. Para o caso do dijkstra, como a heap é mínima, o pai sempre é menor que
seus filhos. Para representar a heap há duas estruturas possíveis, lista encadeada
com ponteiros para os dois filhos e lista simples utilizando um vetor[8]. Na imple-
mentação foi utilizada a segunda estrutura por ser mais simples de trabalhar. Vide
Programa 6:
#include "TGrafoD . h"
typedef struct Heap {
int ∗v , ∗ d i s t , ∗pos , qtdV ;
5 } THeap ;
int tamanho (THeap∗) ;
void criaHeap (THeap∗ , int ∗) ;
10
void r e c o n s t r o i ( int , int , THeap∗) ;
void c on s t r o i (THeap∗) ;
9
15 int pegarMenor (THeap∗) ;
void diminui (THeap∗ , int ∗) ;
Caminho d i j k s t r aP (TGrafo ∗ , int ∗) ;
20
void d i j k s t r a (TGrafo ∗ , int ∗) ;
Programa 6: TAD Grafo
Para representar uma árvore com vetor considera-se que para o vértice i seus
filhos são (2 ∗ i + 1) e (2 ∗ i + 2), sendo sua raiz o nó de índice 0. O pai de um nó
de índice i é representado pelo nó de índice ceil(i/2).
2.2.1 Inicialização da heap
A função �Criaheap�7 aloca todas os vetores da heap e inicializa seus valores
para os esperados ao inicio do dijkstra.
void criaHeap (THeap∗ h , int∗ qtdD) {
int i ;
h−>qtdV = ∗qtdD ;
h−>v = ( int ∗) c a l l o c (∗qtdD , s izeof ( int ) ) ;
5 h−>d i s t = ( int ∗) c a l l o c (∗qtdD , s izeof ( int ) ) ;
h−>pos = ( int ∗) c a l l o c (∗qtdD , s izeof ( int ) ) ;
for ( i = 0 ; i < ∗qtdD ; i++) {
h−>d i s t [ i ] = INF ;
h−>v [ i ] = i ;
10 h−>pos [ i ] = i ;
}
}
Programa 7: Criação da heap
A Inserção para a heap binária consiste em colocar sua chave no vetor e refazer
o posicionamento do nós no vetor seguindo os índices de forma a respeitar a pro-
priedade da heap de que o pai é menor que todos os filhos. A ordem de complexidade
da inserção é O(logn)[8]. Para o caso do dijkstra todos os nós são inseridos na heap
logo no começo, para isso existe a função constrói que considera que as n/2 últimas
posições do vetor já estão na heap, já que nenhuma posição representa o pai de outra
já que i é pai de 2∗i+1 e 2∗i+2 e i é pai de n+1 e n+2, para i = n/2. Considerando
isso os n/2 primeiros nós são inseridos na heap pela função �reconstrói� que verifica
a propriedade da heap, trocando o pai com seu menor filho, caso o filho seja menor
que o pai. Na teoria são feitas n/2 inserções na heap, o que gera uma complexidade
O(nlogn)[2]. Vide Programa 8
void c on s t r o i (THeap∗ h) {
int esq ;
esq = h−>qtdV / 2 ;
while ( esq >= 0) {
5 r e c o n s t r o i ( esq , h−>qtdV − 1 , h) ;
esq−−;
}
}
10 void r e c o n s t r o i ( int esq , int dir , THeap ∗h) {
10
int i = esq ;
int j ;
int aux ;
j = i ∗ 2 + 1 ;
15 aux = h−>v [ i ] ;
while ( j <= d i r ) {
i f ( j < d i r )
i f (h−>d i s t [ h−>v [ j ] ] > h−>d i s t [ h−>v [ j + 1 ] ] )
j++;
20 i f (h−>d i s t [ aux ] <= h−>d i s t [ h−>v [ j ] ] )
break ;
h−>pos [ h−>v [ j ] ] = i ;
h−>v [ i ] = h−>v [ j ] ;
i = j ;
25 j = i ∗ 2 + 1 ;
}
h−>pos [ aux ] = i ;
h−>v [ i ] = aux ;
}
Programa 8: Inicialização da heap
2.2.2 Remove menor
A remoção do menor é feita pegando sua chave e o trocando com o ultimo
elemento válido do vetor, que será a folha extrema direita da árvore. Após isso a
heap é refeita com a função �reconstrói� desconsiderando a posição onde estava o
ultimo. Sua complexidade é O(logn)[8].Vide Programa 8
int pegarMenor (THeap∗ h) {
int min ;
min = h−>v [ 0 ] ;
h−>v [ 0 ] = h−>v[(−−h−>qtdV) ] ;
5 h−>pos [ h−>v [ 0 ] ] = 0 ;
r e c o n s t r o i (0 , h−>qtdV − 1 , h) ;
return min ;
}
Programa 9: Remove Menor
2.2.3 Diminui
Para decrementar a chave, já que o dijkstra já altera o valor do vetor �dist�, a
função apenas verifica se o elemento com chave alterada fere a propriedade da heap
e o troca com seu pai em caso afirmativo. Isso é feito até que a propriedade volte a
ser obedecida pelo nó alterado. Vide Program 10
void diminui (THeap ∗h , int∗ i ) {
int aux , pos ;
pos = h−>pos [∗ i ] ;
5
while ( ( pos ) >= 1 && h−>d i s t [ h−>v [ ( int ) c e i l ( ( pos ) / 2 . ) − 1 ] ] > h
−>d i s t [ h−>v [ ( pos ) ] ] ) {
aux = h−>v [ ( int ) c e i l ( ( pos ) / 2 . ) − 1 ] ;
11
h−>v [ ( int ) c e i l ( ( pos ) / 2 . ) − 1 ] = h−>v [ ( pos ) ] ;
10 h−>pos [ h−>v [ ( int ) c e i l ( ( pos ) / 2 . ) − 1 ] ] = ( int ) c e i l ( ( pos ) /
2 . ) − 1 ;
h−>v [ ( pos ) ] = aux ;
h−>pos [ aux]=pos ;
pos = ( int ) c e i l ( ( pos ) / 2 . ) − 1 ;
}
15 }
Programa 10: Decrementa Chave
2.2.4 Tamanho
Esta função apenas retorna o tamanho da heap. Usada para verificar a existencia
de elementos na heap. Vide Programa 11
int tamanho (THeap∗ h) {
return h−>qtdV ;
}
Programa 11: Tamanho
2.3 Dijkstra
2.3.1 Função Dijkstra
Essa função é responsável pela simples execução do algoritmo de Dijkstra sem
impressão de caminho.
void d i j k s t r a (TGrafo∗ g , int∗ s ) {
THeap h ;
int v , u , i , ∗prev ;
5 prev = ( int ∗) c a l l o c ( g−>qtdVert , s izeof ( int ) ) ;
cr iaHeap(&h , &(g−>qtdVert ) ) ;
h . d i s t [∗ s ] = 0 ;
c on s t r o i (&h) ;
10 while ( tamanho(&h) ) {
v = pegarMenor(&h) ;
for ( i = 0 ; i < g−>v [ v ] . qtdAl loc ; i++) {
u = g−>v [ v ] . v i z i nho s [ i ] ;
i f (h . d i s t [ u ] > h . d i s t [ v ] + g−>v [ v ] . pesos [ i ] ) {
15 h . d i s t [ u ] = h . d i s t [ v ] + g−>v [ v ] . pesos [ i ] ;
prev [ u ] = v ;
diminui (&h , &u) ;
}
}
20 }
f r e e (h . d i st ) ;
f r e e (h . v ) ;
f r e e ( prev ) ;
}
Programa 12: Fijkstra sem Impressão
12
2.3.2 Função DijkstraP
Essa função é responsável pela execução do algoritmo de Dijkstra imprimindo de
caminho. O caminho que é calculado para cada vertice v percorrendo o vetor �pred�
iniciando pelo �pred[v]� seguindo pelo �pred� até que ele seja igual ao nó fonte do
dijkstra. Vide Programa 13
Caminho d i j k s t r aP (TGrafo∗ g , int∗ s ) {
THeap h ;
Caminho c ;
FILE∗ arq ;
5 int v , w, u , aux , ∗prev , i ;
prev = ( int ∗) c a l l o c ( g−>qtdVert , s izeof ( int ) ) ;
cr iaHeap(&h , &(g−>qtdVert ) ) ;
h . d i s t [∗ s ] = 0 ;
10 c on s t r o i (&h) ;
for (u = 0 ; u < g−>qtdVert ; u++) {
15 prev [ u ] = −1;
}
while ( tamanho(&h) ) {
v = pegarMenor(&h) ;
for ( i = 0 ; i < g−>v [ v ] . qtdAl loc ; i++) {
20 u = g−>v [ v ] . v i z i nho s [ i ] ;
i f (h . d i s t [ u ] > h . d i s t [ v ] + g−>v [ v ] . pesos [ i ] ) {
h . d i s t [ u ] = h . d i s t [ v ] + g−>v [ v ] . pesos [ i ] ;
prev [ u ] = v ;
diminui (&h , &u) ;
25 }
}
}
w = INF ;
30 for (u = 0 ; u < g−>qtdVert ; u++) {
f r e e ( g−>v [ u ] . pesos ) ;
f r e e ( g−>v [ u ] . v i z i nho s ) ;
}
arq = fopen (" spa th s . t x t " , "w" ) ;
35
i f ( ! arq ) {
p r i n t f ("Erro ao e s c r e v e r no arqu ivo " ) ;
return ;
}
40 c . r e su l t ado = ( int ∗) mal loc ( s izeof ( int ) ∗( g−>qtdVert+1) ) ;
for (u = 0 ; u < g−>qtdVert ; u++) {
i f (u == ∗ s | | h . d i s t [ u]== w)
continue ;
c . qtdusada = 2 ;
45 c . r e su l t ado [ 0 ] = h . d i s t [ u ] ;
c . r e su l t ado [ 1 ] = u ;
aux = prev [ u ] ;
while ( aux != ∗ s && aux != −1){
c . r e su l t ado [ c . qtdusada++] = aux ;
50 aux = prev [ aux ] ;
}
13
c . r e su l t ado [ c . qtdusada ] = ∗ s ;
f p r i n t f ( arq , "[%d,%d](%d)" , (∗ s )+1, u+1, c . r e su l t ado [ 0 ] ) ;
for ( i = c . qtdusada ; i > 0 ; i−−){
55 f p r i n t f ( arq , " %d" , c . r e su l t ado [ i ]+1) ;
}
f p r i n t f ( arq , "\n" ) ;
}
f r e e ( c . r e su l t ado ) ;
60 f r e e (h . d i s t ) ;
f r e e (h . v ) ;
f r e e ( g−>v) ;
return c ;
}
Programa 13: Dijkstra com Impressão
2.3.3 Função Main para o Dijkstra
Essa função efetua as chamadas para leitura de arquivos e execução do dijkstra.
Note que foi feito uso de uma técnica denominada Loop Unrolling para aproveitarmos
melhor o uso do Pipeline do processador[4], ganhando uma leve melhora no tempo
de execução do programa.
#include "TDijks tra . h"
int main ( int argc , char∗∗ argv ) {
5 int f lagDepuracao , nrExecucao , vertRand ;
TGrafo g ;
Caminho c ;
i f ( argc < 3) {
p r i n t f ("Confira o numero de parametros " ) ;
10 return (EXIT_FAILURE) ;
}
srand (0 ) ;
f lagDepuracao = a t o i ( argv [ 3 ] ) ;
nrExecucao = a to i ( argv [ 2 ] ) ;
15
g = cria_grafo_por_nome ( argv [ 1 ] ) ;
i f ( g . qtdVert == −1) {
p r i n t f ("\n∗∗Erro ao c r i a r o gra fo " ) ;
return (EXIT_FAILURE) ;
20 }
switch ( f lagDepuracao ) {
case 0 :
switch ( nrExecucao % 4) {
case 0 :
25 while ( nrExecucao ) {
vertRand = rand ( ) % g . qtdVert ;
d i j k s t r a (&g , &vertRand ) ;
nrExecucao−−;
30 vertRand = rand ( ) % g . qtdVert ;
d i j k s t r a (&g , &vertRand ) ;
nrExecucao−−;
vertRand = rand ( ) % g . qtdVert ;
14
35 d i j k s t r a (&g , &vertRand ) ;
nrExecucao−−;
vertRand = rand ( ) % g . qtdVert ;
d i j k s t r a (&g , &vertRand ) ;
40 nrExecucao−−;
}
break ;
case 2 :
while ( nrExecucao ) {
45 vertRand = rand ( ) % g . qtdVert ;
d i j k s t r a (&g , &vertRand ) ;
nrExecucao−−;
vertRand = rand ( ) % g . qtdVert ;
50 d i j k s t r a (&g , &vertRand ) ;
nrExecucao−−;
}
break ;
55 default :
while ( nrExecucao−−) {
vertRand = rand ( ) % g . qtdVert ;
d i j k s t r a (&g , &vertRand ) ;
}
60 break ;
}
break ;
case 1 :
65 vertRand = 0 ;
c = d i j k s t r aP (&g , &vertRand ) ;
}
return (EXIT_SUCCESS) ;
70 }
Programa 14: Programa principal do Dijkstra
2.4 Grafo do Floyd-Warshall
Para a representação do grafo utilizamos a estrutura �TGrafo� 15, onde temos
uma variável ehcicloNeg para a verificação se o grafo é negativo ou não bem como
qtdVert, qtdAres para a quantidade de vértices e arestas respectivamente. O grafo,
na verdade, é representado por uma matriz de adjacências do tipo TVertice** matriz,
contendo um peso (distância) de um vértice A para um vértice B. Isso pode ser
visto facilmente no Programa 15.
Além de calcular a distância e a matriz de predecessores, para a impressão dos
caminhos de todos os vértices para todos os demais, foi preciso utilizar a estrutura
Caminho, onde qtdTotal, neg, s, t representam a quantidade total de vértices do
grafo, verificação se o grafo é ou não negativo para a geração do caminho de ciclo
negativo, s e t os vértices de início e final do grafo, respectivamente. E, ainda, o
resultado contendo a quantidade de vértices que fazem parte do caminho gerado e o
próprio caminho de um vértice A para um vértice B. Isso pode ser visto na Figura
5
15
#include " s t d a f x . h"
typedef struct {
int∗ TP, qtdNos ;
5 } TPasseio ;
typedef struct {
TPasseio∗ r e su l t ado ;
int qtdTotal , neg , s , t ;
10 } Caminho ;
typedef struct {
int peso ;
} TVertice ;
15
typedef struct {
int qtdVert , qtdAres ;
short int ehc i c loNeg ;
TVertice ∗∗ matriz ;
20 } TGrafo ;
TGrafo cria_grafo_por_nome (char∗) ;
void imprimir_salvar (Caminho∗) ;
25
void i n i c i a_matr i z (TGrafo ∗) ;
void inst_matr iz (TGrafo ∗ , int ∗ , int ∗ , int ∗) ;
30 Caminho∗ f loydP (TGrafo ∗) ;
void f l oyd (TGrafo ∗ , TVertice ∗∗ , int ∗∗) ;
TVertice ∗∗ a locaMatr i z ( TVertice ∗∗ , int ∗) ;
35
int ∗∗ i n i c i aP r ed ( int ∗∗ , int∗ ) ;
Caminho∗ floydPNeg (TGrafo∗ ) ;
40 void f loydNeg (TGrafo∗ TVertice ∗∗ , int ∗∗ ) ;
Programa 15: TAD Grafo
2.4.1 Função CriaGrafoPorNome
A Função 2.4.1 tem como objetivo fazer a leitura do grafo a partir de um arquivo
.txt e ainda iniciar a matriz de adjacências 2.4.3 bem como instanciar a matriz com
todos os pesos do grafo de um vértice A para um vértice B. E é claro, verificar para
todos os vértices do grafo, durante a inserção, se o grafo contém aresta com peso
negativo.
Vide Programa 16
TGrafo cria_grafo_por_nome (char∗ nome) {
FILE ∗arqE ;
char ∗buf , ∗ tok ;
TGrafo g ;
16
5 int numArestas , numVertices , vA, vB , peso , media_qtd_arestas ;
tok = (char∗) mal loc ( s izeof (char ) ∗10) ;
buf = (char∗) mal loc ( s izeof (char ) ∗100) ;
arqE = fopen (nome , "r" ) ;
i f ( ! arqE ) {
10 p r i n t f ("Erro ao a b r i r o arqu ivo de entrada %s" , nome) ;
g . qtdVert = −1;
return ( g ) ;
}
g . ehc i c loNeg = 0 ;
15 while ( ! f e o f ( arqE ) ) {
buf = f g e t s ( buf , BUFSIZ , arqE ) ;
i f ( buf == NULL)
break ;
switch ( buf [ 0 ] ) {
20 case ' p ' :
tok = s t r t ok ( buf , " " ) ;
tok = s t r t ok (NULL, " " ) ;
tok = s t r t ok (NULL, " " ) ;
numVertices = a t o i ( tok ) ;
25 tok = s t r t ok (NULL, " " ) ;
numArestas = a t o i ( tok ) ;
g . qtdAres = numArestas ;
g . qtdVert = numVertices ;
i n i c i a_matr i z (&g ) ;
30 break ;
case ' a ' :
tok = s t r t ok ( buf , " " ) ;
tok = s t r t ok (NULL, " " ) ;
vA = ato i ( tok ) − 1 ;
35 tok = s t r t ok (NULL, " " ) ;
vB = ato i ( tok ) − 1 ;
tok = s t r t ok (NULL, " " ) ;
peso = a to i ( tok ) ;
i f ( peso <0)
40 g . ehc i c loNeg = 1 ;
g . matr iz [ vA ] [ vB ] . peso = peso ;
break ;
default :
break ;
45 }
}
return ( g ) ;
}
Programa 16: Função criagrafopornome
2.4.2 Função alocaMatriz
Para a alocação da matriz, por padrão, seria feita em ordem de complexidade
quadrática,no entanto, para otimizar o código fizemos em ordem de complexidade
linear. Para isso foi preciso alocar a matriz com a quantidade de linhas da matriz de
adjacências e mais uma alocação para a posição �matriz[0]� com tamanho Linha ∗
Coluna, fazendo, em seguida, um redirecionamento dos endereços da matriz.
Por exemplo, numa matriz 3x2 alocamos a matriz com 3 posições, sendo que para
a �matriz[0]� alocaremos 6 posições. Assim, no redirecionamento dos ponteiros como,
17
por exemplo, a posição �matriz[1]� receberá o endereço da matriz[0][i ∗ coluna], ou
seja, matriz[0][1x2]. Para melhor entendimento, vide Figura 1 e Programa 17.
Figura 1: Figura Repres. Alocação Matriz
18
TVertice ∗∗ a locaMatr i z ( TVertice ∗∗ matriz , int∗ tam) {
int i , j ;
matr iz = ( TVertice ∗∗) mal loc ( (∗ tam) ∗ s izeof ( TVertice ∗) ) ;
i f ( matr iz == NULL) {
5 p r i n t f ("Erro ao a locar a matr iz \n" ) ;
return 0 ;
}
matr iz [ 0 ] = ( TVertice ∗) mal loc ( ( (∗ tam) ∗(∗ tam) ) ∗ s izeof ( TVertice ) )
;
i f ( matr iz [ 0 ] == NULL) {
10 p r i n t f ("Erro ao a locar a matr iz \n" ) ;
return 0 ;
}
for ( i = 1 ; i < (∗ tam) ; i++) {
matr iz [ i ] = &(matr iz [ 0 ] [ i ∗ (∗ tam) ] ) ;
15 }
return matriz ;
}
Programa 17: Função alocaMatriz
2.4.3 Função iniciaMatriz
Função responsável por alocar 2.4.2 e inicializar a matriz de adjacências. Vide
Programa 18
void i n i c i a_matr i z (TGrafo∗ g ) {
int i , j ;
g−>matriz = alocaMatr i z ( g−>matriz , &(g−>qtdVert ) ) ;
for ( i = 0 ; i < g−>qtdVert ; i++)
5 for ( j = 0 ; j < g−>qtdVert ; j++)
g−>matriz [ i ] [ j ] . peso = INF ;
for ( i = 0 ; i < g−>qtdVert ; i++)
g−>matriz [ i ] [ i ] . peso = 0 ;
}
Programa 18: Função iniciamatriz
2.4.4 Função iniciaPred
Função semelhante a Função �iniciaMatriz� 2.4.3. Vide Programa 19
int ∗∗ i n i c i aP r ed ( int ∗∗ pred , int∗ tam) {
int i , j ;
i f ( pred == NULL) {
pred = ( int ∗∗) mal loc ( (∗ tam) ∗ s izeof ( int ∗) ) ;
5 i f ( pred == NULL) {
p r i n t f ("Erro ao a locar a matr iz \n" ) ;
return 0 ;
}
pred [ 0 ] = ( int ∗) mal loc ( ( (∗ tam) ∗(∗ tam) ) ∗ s izeof ( int ) ) ;
10 i f ( pred [ 0 ] == NULL) {
p r i n t f ("Erro ao a locar a matr iz " ) ;
return 0 ;
}
for ( i = 1 ; i < (∗ tam) ; i++) {
19
15 pred [ i ] = &(pred [ 0 ] [ ( ∗ tam) ∗ i ] ) ;
}
}
for ( i = 0 ; i < (∗ tam) ; i++)
for ( j = 0 ; j < (∗ tam) ; j++)
20 pred [ i ] [ j ] = i ;
return pred ;
}
Programa 19: Função iniciaPred
2.5 Floyd-Warshall
2.5.1 Função floydP
Função responsável por calcular a distância e predecessores de todos os vértices
do grafo positivo, utilizando o Algoritmo de Floyd Warshall, note que não é preciso
reinicializar a matriz de adjacências bem como a de predecessores uma vez que
quando passarmos ao programa a flag 1 de impressão o programa executará somente
uma única vez.
Para uma ilustração da geração dos caminhos veja a Figura 5. Vide Programa
20
Caminho∗ f loydP (TGrafo∗ g ) {
int k , i , j , aux , n = 0 , pos ;
Caminho∗ c ;
int ∗∗ pred ;
5 pred = NULL;
pred = in i c i aP r ed ( pred , &(g−>qtdVert ) ) ;
c = (Caminho∗) mal loc ( g−>qtdVert ∗ s izeof (Caminho ) ) ;
c−>neg = 0 ;
c−>s = 0 ;
10 c−>t = g−>qtdVert ;
for ( k = 0 ; k < g−>qtdVert ; k++)
for ( i = 0 ; i < g−>qtdVert ; i++)
for ( j = 0 ; j < g−>qtdVert ; j++)
i f ( ( g−>matriz [ i ] [ k ] . peso + g−>matriz [ k ] [ j ] . peso ) < g−>
matriz [ i ] [ j ] . peso ) {
15 g−>matriz [ i ] [ j ] . peso = g−>matriz [ i ] [ k ] . peso + g−>
matriz [ k ] [ j ] . peso ;
pred [ i ] [ j ] = pred [ k ] [ j ] ;
}
c−>qtdTotal = g−>qtdVert ;
for ( k = c−>s ; k < c−>t ; k++) {
20 c [ k ] . r e su l t ado = ( TPasseio ∗) c a l l o c ( c−>qtdTotal , s izeof (
TPasseio ) ) ;
for ( i = c−>s ; i < c−>t ; i++) {
c [ k ] . r e su l t ado [ i ] .TP = ( int ∗) c a l l o c ( c−>qtdTotal , s izeof (
int ) ) ;
i f ( i == k)
continue ;
25 c [ k ] . r e su l t ado [ i ] .TP[ 0 ] = g−>matriz [ k ] [ i ] . peso ;
c [ k ] . r e su l t ado [ i ] . qtdNos = 1 ;
pos = 1 ;
aux = pred [ k ] [ i ] ;
while ( ( aux != i ) && ( aux != k) ) {
20
30 c [ k ] . r e su l t ado [ i ] . qtdNos++;
c [ k ] . r e su l t ado [ i ] .TP[ pos++] = aux ;
aux = pred [ k ] [ aux ] ;
}
}
35 }
f r e e ( pred [ 0 ] ) ;
f r e e ( pred ) ;
return c ;
}
Programa 20: Função floydP
2.5.2 Função floyd
Análogo a Função floydP 2.5.1, porém sem geração de caminhos e ainda dois
pontos importantes:
• Matriz de Distâncias: criamos uma matriz auxiliar que é alocada somente
uma única vez e desalocada somente no final das n execuções, porém sempre
que é executada, inicializamos a matriz de modo que fique de acordo com a
especificação proposta pelo trabalho e ainda com código mais otimizado.
• Matriz de Predecessores: Optamos por reutilizá-la, porém reiniciando-a na
Função �mainF� 2.5.6 a cada execução. A função responsável por alocar e /
ou inicialização do �Pred� pode ser conferida na Seção 2.4.4. Vale lembrar que
a cada execução a matriz de predecessores é reinicializada, logo está de acordo
com a especificação proposta pelo trabalho e ainda mais otimizado.
void f l oyd (TGrafo∗ g , TVertice ∗∗ auxMatriz , int ∗∗ pred ) {
int k , i , j ;
for ( i = 0 ; i < g−>qtdVert ; i++)
for ( j = 0 ; j < g−>qtdVert ; j++)
5 auxMatriz [ i ] [ j ] = g−>matriz [ i ] [ j ] ;
for ( k = 0 ; k < g−>qtdVert ; k++) {
for ( i = 0 ; i < g−>qtdVert ; i++)
for ( j = 0 ; j < g−>qtdVert ; j++)
i f ( ( auxMatriz [ i ] [ k ] . peso + auxMatriz [ k ] [ j ] . peso ) <
auxMatriz [ i ] [ j ] . peso ) {
10 auxMatriz [ i ] [ j ] . peso = auxMatriz [ i ] [ k ] . peso +
auxMatriz [ k ] [ j ] . peso ;
pred [ i ] [ j ] = pred [ k ] [ j ] ;
}
}
}
Programa 21: Função floyd
2.5.3 Função floydPNeg
Função responsável por calcular a distância e predecessores de todos os vértices
do grafo negativo, utilizando o Algoritmo de Floyd Warshall, note que assim como
o Programa20 não é preciso reinicializar a matriz de adjacências bem como a de
21
predecessores uma vez que quando passarmos ao programa a flag 1 de impressão o
programa executará somente uma única vez. Logo, bastará somente inicializá-la.
Como o grafo é negativo (contém ciclos com pesos negativos), então será necessário
sair da execução do algoritmo de Warshall e identificar o ciclo de peso negativo,
gerando o caminho desse ciclo para futura impressão em arquivo. Isso é feito de
modo análogo à geração de caminho da Seção 2.5.1, mas, para isso, bastará percor-
rer e gerar o caminho da posição da matriz que foi identificado o ciclo negativo, ou
seja, a posição de uma das diagonais principais da matriz de adjacências do grafo.
Obs.: Para contornar a condição de parada do programa para ciclos negativos,
incrementamos uma unidade na quantidade da posição em que a matriz sua diagonal
principal foi modificada, isso somente para a representação do vértice final.
Para uma ilustração da geração dos caminhos veja a Figura 14. Vide Programa
22
Caminho∗ floydPNeg (TGrafo∗ g ) {
int k , i , j , aux , n = 0 , pos ;
Caminho∗ c ;
int ∗∗ pred ;
5 pred = NULL;
pred = in i c i aP r ed ( pred , &(g−>qtdVert ) ) ;
c = (Caminho∗) mal loc ( g−>qtdVert ∗ s izeof (Caminho ) ) ;
c−>neg = 0 ;
c−>s = 0 ;
10 c−>t = g−>qtdVert ;
for ( k = 0 ; k < g−>qtdVert ; k++) {
for ( i = 0 ; i < g−>qtdVert ; i++)
for ( j = 0 ; j < g−>qtdVert ; j++) {
i f ( ( g−>matriz [ i ] [ k ] . peso + g−>matriz [ k ] [ j ] . peso ) < g−>
matriz [ i ] [ j ] . peso ) {
15 g−>matriz [ i ] [ j ] . peso = g−>matriz [ i ] [ k ] . peso + g−>
matriz [ k ] [ j ] . peso ;
pred [ i ] [ j ] = pred [ k ] [ j ] ;
i f ( g−>matriz [ i ] [ i ] . peso < 0) {
c−>neg = 1 ;
c−>s = i ;
20 c−>t = i + 1 ;
goto NEG;
}
}
}
25 }
NEG:
c−>qtdTotal = g−>qtdVert ;
for ( k = c−>s; k < c−>t ; k++) {
c [ k ] . r e su l t ado = ( TPasseio ∗) c a l l o c ( c−>qtdTotal , s izeof (
TPasseio ) ) ;
30 for ( i = c−>s ; i < c−>t ; i++) {
c [ k ] . r e su l t ado [ i ] .TP = ( int ∗) c a l l o c ( c−>qtdTotal , s izeof (
int ) ) ;
c [ k ] . r e su l t ado [ i ] .TP[ 0 ] = g−>matriz [ k ] [ i ] . peso ;
c [ k ] . r e su l t ado [ i ] . qtdNos = 1 ;
pos = 1 ;
35 aux = pred [ k ] [ i ] ;
while ( ( aux != i ) && ( aux != k) ) {
c [ k ] . r e su l t ado [ i ] . qtdNos++;
c [ k ] . r e su l t ado [ i ] .TP[ pos++] = aux ;
22
aux = pred [ k ] [ aux ] ;
40 }
}
}
f r e e ( pred [ 0 ] ) ;
f r e e ( pred ) ;
45 return c ;
}
Programa 22: Função floydPNeg
2.5.4 Função floydNeg
Análogo a Função �floydPNeg� 2.5.3, porém sem geração de caminhos e ainda
com o mesmo ponto importante da Seção 2.5.2.
void f loydNeg (TGrafo∗ g , TVertice ∗∗ auxMatriz , int ∗∗ pred ) {
int k , i , j ;
for ( i = 0 ; i < g−>qtdVert ; i++)
for ( j = 0 ; j < g−>qtdVert ; j++)
5 auxMatriz [ i ] [ j ] = g−>matriz [ i ] [ j ] ;
for ( k = 0 ; k < g−>qtdVert ; k++)
for ( i = 0 ; i < g−>qtdVert ; i++)
for ( j = 0 ; j < g−>qtdVert ; j++)
i f ( ( auxMatriz [ i ] [ k ] . peso + auxMatriz [ k ] [ j ] . peso ) <
auxMatriz [ i ] [ j ] . peso ) {
10 auxMatriz [ i ] [ j ] . peso = auxMatriz [ i ] [ k ] . peso +
auxMatriz [ k ] [ j ] . peso ;
pred [ i ] [ j ] = pred [ k ] [ j ] ;
i f ( auxMatriz [ i ] [ i ] . peso < 0) {
return ;
}
15 }
}
Programa 23: Função floydNeg
2.5.5 Função imprimirsalvar
Função utilizada para impressão dos resultados, isto é, distância e peso de todos
os vértices para os demais vértices do grafo bem como o caminho entres os vértices
de início e final.
Obs.: Como os caminhos de cada vértice são acessados e armazenados em ordem
inversa a impressão dos caminhos é feita em ordem inversa para que os caminhos de
saída estejam na ordem correta. Um exemplo dessa geração de caminhos pode ser
vista na Figura 5. Vide Programa 24
void imprimir_salvar (Caminho∗ c ) {
FILE∗ arqS ;
int i , j , k ;
arqS = fopen (" spa th s . t x t " , "w" ) ;
5 i f ( ! arqS ) {
p r i n t f ("Erro ao e s c r e v e r no arqu ivo " ) ;
return ;
}
i f ( c−>neg )
23
10 f p r i n t f ( arqS , "Cic lo Negat ivo \n" ) ;
for ( k = c−>s ; k < c−>t ; k++) {
for ( i = c−>s ; i < c−>t ; i++) {
i f ( ! c−>neg )
i f ( ( k == i ) | | ( c [ k ] . r e su l t ado [ i ] .TP[ 0 ] == INF) )
15 continue ;
f p r i n t f ( arqS , "[%d,%d](%d)" , k + 1 , i + 1 , c [ k ] . r e su l t ado [ i
] .TP[ 0 ] ) ;
f p r i n t f ( arqS , " %d" , k + 1) ;
for ( j = c [ k ] . r e su l t ado [ i ] . qtdNos − 1 ; j >= 1 ; j−−)
f p r i n t f ( arqS , " %d" , c [ k ] . r e su l t ado [ i ] .TP[ j ] + 1) ;
20 f p r i n t f ( arqS , " %d\n" , i + 1) ;
}
f p r i n t f ( arqS , "\n" ) ;
}
}
Programa 24: Função imprimirsalvar
2.5.6 Função mainF
Função Main do programa responsável por chamar as demais funções.
Note que novamente fizemos uso do Loop Unrolling para aproveitarmos melhor
o uso do Pipeline do processador[4].
Vide Programa 25.
#include " s t d a f x . h"
#include <time . h>
#include "TGrafoF . h"
int main ( int argc , char∗∗ argv ) {
5
int f lagDepuracao , nrExecucao , vertRand ;
TGrafo g ;
Caminho∗ c ;
TVertice ∗∗ auxMatriz ;
10 int ∗∗ pred ;
pred = NULL;
i f ( argc < 3) {
p r i n t f ("Confira o numero de parametros " ) ;
return (EXIT_FAILURE) ;
15 }
srand (0 ) ;
f lagDepuracao = a t o i ( argv [ 3 ] ) ;
nrExecucao = a to i ( argv [ 2 ] ) ;
g = cria_grafo_por_nome ( argv [ 1 ] ) ;
20 i f ( g . qtdVert == −1) {
p r i n t f ("\n∗∗Erro ao c r i a r o gra fo " ) ;
return (EXIT_FAILURE) ;
}
auxMatriz = NULL;
25 auxMatriz = alocaMatr i z ( auxMatriz , &(g . qtdVert ) ) ;
switch ( g . ehc i c loNeg ) {
case 0 :
switch ( f lagDepuracao ) {
30 case 0 :
switch ( nrExecucao % 4) {
24
case 0 :
while ( nrExecucao ) {
pred = in i c i aP r ed ( pred , &(g . qtdVert ) ) ;
35 f l o yd (&g , auxMatriz , pred ) ;
nrExecucao−−;
pred = in i c i aP r ed ( pred , &(g . qtdVert ) ) ;
f l oyd (&g , auxMatriz , pred ) ;
40 nrExecucao−−;
pred = in i c i aP r ed ( pred , &(g . qtdVert ) ) ;
f l oyd (&g , auxMatriz , pred ) ;
nrExecucao−−;
45
pred = in i c i aP r ed ( pred , &(g . qtdVert ) ) ;
f l oyd (&g , auxMatriz , pred ) ;
nrExecucao−−;
}
50 break ;
case 2 :
{
while ( nrExecucao ) {
pred = in i c i aP r ed ( pred , &(g . qtdVert ) ) ;
55 nrExecucao−−;
f l o yd (&g , auxMatriz , pred ) ;
pred = in i c i aP r ed ( pred , &(g . qtdVert ) ) ;
nrExecucao−−;
60 f l o yd (&g , auxMatriz , pred ) ;
}
break ;
}
65 default :
while ( nrExecucao−−) {
pred = in i c i aP r ed ( pred , &(g . qtdVert ) ) ;
f l oyd (&g , auxMatriz , pred ) ;
}
70 break ;
}
f r e e ( pred [ 0 ] ) ;
f r e e ( pred ) ;
break ;
75 case 1 :
c = floydP(&g ) ;
imprimir_salvar ( c ) ;
}
break ;
80 case 1 :
switch ( f lagDepuracao ) {
case 0 :
switch ( nrExecucao % 4) {
case 0 :
85 while ( nrExecucao ) {
pred = in i c i aP r ed ( pred , &(g . qtdVert ) ) ;
f loydNeg(&g , auxMatriz , pred ) ;
nrExecucao−−;
25
90 pred = in i c i aP r ed ( pred , &(g . qtdVert ) ) ;
f loydNeg(&g , auxMatriz , pred ) ;
nrExecucao−−;
pred = in i c i aP r ed ( pred , &(g . qtdVert ) ) ;
95 f loydNeg(&g , auxMatriz , pred ) ;
nrExecucao−−;
pred = in i c i aP r ed ( pred , &(g . qtdVert ) ) ;
f loydNeg(&g , auxMatriz , pred ) ;
100 nrExecucao−−;
}
break ;
case 2 :
{
105 while ( nrExecucao ) {
pred = in i c i aP r ed ( pred , &(g . qtdVert ) ) ;
nrExecucao−−;
f loydNeg(&g , auxMatriz , pred ) ;
110 pred = in i c i aP r ed ( pred , &(g . qtdVert ) ) ;
nrExecucao−−;
f loydNeg(&g , auxMatriz , pred ) ;
}
break ;
115 }
default :
while ( nrExecucao−−) {
pred = in i c i aP r ed ( pred , &(g . qtdVert ) ) ;
f loydNeg(&g , auxMatriz , pred ) ;
120 }
break ;
}
f r e e ( pred [ 0 ] ) ;
f r e e ( pred ) ;
125 break ;
case 1 :
c = floydPNeg(&g ) ;
imprimir_salvar ( c ) ;
}
130 }
i f ( f lagDepuracao )
f r e e ( c ) ;
f r e e ( auxMatriz [ 0 ] ) ;
f r e e ( auxMatriz ) ;
135 return 0 ;
}
Programa 25: Função mainF
26
3 Testes
3.1 Exemplo de teste para o Floyd-Warshall
Para uma simples conferência e facilidade na implementação foram elaborados
2 (dois) grafos de teste para o Floyd-Warshall, sendo um deles com peso negativo,
vide 3.1.2, e outro com peso positivo, vide 3.1.1.
3.1.1 Grafo com Peso Positivo
Vide na Figura 2 a representação e um grafo com pesos positivos, a matriz de
distâncias de todos os vértices 3 e a matriz de predecessores dos vértices 4.
A Figura 5 ilustra a geração de caminho dos vértices 1→ 2 com peso 6, onde o
caminho gerado é: 1→ 3→ 4→ 2
Figura 2: Figura Grafo com Peso Positivos
Figura 3: Figura Matriz Dist
27
Figura 4: Figura Matriz Pred
Figura 5: Figura Exemplo de Caminho
28
3.1.2 Grafo com Peso Negativo
Vide na Figura 6 a representação e um grafo com peso negativo, a matriz de
distâncias de todos os vértices 7 e a matriz de predecessores dos vértices 8.
A Figura 14 ilustra a geração de caminho dos vértices 5→ 5 com peso -2, onde
o caminho gerado é: 5→ 4→ 1→ 2→ 5
Figura 6: Figura Grafo com Peso Negativo
Figura 7: Figura Matriz Dist
29
Figura 8: Figura Matriz Pred
Figura 9: Figura Exemplo de Caminho Neg
30
3.2 Testes em massa
Os testes foram realizados computacionalmente, programa demonstrado em 26,
dez vezes para cada valor de n execuções, com n = [1...9, 10, 20...90, 100, 200...1000].
Após isso é calculada a média dos tempos, o desvio padrão e a variância. Nos
gráficos estãomarcados pontos que representam intervalo de confiança dos tempos,
ou seja, a média menos a variância e a média mais a variância de cada determinada
quantidade de execução.
Cada gráfico representa dois testes, o método proposto na preliminar, em ver-
melho, e a nova implementação, em azul. Além dos pontos há uma reta que repre-
senta a tendência das médias.
3.2.1 Floyd-Warshall
rg300_768
Figura 10: Grafico para Floyd-Warshall sobre o grafo rg300_768
31
Como pode ser observado, todos os grafos que não possuem ciclos negativos no Floyd
Warshall tendem a ser mais rápidos. O que mostra que mesmo a matriz não sendo
reiniciada na versão preliminar, a nova implementação é ainda melhor.
rg300_4730
Figura 11: Grafico para Floyd-Warshall sobre o grafo rg300_4730
Como pode ser observado, o tempo do Floyd Warshall foi ligeiramente melhor na
otimização do que na versão das preliminares.
comp-2007-2-22c
32
Figura 12: Grafico para Floyd-Warshall sobre o grafo comp-2007-2-22c
33
Como pode ser observado no gráfico a nova versão por vezes é mais rápida. Isso
ocorre principalmente porque na versão preliminar não tratava duas vezes um ciclo
negativo, já que não reiniciava a matriz dos custos a cada nova interação.
3.2.2 Dijkstra
rome99c
Figura 13: Grafico para Dijkstra sobre o grafo rome99c
Dentre os testes realizados os resultados que mostraram maior diferença nos
tempos foi o Dijkstra. Com uma melhoria linear de, aproximadamente, cinco vezes
representa ainda uma estabilidade grande com grandes execuções, já que o intervalo
de confiança é estritamente pequeno( 0,02201 para 1000 execuções).
34
USA-road-d-NYc
Figura 14: Grafico para Dijkstra sobre o grafo USA-road-d-NYc
Sendo o USA-road-d.NYc.gr um grafo extremamente grande para a execução com a
implementação antiga, tendendo, segundo uma conta média de resultados, 2,5 dias
para mil execuções foi necessário para-lo após a execução de 30. Apesar de parecer
uma reta vertical a média dos resultados, cada valor de 1 à 30 foi computado e salvo.
Isso demonstra a grande melhoria do algoritmo.
35
4 Conclusão
O problema de caminhos mínimos, apesar de ser um problema NP-Completo,
há soluções ótimas com algoritmos relativamente rápidos para algumas instancias
e por vezes otimizações podem melhorar consideravelmente a função complexidade
deles, tal como o Dijkstra, que com a Heap de Fibonacci implementada para grafos
muito grandes torna-se mais rápido. Entretanto, como todos os algoritmos são ditos
�gulosos�, ou seja, não acham a solução ótima a princípio, ainda há muito a ser
pesquisado nesta área, partindo do princípio que a quantidade de aplicações deste
problema é inimaginável.
36
Referências
[1] John Mark Gurney. fib, 2003. http://resnet.uoregon.edu/~gurney_j/jmpc/
fib.html, acessado em 07/10/2010.
[2] David Menotti. Aula 19 ordenação iv heapsort, 2010. http://
www.decom.ufop.br/menotti/edI101/slides/aula-ORDHeapSort.ppt, aces-
sado em 22/09/2010.
[3] Rosane Minghim. Grafos parte 2, 2010. https://docs.google.com/viewer?
url=http://wiki.icmc.usp.br/images/5/5d/AlgII_Rosane_02_Grafos2.
pdf&pli=1, acessado em 01/10/2010.
[4] David A. Patterson and John L. hennessy. Computer Organization and Design.
Morgan Kaufmann Publishers, 4th edition, 2008.
[5] Haroldo Gambini Santos. Grafos com pesos - computando caminhos mínimos,
2010. http://grafos-ufop.googlegroups.com/web/grafos_04.pdf?gda=
Sx3MV0MAAACp509PEQE-F0yARdQXL36CtbRu5bCtxrbcvuUDlY-ViORczfpiWbs5z6OtNHg3VURtxVPdW1gYotyj7-X7wDONZeyzzuqDOUYJGTuqSocT1A,
acessado em 26/08/2010.
[6] Ronald L. Rivest Thomas H. Cormen, Charles E. Leiserson. Algoritmos: Teoria
e Prática. Editora Campus, segunda edição edition, 2002.
[7] the free encyclopedia Wikipedia. Fibonacci heap, 2010. http://en.wikipedia.
org/wiki/Fibonacci_heap, acessado em 24/09/2010.
[8] N. Ziviani. Projeto de Algoritmos: com implementações em Pascal e C. Cengage
Learning (Thomson / Pioneira), São Paulo, 1st edition, 2004.
37
Anexo
Este algoritmo gera um programa para executar os testes em massa para os
algoritmos Dijkstra e Floyd-Warshall
#include <s td i o . h>
#include <s t d l i b . h>
#include <s t r i n g . h>
#include <math . h>
5
int l eArquivo ( f loat ∗tempo , int ∗ i ) {
char ∗ tok ;
char ∗buf ;
10 FILE∗ arqE ;
int min ;
f loat seg ;
buf = (char∗) mal loc ( s izeof (char ) ∗BUFSIZ) ;
15 arqE = fopen (" l o g " , "r" ) ;
i f ( arqE == NULL) {
p r i n t f ("Erro ao a b r i r arqu ivo de entrada \n" ) ;
return 0 ;
20 }
buf = f g e t s ( buf , BUFSIZ , arqE ) ;
tok = s t r t ok ( buf , " : " ) ;
25 min = a to i ( tok ) ;
tok = s t r t ok (NULL, " : " ) ;
s s c an f ( tok , "%f " , &seg ) ;
tempo [∗ i ] = seg + min ∗ 60 ;
(∗ i )++;
30
f c l o s e ( arqE ) ;
return 1 ;
}
35 int e s t a t i s t i c a ( f loat ∗tempo , int ∗n , char∗ name) {
FILE∗ arqS ;
int i ;
double x , media , var ;
var=x=0;
40 arqS = fopen (name , "a+" ) ;
i f ( arqS == NULL) {
p r i n t f ("Erro ao a b r i r arqu ivo de sa ida \n" ) ;
return 0 ;
}
45 for ( i = 0 ; i <10; i++)
x += tempo [ i ] ;
media = x / 10 ;
for ( i = 0 ; i <10; i++)
var += pow( (double ) ( tempo [ i ] − media ) , 2) ;
50 var = sq r t ( var /9) ;
f p r i n t f ( arqS , "%d %l f \n" , (∗n) , media − var ) ;
f p r i n t f ( arqS , "%d %l f \n" , (∗n) , media + var ) ;
f f l u s h ( s td in ) ;
38
f c l o s e ( arqS ) ;
55 }
int main ( int argc , char∗∗ argv ) {
int n , i , j , k ;
60 char∗ s t r i n g ;
f loat ∗ tempo ;
int∗ pos ;
tempo = ( f loat ∗) c a l l o c (10 , s izeof ( f loat ) ) ;
s t r i n g = (char ∗) mal loc ( s izeof (char ) ∗150) ;
65 k = 0 ;
pos = ( int ∗) mal loc ( s izeof ( int ) ∗28) ;
for ( i = 1 ; i < 1000 ; i ∗= 10)
for ( j = 1 ; j < 10 ; j++)
pos [ k++] = i ∗ j ;
70 pos [ k ] = 1000 ;
for (n = 0 ; n < 28 ; n++) {
p r i n t f ("mÃ
c©todo: %s entrada : %s q td de execucoes : %d\n" , argv
[ 1 ] , argv [ 2 ] , pos [ n ] ) ;
k = 0 ;
75 for ( i = 0 ; i < 10 ; i++) {
s p r i n t f ( s t r i ng , "/usr / b in / time −o l o g −f %s ./%s input/%s
%d 0" ," %E " , argv [ 1 ] , argv [ 2 ] , pos [ n ] ) ;
system ( s t r i n g ) ;
l eArquivo ( tempo , &k) ;
}
80 e s t a t i s t i c a ( tempo , &(pos [ n ] ) , argv [ 3 ] ) ;
}
return 0 ;
85 }
Programa 26: Programa de Teste
39
	Introdução
	Considerações iniciais
	Especificações da máquina
	Especificação do problema
	Material a ser entregue
	Documentação impressa incluindo
	Regras de Implementação
	Problemas Teste
	Formato de Entrada e Saída e Parâmetros
	Dijkstra
	Heaps
	Aplicação do Algoritmo
	Versão Preliminar x Final
	Floyd-Warshall
	Aplicação do Algoritmo
	Versão Preliminar x Final
	Algoritmo e estruturas de dados
	Grafo do Dijkstra
	Função CriaGrafoPorNome
	Função ConstruindoLista
	Função AddInteração
	Heap Binária
	Inicialização da heap
	Remove menor
	Diminui
	Tamanho
	Dijkstra
	Função Dijkstra
	Função DijkstraP
	Função Main para o Dijkstra
	Grafo do Floyd-Warshall
	Função CriaGrafoPorNome
	Função alocaMatriz
	Função iniciaMatriz
	Função iniciaPred
	Floyd-Warshall
	Função floydP
	Função floyd
	Função floydPNeg
	Função floydNeg
	Função imprimirsalvar
	Função mainF
	Testes
	Exemplo de teste para o Floyd-Warshall
	Grafo com Peso Positivo
	Grafo com Peso Negativo
	Testes em massa
	Floyd-Warshall
	Dijkstra
	Conclusão