MINISTÉRIO DA EDUCAÇÃO
UNIVERSIDADE FEDERAL RURAL DA AMAZÔNIA
CAMPUS CAPITÃO POÇO
BACHARELADO EM SISTEMAS DE INFORMAÇÃO
INTRODUÇÃO À INTELIGÊNCIA ARTIFICIAL
Anthony Ivens da Silva Ferreira,
Rodolfo Chaves Lima De Oliveira
Capitão poço – PA
2024
Relatório sobre a Implementação do Algoritmo de Dijkstra
Introdução
O algoritmo de Dijkstra é um dos mais conhecidos e eficientes para encontrar o
caminho mais curto entre um nó inicial e os demais nós em um grafo
ponderado com pesos não negativos. Ele tem aplicações em redes de
computadores, sistemas de navegação, logística e outros domínios que
requerem otimização de caminhos.
Objetivo
O objetivo deste trabalho é implementar o algoritmo de Dijkstra em Python,
utilizando a biblioteca networkx para representar e visualizar o grafo, e heapq
para otimizar a seleção dos menores caminhos.
Metodologia
A implementação foi dividida em duas partes:
1. Construção e visualização do grafo utilizando a biblioteca networkx e
matplotlib.
2. Implementação do algoritmo de Dijkstra para calcular a menor distância
de um nó inicial para todos os outros nós do grafo.
3. Ambiente de Desenvolvimento para o desenvolvimento do
código, utilizamos o Visual Studio Code (VS Code), um editor de
código leve e versátil, com suporte a diversas linguagens de
programação. O projeto foi configurado da seguinte maneira:
4. Instalação das Bibliotecas Necessárias:
a. Utilizamos o gerenciador de pacotes pip para instalar as
bibliotecas:
5. pip install networkx matplotlib
6. Execução do Código:
a. O código foi escrito e salvo com a extensão .py no VS
Code.
b. Utilizamos o terminal integrado do VS Code para rodar o
script com:
7. python nome_do_arquivo.py
a. O código gerado:
import networkx as nx
import [Link] as plt
def desenhar_grafo():
G = [Link]()
Distancia = [
('1', '2', 7), ('1', '3', 9), ('1', '6', 14),
('2', '3', 10), ('2', '4', 15), ('3', '4', 11),
('3', '6', 2), ('4', '5', 6), ('6', '5', 9) ]
for A, R, peso in Distancia:
G.add_edge(A, R, weight=peso)
pos = nx.spring_layout(G)
labels = nx.get_edge_attributes(G, 'weight')
[Link](figsize=( 7, 5))
[Link](G, pos, with_labels=True, node_color='red', node_size=1000,
font_size=12, edge_color='black')
nx.draw_networkx_edge_labels(G, pos, edge_labels=labels,
font_size=10)
[Link]("Representação do Algoritmo de Dijkstra")
[Link]()
desenhar_grafo()
b. O gráfico gerado é exibido automaticamente em uma
nova janela.
Implementação
A implementação utiliza um dicionário para representar o grafo, onde cada nó
está associado a seus vizinhos e respectivos pesos das arestas. O algoritmo
emprega uma fila de prioridade (“heap queue”) para explorar os nós com menor
custo acumulado.
1. Construção do Grafo O grafo é definido por uma lista de arestas, onde
cada aresta é representada por uma tupla contendo dois nós e o peso da
conexão entre eles. A função desenhar_grafo utiliza a biblioteca networkx para
gerar a representação visual.
2. Algoritmo de Dijkstra O algoritmo inicia com todas as distâncias definidas
como infinito (∞), exceto para o nó inicial, que recebe distância zero. Em
seguida, os nós são processados iterativamente, atualizando as distâncias
conforme novos caminhos mais curtos são encontrados.
Resultados
A execução do código apresenta:
Um grafo visual com nós conectados pelas arestas e seus respectivos
pesos.
A saída no console exibindo as menores distâncias do nó inicial para os
demais nós
Conclusão
A implementação do algoritmo de Dijkstra permitiu calcular com eficiência os
menores caminhos em um grafo ponderado. A combinação do networkx para a
visualização e heapq para otimização do processamento proporcionou uma
solução eficiente e didática para o problema de menor caminho.
Bibliografia
Dijkstra, E. W. "A Note on Two Problems in Connexion with Graphs".
Numerische Mathematik, 1959.
NetworkX Documentation: [Link]
Python heapq Module: [Link]
