algoritmo-dijkstra.py

import sys
import os

class Dijkstra:
    def __init__(self, grafo):
        self.grafo = grafo
        self.distancias = {}
        self.visitado = {}
        self.anterior = {}
        self.infinito = sys.maxsize

    def dijkstra(self, inicio):
        for no in self.grafo:
            self.distancias[no] = self.infinito
            self.visitado[no] = False
            self.anterior[no] = None

        self.distancias[inicio] = 0 

        while True:
            menor_distancia = self.infinito
            no_atual = None

            for no in self.grafo:
                if not self.visitado[no] and self.distancias[no] < menor_distancia:
                    menor_distancia = self.distancias[no]
                    no_atual = no

            if no_atual is None:
                break

            self.visitado[no_atual] = True

            for vizinho in self.grafo[no_atual]:
                distance = self.distancias[no_atual] + self.grafo[no_atual][vizinho]
                if distance < self.distancias[vizinho]:
                    self.distancias[vizinho] = distance
                    self.anterior[vizinho] = no_atual

    def distanciasMinimas(self):
        return self.distancias

    def caminhosCurtos(self):
        caminhos = {}
        for no in self.anterior:
            caminho = []
            no_atual = no
            while no_atual is not None:
                caminho.insert(0, no_atual)
                no_atual = self.anterior[no_atual]
            caminhos[no] = caminho
        return caminhos

def inicio():
    os.system('clear')
    no_inicio = ''
    caminho_curto = ''
    grafo = {
        'Criciuma': {'Forquilinha': 4, 'Porto Alegre': 8}, 
        'Forquilinha': {'Criciuma': 4, 'Porto Alegre': 11, 'Tubarão': 8}, 
        'Tubarão': {'Forquilinha': 8, 'Dois Irmãos': 7, 'Terezina': 4, 'Nova Veneza': 2}, 
        'Dois Irmãos': {'Tubarão': 7, 'Londrina': 9, 'Terezina': 14}, 
        'Londrina': {'Dois Irmãos': 9, 'Terezina': 10}, 
        'Terezina': {'Londrina': 10, 'Dois Irmãos': 14, 'Tubarão': 4, 'Sto. Antonio': 2}, 
        'Sto. Antonio': {'Terezina': 2, 'Nova Veneza': 6, 'Porto Alegre': 1}, 
        'Porto Alegre': {'Sto. Antonio': 1, 'Nova Veneza': 7, 'Forquilinha': 11, 'Criciuma': 8}, 
        'Nova Veneza': {'Porto Alegre': 7, 'Sto. Antonio': 6, 'Tubarão': 2},
    }

    while no_inicio not in grafo.keys() and no_inicio not in ['0', 0]:
        print('Lista de cidades disponíveis: ')
        for cidade in grafo.keys():
            print(cidade)
        print('0 - Sair')
        no_inicio = input("\nDigite o nome da cidade origem: ")
        no_inicio = no_inicio.title()
        os.system('clear')

    if no_inicio in ['0', 0]:
        exit()

    dijkstra = Dijkstra(grafo)
    dijkstra.dijkstra(no_inicio)

    distancias = dijkstra.distanciasMinimas()
    print("Distâncias mínimas a partir do nó de partida", no_inicio)
    for no in distancias:
        print(f"Nó: {no}, Distância mínima: {distancias[no]}")

    while caminho_curto.upper() not in ['S', 'N']:
        caminho_curto = input("\nMostrar caminhos mais curtos ? (S ou N) ")

    if caminho_curto.upper() == 'S':
        caminhos = dijkstra.caminhosCurtos()
        print("\nCaminhos mais curtos:")
        for no in caminhos:
            caminho = caminhos[no]
            print(f"Nó: {no}, Caminho: {caminho}")

    executar = input('Executar novamente? (S ou N)')
    if executar.upper() == 'S':
        inicio()

inicio()