Relatório do Trabalho Prático 1 - Técnicas de Busca e Ordenação 2025/2

Título: Cálculo de Caminhos Mínimos com Algoritmo de Dijkstra Data: 07/01/2026

---

1. Identificação do Grupo

• Aluno 1: Paulo Sérgio Amorim Mônico - 2024102678 - paulo.monico@edu.ufes.br
• Aluno 2: Vitor Soprani Passamani - 2024102710 - vitor.passamani@edu.ufes.br

---

2. Introdução

Este relatório documenta o desenvolvimento e análise do Trabalho Prático 1. O objetivo é implementar e comparar abordagens para o cálculo de caminhos mínimos em grafos direcionados com pesos positivos (representando uma rede logística), utilizando o Algoritmo de Dijkstra.

---

3. Detalhes de Implementação

O projeto exige duas implementações distintas do algoritmo de Dijkstra e uma melhoria prática.

3.1. Implementação 1: Dijkstra com Heap Binário

Esta versão utiliza uma estrutura de Heap Binário (Fila de Prioridade) para gerenciar a seleção do vértice com menor custo acumulado.

• Estruturas de Dados (TADs):
  • Grafo (com lista encadeada de vértices), Heap Mínimo
• Complexidade Teórica:
  • Tempo (inicialização): $O(|V|^2)$
  • Tempo (dijkstra): $O((|V| + |E|) \log |V|)$
  • Espaço (grafo): $O(|V| + |E|)$

3.2. Implementação 2: Dijkstra com Heap Fibonacci

Esta versão utiliza uma estrutura de Heap Fibonacci para a fila de prioridade.

• Abordagem Escolhida:
  • Foi utilizado um heap fibonacci (uma floresta com árvores heap-orderd onde cada árvore possui um número de filhos (grau) diferente) para implementar a fila de prioridade.
• Justificativa:
• • Essa abordagem foi utilizada pois, apesar de apresentar uma grande complexidade na implementação, teoricamente possui um desempenho melhor do que o heap binário comum.
• Complexidade Teórica (amortizada) das operações do heap fibonacci:
• • Insert: Θ(1);
• • Extract_Min: O(lg(n));
• • Decrease_Key: Θ(1);
• Perceba que, em grafos densos (i.e |E| proximo de |V|^2), a operação Decrease_Key será realizada um número de vezes muito maior do que a operação Extract_Min (que é realizada apenas uma vez para cada vértice), podendo levar a um ganho no desempenho;
• Ja para grafos esparsos, o uso do heap fibonacci não deve apresentar grandes diferenças no desempenho, podendo até apresentar uma certa queda devida ao overhead das operações.

3.3. Melhoria Prática

Uma otimização foi aplicada visando reduzir gargalos de desempenho identificados.

• Descrição da Melhoria:
  • Nossa melhoria prática foi desenvolver um outro programa que converte a entradado grafo no modo texto para o modo binário. Em seguida, executamos o algoritmo dos caminhos mínimos novamente mas passando uma flag que indica que o código espera a entrada no modo binário. A implementação utilizada na melhoria prática é a primeira.
• Justificativa (Gargalo Original):
  • Percebemos que o gargalo do programa é a leitura do grafo. A entrada padrão está no formato de lista de adjacências, o que prejudica a complexidade da inicialização da estrutura do grafo. Além disso, o IO é mais lento no modo texto, pois é preciso fazer parsing de string para tipos numéricos, por exemplo. Essa última problemática conseguiu ser mitigada substituindo ao máximo funções como fscanf por caminhamentos na string de linha utilizando ponteiros.
• Implementação:
  • Inicializa o grafo assim como na versão em modo texto
  • Começa a escrever o grafo em modo binário. O formato pode ser descrito da seguinte forma:
  • Os vértices já estão ordenados na ordem natural (nome + índice).
  • Salva o número de vértices e o índice do primeiro vértice para se realizar o algoritmo.
  • Para cada vértice, salva-se o tamanho da string do seu rótulo (considerando o \0), a string propriamente dita do seu rótulo, quantas arestas ele possui conexão (E), e em seguida E tuplas (inteiro, float) que são os índices e os pesos das arestas dos vértices que ele possui conexão.
• Complexidade Teórica:
  • Tempo (inicialização): $O(|V| + |E|)$
  • Tempo (dijkstra): $O((|V| + |E|) \log |V|)$
  • Espaço (grafo): $O(|V| + |E|)$

---

4. Análise Experimental e Resultados

4.1. Metodologia

• Ambiente de Teste:
  • CPU: Intel Core i5-1235U @ 4.40 GHz
  • RAM: 8GB
  • Kernel: Linux (6.18.3)
  • Distro: Arch Linux
  • Shell: ZSH (5.9)
  • Compilador: GCC
• Ferramentas: comando interno time (para tempo de execução), valgrind (para verificação de memória).
• Medições: Consideramos o tempo total (user + kernel mode). Foi realizado uma média de 10 runs para medir o tempo. Para medir o uso de memória, foi utilizado apenas uma run devido à lentidão do valgrind. As medições foram feitas sem utilizar flags de otimizaçao como -O3 (apenas as otimizações padrões do GCC).
• Script para medição de tempo: time ./trab1 <caso> <saida> ; sleep 2. sleep 2 ajuda a não sobrecarregar o processador com execuções uma depois da outra e evitar spikes nas runs. Considerando que a execução aconteceu num notebook com sistema de resfriamento muito limitado, achamos que é justificável essa abordagem.

4.2. Resultados Quantitativos

Implementação 1: Dijkstra com Heap Binário

Caso de Teste	Qtd. Vértices (|V|)	Média do Tempo de Execução (s)	Memória (Bytes)
caso_teste_muito_pequeno_1.txt	5	0,0040	9.959
caso_teste_muito_pequeno_2.txt	8	0,0036	10.659
caso_teste_pequeno_1.txt	100	0,0077	169.646
caso_teste_pequeno_2.txt	100	0,0076	170.734
caso_teste_pequeno_3.txt	1.000	0,1040	15.319.714
caso_teste_pequeno_4.txt	1.000	0,1059	15.326.082
caso_teste_medio_1.txt	5.000	2,2636	381.245.538
caso_teste_medio_2.txt	5.000	2,2705	381.266.562
caso_teste_medio_3.txt	5.000	2,2475	381.262.242
caso_teste_medio_4.txt	6.000	4,0007	549.003.266

Observação: mesmo com sleep 2. Aconteceu muitos spikes no caso_teste_medio_4. Segue o detalhamento de cada run:

./trab1 casos_teste_v3/caso_teste_medio_4.txt saida.txt  2,93s user 0,32s system 99% cpu 3,250 total
./trab1 casos_teste_v3/caso_teste_medio_4.txt saida.txt  2,88s user 0,32s system 99% cpu 3,205 total
./trab1 casos_teste_v3/caso_teste_medio_4.txt saida.txt  2,91s user 0,32s system 99% cpu 3,235 total
./trab1 casos_teste_v3/caso_teste_medio_4.txt saida.txt  2,89s user 0,35s system 99% cpu 3,249 total
./trab1 casos_teste_v3/caso_teste_medio_4.txt saida.txt  2,87s user 0,33s system 99% cpu 3,199 total
./trab1 casos_teste_v3/caso_teste_medio_4.txt saida.txt  5,64s user 0,52s system 99% cpu 6,174 total
./trab1 casos_teste_v3/caso_teste_medio_4.txt saida.txt  3,88s user 0,34s system 99% cpu 4,237 total
./trab1 casos_teste_v3/caso_teste_medio_4.txt saida.txt  2,87s user 0,35s system 99% cpu 3,222 total
./trab1 casos_teste_v3/caso_teste_medio_4.txt saida.txt  3,06s user 0,31s system 99% cpu 3,383 total
./trab1 casos_teste_v3/caso_teste_medio_4.txt saida.txt  5,10s user 0,48s system 99% cpu 5,612 total

Implementação 2: Dijkstra com Heap Fibonacci

Caso de Teste	Qtd. Vértices (|V|)	Média do Tempo de Execução (s)	Memória (Bytes)
caso_teste_muito_pequeno_1.txt	5	0,0042	10,795
caso_teste_muito_pequeno_2.txt	8	0,0038	12,327
caso_teste_pequeno_1.txt	100	0,0088	196,518
caso_teste_pequeno_2.txt	100	0,0074	197,606
caso_teste_pequeno_3.txt	1.000	0,1083	15,676,906
caso_teste_pequeno_4.txt	1.000	0,1083	15,678,666
caso_teste_medio_1.txt	5.000	2,4299	383,330,746
caso_teste_medio_2.txt	5.000	2,2668	383,371,482
caso_teste_medio_3.txt	5.000	2,2440	383,341,050
caso_teste_medio_4.txt	6.000	4,3788	551,524,79

Observação: mais uma vez aconteceu vários spikes no caso_teste_medio_4. Segue o detalhamento de cada run:

./trab1 casos_teste_v3/caso_teste_medio_4.txt saida.txt  2,86s user 0,41s system 99% cpu 3,295 total
./trab1 casos_teste_v3/caso_teste_medio_4.txt saida.txt  2,86s user 0,31s system 99% cpu 3,173 total
./trab1 casos_teste_v3/caso_teste_medio_4.txt saida.txt  5,66s user 0,46s system 99% cpu 6,142 total
./trab1 casos_teste_v3/caso_teste_medio_4.txt saida.txt  5,13s user 0,45s system 99% cpu 5,600 total
./trab1 casos_teste_v3/caso_teste_medio_4.txt saida.txt  2,91s user 0,31s system 99% cpu 3,224 total
./trab1 casos_teste_v3/caso_teste_medio_4.txt saida.txt  5,51s user 0,49s system 99% cpu 6,021 total
./trab1 casos_teste_v3/caso_teste_medio_4.txt saida.txt  4,60s user 0,38s system 99% cpu 4,998 total
./trab1 casos_teste_v3/caso_teste_medio_4.txt saida.txt  3,00s user 0,31s system 99% cpu 3,313 total
./trab1 casos_teste_v3/caso_teste_medio_4.txt saida.txt  3,77s user 0,43s system 99% cpu 4,218 total
./trab1 casos_teste_v3/caso_teste_medio_4.txt saida.txt  3,39s user 0,40s system 99% cpu 3,804 total

Melhoria Prática

Caso de Teste (em binário)	Qtd. Vértices (|V|)	Média do Tempo de Execução (s)	Memória (Bytes)
caso_teste_muito_pequeno_1.txt	5	0,0039	9.971
caso_teste_muito_pequeno_2.txt	8	0,0037	10.243
caso_teste_pequeno_1.txt	100	0,0073	166.318
caso_teste_pequeno_2.txt	100	0,0076	167.406
caso_teste_pequeno_3.txt	1.000	0,0597	15.287.586
caso_teste_pequeno_4.txt	1.000	0,0597	15.293.954
caso_teste_medio_1.txt	5.000	1,1265	381.085.410
caso_teste_medio_2.txt	5.000	1,1295	381.106.434
caso_teste_medio_3.txt	5.000	1,1244	381.102.114
caso_teste_medio_4.txt	6.000	1,6241	548.811.138

Observação: perceba que no modo binário não houve spikes e a média se manteve baixa. Segue o detalhamento de cada run:

./trab1 casos_binarios/caso_teste_medio_4.bin saida.txt  1,35s user 0,37s system 97% cpu 1,759 total
./trab1 casos_binarios/caso_teste_medio_4.bin saida.txt  1,30s user 0,29s system 99% cpu 1,595 total
./trab1 casos_binarios/caso_teste_medio_4.bin saida.txt  1,31s user 0,31s system 99% cpu 1,628 total
./trab1 casos_binarios/caso_teste_medio_4.bin saida.txt  1,31s user 0,29s system 99% cpu 1,608 total
./trab1 casos_binarios/caso_teste_medio_4.bin saida.txt  1,29s user 0,31s system 99% cpu 1,601 total
./trab1 casos_binarios/caso_teste_medio_4.bin saida.txt  1,30s user 0,29s system 99% cpu 1,590 total
./trab1 casos_binarios/caso_teste_medio_4.bin saida.txt  1,31s user 0,28s system 99% cpu 1,600 total
./trab1 casos_binarios/caso_teste_medio_4.bin saida.txt  1,35s user 0,29s system 99% cpu 1,647 total
./trab1 casos_binarios/caso_teste_medio_4.bin saida.txt  1,30s user 0,28s system 99% cpu 1,593 total
./trab1 casos_binarios/caso_teste_medio_4.bin saida.txt  1,33s user 0,29s system 99% cpu 1,620 total

4.3. Discussão e Análise Comparativa

• Comparação entre Implementações:
  • É evidente (infelizmente) que a abordagem utilizando a fila de prioridade implementada com um heap fibonacci foi ligeiramente mais lenta (ordem de grandeza de décimos de segundos) na grande maioria dos casos e gastou mais memória. O primeiro fator pode ser explicado pela grande complexidade das operações na estrutura. O segundo fator deve-se ao fato de que o heap fibonacci utiliza estruturas encadeadas e não um simples vetor (como a primeira implementação).
  • De fato, apesar de sua grande eficiência na teoria, o heap fibonacci é uma estrutura de dados pouco prática para implementações reais, sendo o o heap binário a estrutura de escolha em grande parte dos casos.
• Análise da Melhoria Prática:
  • Em termos de tempo de execução, a melhoria prática otimizou consideravelmente o tempo de execução do programa. Para o último caso médio, a diferença chega quase em 60% (o código com a melhoria executou quase 60% mais rápido que o código sem a melhoria).
  • Não houve melhoria significativa no uso de memória. A única alocação que deixou de acontecer foi o buffer de linha na inicialização no modo texto.

---

5. Instruções de Compilação e Execução

Pré-requisitos

• GCC e Make instalados.

Compilação

Na raiz do projeto, execute:

make v1

Isso gerará o executável trab1 com a primeira implementação.

make v2

Isso gerará o executável trab1 com a segunda implementação.

Executar apenas make compilará a primeira implementação.

Execução

O programa segue o padrão de entrada e saída especificado:

./trab1 <arquivo_entrada> <arquivo_saida>

Exemplo:

./trab1 casos_teste/entrada.txt saida.txt

Limpeza

Para remover arquivos objeto e binários:

make clean

5.1. Compilação e Execução da Melhoria Prática

Primeiro, compile o programa parser para transformar a entrada:

make parser

Em seguida, realiza a conversão de uma entrada válida em modo texto:

./parser <entrada_em_texto> <entrada_em_binario>

Isso gerará uma entrada em modo binário que representa o mesmo grafo. Agora, compile o programa principal de modo a incluir a melhoria:

make melhoria

Dessa forma, o executável trab1 esperará uma entrada no modo binário e não no modo texto. Atenção: o programa não funcionará corretamente se for informado um arquivo no formato não esperado. Finalmente, execute o programa:

./trab1 <entrada_em_binario> <saida>

5.2. Compilação e Execução do gerador de casos (EXTRA)

Primeiro, compile o programa gerador de casos:

make generator

Em seguida, execute o programa gerador:

./generator <numero_de_nodes> <arquivo_saida>

O generator gera saídas em modo texto.

---

6. Estrutura do Projeto

• src/: Arquivos fonte (.c) e cabeçalhos (.h).
• obj/: Arquivos objeto compilados.
• casos_teste_v3/: Casos de teste fornecidos.
• Makefile: Automação da compilação.
• README.md: Relatório do projeto.

7. Tratamento da palavra "bomba" na entrada

Nossa estratégia para tratar a string "bomba" na entrada foi considerar que "bomba" equivale a 0, isto é, na verdade, não há aresta ligando os dois vértices envolvidos.