Prévia do material em texto
PONTIFÍCIA UNIVERSIDADE CATÓLICA DE MINAS GERAIS
Trabalho prático
Algoritmo Dijkstra - Menor caminho
Bruno Maciel dos Santos
Tiago Rafael Martins Cardoso
Victória Gonçalves da Silva
Betim
2024
1. Algoritmo
using System;
using System.Collections.Generic;
namespace ConsoleApp1
{
public class AlgoritmoDijkstra
{
private int[,] Vertices;
public AlgoritmoDijkstra(int numVertices) {
Vertices = new int[numVertices, numVertices];
}
public void criarAresta(int noOrigem, int noDestino, int peso)
{
if (peso >= 1)
{
Vertices[noOrigem, noDestino] = peso;
Vertices[noDestino, noOrigem] = peso;
}
}
private int getMaisProximo(int[] listaCustos, HashSet naoVisitados)
{
int minDistancia = int.MaxValue;
int noProximo = 0;
foreach(int i in naoVisitados)
{
if (listaCustos[i] getVizinhos(int no)
{
List vizinhos = new List();
for (int i = 0; i 0)
{
vizinhos.Add(i);
}
}
return vizinhos;
}
private int getCusto(int noOrigem, int noDestino)
{
return Vertices[noOrigem, noDestino];
}
public void caminhoMinimo()
{
int[] custo = new int[Vertices.GetLength(0)];
int[] antecessor = new int[Vertices.GetLength(0)];
HashSet naoVisitados = new HashSet();
custo[0] = 0;
for(int i = 0;i ");
foreach(int no in caminho(antecessor, i))
{
if (no != 0)
Console.Write(no + " -> ");
}
Console.WriteLine("Fim da Rota\nCusto: " + custo[i] + "\n");
}
}
private List caminho(int[] antecessor, int no)
{
List caminho = new List();
caminho.Add(no);
while (antecessor[no] != -1)
{
caminho.Add(antecessor[no]);
no = antecessor[no];
}
caminho.Reverse();
return caminho;
}
}
internal class Program
{
private static int D = 0;
private static int S1 = 1;
private static int S2 = 2;
private static int S3 = 3;
private static int S4 = 4;
private static int S5 = 5;
private static int S6 = 6;
static void Main(string[] args)
{
AlgoritmoDijkstra dijkstra = new AlgoritmoDijkstra(7);
dijkstra.criarAresta(D, S3, 5);
dijkstra.criarAresta(D, S5, 6);
dijkstra.criarAresta(S3, S5, 4);
dijkstra.criarAresta(S3, S2, 14);
dijkstra.criarAresta(S3, S1, 5);
dijkstra.criarAresta(S5, S4, 9);
dijkstra.criarAresta(S5, S6, 8);
dijkstra.criarAresta(S1, S2, 10);
dijkstra.criarAresta(S2, S4, 3);
dijkstra.criarAresta(S4, S6, 7);
dijkstra.caminhoMinimo();
Console.ReadKey();
}
}
}
2. Passo a passo da execução
Imagem 1
Imagem 2
Imagem 3
Imagem 4
Imagem 5
Imagem 6
Imagem 7
Imagem 8
Imagem 9
Imagem 10
Imagem 11
Imagem 12
Imagem 13
Imagem 14
Imagem 15
3. Relatório de desenvolvimento
1. Desenvolvimento do Programa
Objetivo: Implementar o algoritmo de Dijkstra para calcular os caminhos
mínimos em um grafo ponderado, aplicado a um sistema de roteamento de
pontos de entrega a partir de um depósito.
Linguagem: Código desenvolvido em C#, utilizando uma matriz de adjacência
para representar as conexões entre os nós do grafo.
Estrutura Principal:
A classe AlgoritmoDijkstra foi usada para gerenciar o grafo e implementar o
algoritmo.
A classe Program contém a lógica para criar os nós e arestas, além de iniciar
a execução do algoritmo.
Fluxo do Algoritmo:
Inicia com um custo de 0 para o nó de origem (depósito) e infinito para os
demais nós.
Usa uma lista de nós não visitados para determinar o nó com menor custo
iterativamente.
Atualiza os custos e antecessores com base nas arestas adjacentes.
Após calcular todos os caminhos, exibe os resultados de custo total e
trajetória para cada destino.
2. Resultados Obtidos
Caminhos Gerados:
O programa calcula e exibe a rota mínima de um depósito para os pontos de
entrega, indicando os nós percorridos em ordem e o custo total.
Exemplo de saída:
Distância do depósito para o ponto 1
Trajeto: D -> 3 -> 1 -> Fim da Rota
Custo: 10
Distância do depósito para o ponto 2
Trajeto: D -> 3 -> 2 -> Fim da Rota
Custo: 19
Uso Prático: A aplicação simula uma rede logística, onde cada nó é um ponto
de entrega e o peso das arestas representa custos como distância ou tempo
de viagem.
4. Conclusão
O projeto explorou a aplicação prática do Algoritmo de Dijkstra em um sistema
de roteamento logístico. O grafo utilizado foi modelado com 7 nós,
representando o depósito e os pontos de entrega, e as arestas ponderadas
indicavam os custos associados a cada rota, como distâncias ou tempos de
viagem. O algoritmo foi implementado em C# de maneira eficiente, utilizando
uma matriz de adjacência para estruturar o grafo e estruturas auxiliares para
gerenciar custos e trajetos mínimos.
O programa, desenvolvido pelo aluno Tiago, demonstrou consistência ao
calcular corretamente os caminhos mínimos para diferentes configurações de
grafos, exibindo o passo a passo das decisões tomadas pelo algoritmo. As
representações gráficas elaboradas pela aluna Victoria complementaram a
análise, oferecendo uma visualização clara das conexões e trajetórias
calculadas. Toda a documentação, escrita por Bruno, detalhou o processo de
desenvolvimento e os resultados obtidos, garantindo a organização e clareza
do trabalho apresentado.
No geral, o projeto demonstrou como o Algoritmo de Dijkstra pode ser
aplicado de forma prática para resolver problemas de logística e roteamento.
Ele reforça sua utilidade em cenáriosdo mundo real, como transporte,
distribuição, planejamento de rotas urbanas e até mesmo na otimização de
redes de comunicação. Esse trabalho destaca o papel de ferramentas
computacionais no aumento da eficiência e redução de custos em operações
complexas, mostrando seu potencial para atender demandas modernas em
diferentes áreas.