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 SantosVítor Mangaravite

Professor - Haroldo Gambini Santos

Ouro Preto

25 de outubro de 2010

Sumário

1 Introdução 11.1 Considerações iniciais . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2 Especi�cações da máquina . . . . . . . . . . . . . . . . . . . . . . . . 11.3 Especi�cação do problema . . . . . . . . . . . . . . . . . . . . . . . . 1

1.3.1 Material a ser entregue . . . . . . . . . . . . . . . . . . . . . . 11.3.2 Documentação impressa incluindo . . . . . . . . . . . . . . . . 21.3.3 Regras de Implementação . . . . . . . . . . . . . . . . . . . . 21.3.4 Problemas Teste . . . . . . . . . . . . . . . . . . . . . . . . . 21.3.5 Formato de Entrada e Saída e Parâmetros . . . . . . . . . . . 3

1.4 Dijkstra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.4.1 Heaps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.4.2 Aplicação do Algoritmo . . . . . . . . . . . . . . . . . . . . . 51.4.3 Versão Preliminar x Final . . . . . . . . . . . . . . . . . . . . 5

1.5 Floyd-Warshall . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.5.1 Aplicação do Algoritmo . . . . . . . . . . . . . . . . . . . . . 61.5.2 Versão Preliminar x Final . . . . . . . . . . . . . . . . . . . . 6

2 Algoritmo e estruturas de dados 72.1 Grafo do Dijkstra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

2.1.1 Função CriaGrafoPorNome . . . . . . . . . . . . . . . . . . . . 72.1.2 Função ConstruindoLista . . . . . . . . . . . . . . . . . . . . . 82.1.3 Função AddInteração . . . . . . . . . . . . . . . . . . . . . . . 9

2.2 Heap Binária . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92.2.1 Inicialização da heap . . . . . . . . . . . . . . . . . . . . . . . 102.2.2 Remove menor . . . . . . . . . . . . . . . . . . . . . . . . . . 112.2.3 Diminui . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112.2.4 Tamanho . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

2.3 Dijkstra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122.3.1 Função Dijkstra . . . . . . . . . . . . . . . . . . . . . . . . . . 122.3.2 Função DijkstraP . . . . . . . . . . . . . . . . . . . . . . . . . 132.3.3 Função Main para o Dijkstra . . . . . . . . . . . . . . . . . . . 14

2.4 Grafo do Floyd-Warshall . . . . . . . . . . . . . . . . . . . . . . . . . 152.4.1 Função CriaGrafoPorNome . . . . . . . . . . . . . . . . . . . . 162.4.2 Função alocaMatriz . . . . . . . . . . . . . . . . . . . . . . . . 172.4.3 Função iniciaMatriz . . . . . . . . . . . . . . . . . . . . . . . . 192.4.4 Função iniciaPred . . . . . . . . . . . . . . . . . . . . . . . . . 19

2.5 Floyd-Warshall . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202.5.1 Função �oydP . . . . . . . . . . . . . . . . . . . . . . . . . . . 202.5.2 Função �oyd . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212.5.3 Função �oydPNeg . . . . . . . . . . . . . . . . . . . . . . . . . 212.5.4 Função �oydNeg . . . . . . . . . . . . . . . . . . . . . . . . . 232.5.5 Função imprimirsalvar . . . . . . . . . . . . . . . . . . . . . . 232.5.6 Função mainF . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

2

3 Testes 273.1 Exemplo de teste para o Floyd-Warshall . . . . . . . . . . . . . . . . 27

3.1.1 Grafo com Peso Positivo . . . . . . . . . . . . . . . . . . . . . 273.1.2 Grafo com Peso Negativo . . . . . . . . . . . . . . . . . . . . . 29

3.2 Testes em massa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313.2.1 Floyd-Warshall . . . . . . . . . . . . . . . . . . . . . . . . . . 313.2.2 Dijkstra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

4 Conclusão 36

Lista de Figuras

1 Figura Repres. Alocação Matriz . . . . . . . . . . . . . . . . . . . . . 182 Figura Grafo com Peso Positivos . . . . . . . . . . . . . . . . . . . . 273 Figura Matriz Dist . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274 Figura Matriz Pred . . . . . . . . . . . . . . . . . . . . . . . . . . . . 285 Figura Exemplo de Caminho . . . . . . . . . . . . . . . . . . . . . . . 286 Figura Grafo com Peso Negativo . . . . . . . . . . . . . . . . . . . . . 297 Figura Matriz Dist . . . . . . . . . . . . . . . . . . . . . . . . . . . . 298 Figura Matriz Pred . . . . . . . . . . . . . . . . . . . . . . . . . . . . 309 Figura Exemplo de Caminho Neg . . . . . . . . . . . . . . . . . . . . 3010 Gra�co para Floyd-Warshall sobre o grafo rg300_768 . . . . . . . . . 3111 Gra�co para Floyd-Warshall sobre o grafo rg300_4730 . . . . . . . . 3212 Gra�co para Floyd-Warshall sobre o grafo comp-2007-2-22c . . . . . . 3313 Gra�co para Dijkstra sobre o grafo rome99c . . . . . . . . . . . . . . 3414 Gra�co para Dijkstra sobre o grafo USA-road-d-NYc . . . . . . . . . 35

Lista de Programas

1 Algoritmo Floyd Warshall C . . . . . . . . . . . . . . . . . . . . . . . 52 TAD Grafo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 Função CriaGrafoPorNome para o dijkstra . . . . . . . . . . . . . . . 74 Função ConstruindoLista . . . . . . . . . . . . . . . . . . . . . . . . . 85 Função ConstruindoLista . . . . . . . . . . . . . . . . . . . . . . . . . 96 TAD Grafo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 Criação da heap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 Inicialização da heap . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 Remove Menor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1110 Decrementa Chave . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1111 Tamanho . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1212 Fijkstra sem Impressão . . . . . . . . . . . . . . . . . . . . . . . . . . 1213 Dijkstra com Impressão . . . . . . . . . . . . . . . . . . . . . . . . . . 1314 Programa principal do Dijkstra . . . . . . . . . . . . . . . . . . . . . 1415 TAD Grafo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1616 Função criagrafopornome . . . . . . . . . . . . . . . . . . . . . . . . . 1617 Função alocaMatriz . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1918 Função iniciamatriz . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

3

19 Função iniciaPred . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1920 Função �oydP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2021 Função �oyd . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2122 Função �oydPNeg . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2223 Função �oydNeg . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2324 Função imprimirsalvar . . . . . . . . . . . . . . . . . . . . . . . . . . 2325 Função mainF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2426 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 haviasoluções disponíveis bem como para soluções rápidas para o mesmo problema.

Assim, cabe ao Cientista da Computação identi�car soluções para a resoluçãodos problemas, principalmente, tornando-os otimizados e rápidos. Através dessesconceitos coube ao grupo utilizar os conceitos de Teoria dos Grafos para a modelagemdo trabalho.

Na teoria de grafos, o problema do caminho mínimo consiste na minimização docusto de travessia de um grafo entre dois nós (ou vértices). Custo este dado pelasoma dos pesos de cada aresta percorrida.

Formalmente, dado um grafo valorado (ou seja, um conjunto V de vértices, umconjunto A de arestas e uma função de peso f : A→ R) e, dado qualquer elementov ∈ 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 LATEX, Editor dos grafos: R-2.12.0 for windows.

1.2 Especi�caçõ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 Especi�caçã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 -�ast-math). Devem ser oferecidas as seguintes implementações:

• Algoritmo de Dijkstra para para computação de c.m. de uma fonte para todosos outros vértices;→ a fonte deve ser sorteada com a função rand a cada execução do algoritmode Dijkstra dentro do programa.

1

• Algoritmo Floyd-Warshall (FW) para computação dos caminhos mínimos detodos os vértices para todos os outros do grafo;→ a implementação de FW deve incluir um teste para a existência de ciclos decusto negativo no grafo. Caso um seja encontrado, o algoritmo deve concluirimediatamente sua execução e indicar o ciclo encontrado.

1.3.2 Documentação impressa incluindo

• explicação da implementação, incluindo referências bibliográ�cas;

• 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, excetoa 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 �ag-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 Testarrome99c.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 umcaminho ó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 devesomente 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 linhade 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 �nal irá imprimir/salvar informação dedepuraçã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 paracada par de vértices (s,t), sendo s diferente de t . Cada linha contém a informaçãosobre 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ósintermediários no formato: s n2 n3 ... t

1.4 Dijkstra

O algoritmo de dijkstra para caminhos mínimos foi feito por Edsger W. Dijkstraem 1956 e foi publicado em 1959. Este algoritmo é um algoritmo de busca emgrafos que resolve o problema de caminhos mínimos para grafos sem ciclos de custonegativo [5].

O algoritmo de dijkstra é um algoritmo guloso, pois toma uma decisão queparece ser a melhor no momento. Dado um nó fonte ele calcula o caminho demenor distancia deste nó a todos os outros. Ele funciona semelhante ao BFS, porémtrata grafos com peso. Ele trata os nós mais próximos da fonte primeiro, porémessa proximidade se refere ao peso entre as arestas e não ao número de arestaspercorridas. 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á osanteriores de cada nó no caminho da fonte até ele. Além disso é necessária umaheap para saber a ordem de processamento dos nós.

Ao inicio da execução do algoritmo o vetor de distancias é inicializado com in�nitopara 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�. Enquantoainda há nós na �heap� retira-se o menor vértice (u) e, para cada vizinho v vérticeveri�ca 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çõessobre a �heap�, portanto uma escolha errada de �heap� pode causar ine�ciência doalgoritmo.

1.4.1 Heaps

Heaps são �las 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 �lhos[2], e a heap de mínimo que é utilizada noalgoritmo de dijkstra, em que cada nó x pai sempre é menor que todos seus �lhos.

As heaps para o dijkstra possuem como chave os valores de distancia do vérticefonte até os respectivos nós. A medida que a distancia encontrada diminui para cadanó, sua prioridade aumenta e sua vez de ser processado se aproxima, con�gurandouma 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 �nal foi feita uma tentativa de implementação da heap de �bonacci[7].

As heaps de �bonacci são coleções de árvores ordenadas como heaps mínimos[6]. Asheaps de �bonacci 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 listade �lhos que também pode ter seus �lhos, assim em diante. A heap também temum ponteiro para o menor nó da lista.

A inserção na heap de �bonacci apenas insere o novo nó na lista de raízes. Ainserção veri�ca se o novo nó é menor que o menor atual, caso seja o menor passa aser 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 dalista de raízes e todos seus �lhos são inseridos na lista de raízes. Depois a heap éconsolidada, o que signi�ca que todas as raízes terão grau (numero de �lhos na lista)diferente. Caso haja mais de um nó com um certo grau, o maior deles vira �lho dooutro. A menor das raízes passa a ser o novo �min�. O custo amortizado da funçãode extração de menor é O(logn).

A diminuição da chave pode fazer com que um �lho �que 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 �lho de outro nó e já tenha perdido um �lho sendo�lho desde que virou �lho 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 �lhos. Seo nó decrementado for menor que a raiz, este passará a ser o novo minimo. O custoamortizado desta função é O(1).

As heaps de �bonacci possuem uma estrutura muito complexa, contendo listascirculares duplamente encadeadas. Isso di�cultou bastante a implementação nãopermitindo 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, seuirmão da direita e todos seus �lhos. Acredita-se que essas heaps poderiam melhorarainda mais o algoritmo do dijkstra devido à sua boa complexidade. Com as heapsbinarias a ordem de complexidade do dijkstra se aproxima muito de O(n2logn), comheaps de �bonacci 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 seuvértice no grafo, índice esse que é usado para a identi�cação da distancia do nó novetor �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 saberqual nó da heap foi alterado de inicio foi feita uma busca linear O(n) em todo ovetor da heap, versão que foi enviada na preliminar da competição.

Para a versão �nal 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 seutamanho máximo (n), foi possível fazer um hash mínimo perfeito. Para isso foi criadoum 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 detodos os vértices do grafo para todos os demais, recebendo, para isso, uma matrizde adjacências representando o grafo.

Com ordem de complexidade cúbica assume que para percorrer o caminho A→ Chaverá 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 aosubconjunto 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 porum autômato �nito (algoritmo de Kleene);

• Inversões de matrizes de números reais (algoritmo de Gauss-Jordan);

• Roteamento otimizado. Nesta aplicação, o objetivo é encontrar o caminhocom o máximo �uxo entre dois vértices. Isto signi�ca que, em vez de calcularo 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 asmatrizes de distâncias e dos predecessores não eram reinicializadas quando ousuá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 haviaimpressão ou quando o número de execuções fosse superior a 1 (um).

• Final: Para melhorar o desempenho bem como corrigir o problema anterioralocamos tanto a matriz de distâncias quanto a dos predecessores antes dechamar a função do algoritmo Floyd-Warshall e desalocando no �nal da ex-ecução de todo o programa, assim possibilitou em um ganho de desempenhoquando levarmos em consideração a alocação das matrizes.

Um ponto importante a ser citado é que mesmo não alocando e desalocando atodo execução sempre reinicializamos as duas matrizes. Isso pode ser percebidono 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 veri�cava se havia ou não ciclos negativosno grafo.

6

• Final: Para otimizar o tratamento de ciclos negativos foi incluída na estrutura15 do grafo uma variável ehcicloNeg que veri�ca na entrada de arquivos, videPrograma 16, se no grafo continha ou não peso negativo. Através dessa veri-�cação, para otimizar, criamos diferentes funções para o algoritmo de Floyd-Warshall, sendo para grafos com ciclos negativos: �oydPNeg, �oydNeg, videProgramas 22, 23 respectivamente .

E para positivos: �oydP, �oyd, vide Programas 20, 21 respectivamente. Nessasfunções não realizamos a veri�cação para caso haja ciclo negativo uma vez queo 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ênciasapresentada 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 apartir de um arquivo .txt e iniciar a lista de adjacências bem como instanciar a listacom 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ênciaspara 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 origemda 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 queseus �lhos. Para representar a heap há duas estruturas possíveis, lista encadeadacom ponteiros para os dois �lhos e lista simples utilizando um vetor[8]. Na imple-mentação foi utilizada a segunda estrutura por ser mais simples de trabalhar. VidePrograma 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�lhos 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 valorespara 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 refazero 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 �lhos. A ordem de complexidadeda inserção é O(logn)[8]. Para o caso do dijkstra todos os nós são inseridos na heaplogo no começo, para isso existe a função constrói que considera que as n/2 últimasposições do vetor já estão na heap, já que nenhuma posição representa o pai de outrajá que i é pai de 2∗i+1 e 2∗i+2 e i é pai de n+1 e n+2, para i = n/2. Considerandoisso os n/2 primeiros nós são inseridos na heap pela função �reconstrói� que veri�caa propriedade da heap, trocando o pai com seu menor �lho, caso o �lho seja menorque o pai. Na teoria são feitas n/2 inserções na heap, o que gera uma complexidadeO(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 ultimoelemento válido do vetor, que será a folha extrema direita da árvore. Após isso aheap é refeita com a função �reconstrói� desconsiderando a posição onde estava oultimo. 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�, afunção apenas veri�ca se o elemento com chave alterada fere a propriedade da heape o troca com seu pai em caso a�rmativo. Isso é feito até que a propriedade volte aser 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 veri�car a existenciade 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 semimpressã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 s t ) ;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 decaminho. 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 dodijkstra. 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 aproveitarmosmelhor o uso do Pipeline do processador[4], ganhando uma leve melhora no tempode 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 temosuma variável ehcicloNeg para a veri�cação se o grafo é negativo ou não bem comoqtdVert, 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 servisto facilmente no Programa 15.

Além de calcular a distância e a matriz de predecessores, para a impressão doscaminhos de todos os vértices para todos os demais, foi preciso utilizar a estruturaCaminho, onde qtdTotal, neg, s, t representam a quantidade total de vértices dografo, veri�cação se o grafo é ou não negativo para a geração do caminho de ciclonegativo, s e t os vértices de início e �nal do grafo, respectivamente. E, ainda, oresultado contendo a quantidade de vértices que fazem parte do caminho gerado e opróprio caminho de um vértice A para um vértice B. Isso pode ser visto na Figura5

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 comtodos os pesos do grafo de um vértice A para um vértice B. E é claro, veri�car paratodos os vértices do grafo, durante a inserção, se o grafo contém aresta com pesonegativo.

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 complexidadequadrática, no entanto, para otimizar o código �zemos em ordem de complexidadelinear. Para isso foi preciso alocar a matriz com a quantidade de linhas da matriz deadjacê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 paraa �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], ouseja, 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. VidePrograma 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 �oydP

Função responsável por calcular a distância e predecessores de todos os vérticesdo grafo positivo, utilizando o Algoritmo de Floyd Warshall, note que não é precisoreinicializar a matriz de adjacências bem como a de predecessores uma vez quequando passarmos ao programa a �ag 1 de impressão o programa executará somenteuma única vez.

Para uma ilustração da geração dos caminhos veja a Figura 5. Vide Programa20

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 �oydP

2.5.2 Função �oyd

Análogo a Função �oydP 2.5.1, porém sem geração de caminhos e ainda doispontos importantes:

• Matriz de Distâncias: criamos uma matriz auxiliar que é alocada somenteuma única vez e desalocada somente no �nal das n execuções, porém sempreque é executada, inicializamos a matriz de modo que �que de acordo com aespeci�cação proposta pelo trabalho e ainda com código mais otimizado.

• Matriz de Predecessores: Optamos por reutilizá-la, porém reiniciando-a naFunçã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 quea cada execução a matriz de predecessores é reinicializada, logo está de acordocom a especi�caçã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 �oyd

2.5.3 Função �oydPNeg

Função responsável por calcular a distância e predecessores de todos os vérticesdo grafo negativo, utilizando o Algoritmo de Floyd Warshall, note que assim comoo Programa20 não é preciso reinicializar a matriz de adjacências bem como a de

21

predecessores uma vez que quando passarmos ao programa a �ag 1 de impressão oprograma executará somente uma única vez. Logo, bastará somente inicializá-la.

Como o grafo é negativo (contém ciclos com pesos negativos), então será necessáriosair da execução do algoritmo de Warshall e identi�car o ciclo de peso negativo,gerando o caminho desse ciclo para futura impressão em arquivo. Isso é feito demodo 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 identi�cado o ciclo negativo, ouseja, 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 diagonalprincipal foi modi�cada, isso somente para a representação do vértice �nal.

Para uma ilustração da geração dos caminhos veja a Figura 14. Vide Programa22

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 �oydPNeg

2.5.4 Função �oydNeg

Análogo a Função ��oydPNeg� 2.5.3, porém sem geração de caminhos e aindacom 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 �oydNeg

2.5.5 Função imprimirsalvar

Função utilizada para impressão dos resultados, isto é, distância e peso de todosos vértices para os demais vértices do grafo bem como o caminho entres os vérticesde início e �nal.

Obs.: Como os caminhos de cada vértice são acessados e armazenados em ordeminversa a impressão dos caminhos é feita em ordem inversa para que os caminhos desaída estejam na ordem correta. Um exemplo dessa geração de caminhos pode servista 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 �zemos 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 elaborados2 (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 dedistâ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 ocaminho 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 dedistâ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, ondeo 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. Nosgrá�cos estão marcados pontos que representam intervalo de con�ança dos tempos,ou seja, a média menos a variância e a média mais a variância de cada determinadaquantidade de execução.

Cada grá�co 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: Gra�co para Floyd-Warshall sobre o grafo rg300_768

31

Como pode ser observado, todos os grafos que não possuem ciclos negativos no FloydWarshall tendem a ser mais rápidos. O que mostra que mesmo a matriz não sendoreiniciada na versão preliminar, a nova implementação é ainda melhor.

rg300_4730

Figura 11: Gra�co para Floyd-Warshall sobre o grafo rg300_4730

Como pode ser observado, o tempo do Floyd Warshall foi ligeiramente melhor naotimização do que na versão das preliminares.

comp-2007-2-22c

32

Figura 12: Gra�co para Floyd-Warshall sobre o grafo comp-2007-2-22c

33

Como pode ser observado no grá�co a nova versão por vezes é mais rápida. Issoocorre principalmente porque na versão preliminar não tratava duas vezes um ciclonegativo, já que não reiniciava a matriz dos custos a cada nova interação.

3.2.2 Dijkstra

rome99c

Figura 13: Gra�co para Dijkstra sobre o grafo rome99c

Dentre os testes realizados os resultados que mostraram maior diferença nostempos foi o Dijkstra. Com uma melhoria linear de, aproximadamente, cinco vezesrepresenta ainda uma estabilidade grande com grandes execuções, já que o intervalode con�ança é estritamente pequeno( 0,02201 para 1000 execuções).

34

USA-road-d-NYc

Figura 14: Gra�co 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 aimplementação antiga, tendendo, segundo uma conta média de resultados, 2,5 diaspara mil execuções foi necessário para-lo após a execução de 30. Apesar de pareceruma 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 instanciase por vezes otimizações podem melhorar consideravelmente a função complexidadedeles, tal como o Dijkstra, que com a Heap de Fibonacci implementada para grafosmuito 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 serpesquisado nesta área, partindo do princípio que a quantidade de aplicações desteproblema é inimaginável.

36

Referências

[1] John Mark Gurney. �b, 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. CengageLearning (Thomson / Pioneira), São Paulo, 1st edition, 2004.

37

Anexo

Este algoritmo gera um programa para executar os testes em massa para osalgoritmos 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