Logo Passei Direto
Buscar
Material
páginas com resultados encontrados.
páginas com resultados encontrados.

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.

Mais conteúdos dessa disciplina