ALGORITMOS EM GRAFOS — Busca em Largura (BFS)

Conteúdo da Disciplina: Grafos 1

Alunos

Matrícula	Aluno
231026901	Caio Ferreira Duarte
211029601	Victor Pontual Guedes Arruda Nobrega

Sobre

Este projeto utiliza um dataset de aeroportos brasileiros e suas conexões para aplicar o algoritmo de Busca em Largura (BFS). O objetivo é encontrar o menor caminho em número de conexões entre dois aeroportos e visualizar o grafo de rotas aéreas em um mapa interativo.

A aplicação é desenvolvida em Python utilizando as bibliotecas networkx para a modelagem do grafo, pandas para manipulação de dados, e dash com plotly para a criação da interface web de visualização.

Algoritmo (visão geral)

Busca em Largura (BFS) — Menor Caminho em Grafos Não Ponderados

O algoritmo de Busca em Largura (BFS) é ideal para encontrar o menor caminho em um grafo não ponderado, ou seja, onde todas as arestas têm o mesmo peso. No contexto deste projeto, ele determina a rota com o menor número de voos (escalas) entre um aeroporto de origem e um de destino.

Screenshots

Exemplo da execução da aplicação:

Instalação

Requisitos:

• Python 3.8+

Passos:

1. Clonar o repositório.
2. (Opcional) Criar e ativar um ambiente virtual.

python -m venv .venv
./.venv/Scripts/Activate.ps1

3. Instalar as dependências:

pip install -r requirements.txt

Uso

1. Abra um terminal na pasta do projeto.

2. Execute:

python main.py

Apresentação

Vídeo disponível em: https://youtu.be/fZ1WKv3jRLA?si=6xPxQsA2lbRavCIy