Camino Óptimo en Python

import os

grafo = {}

opc = 0
while opc != 3:
    os.system("cls")
    print("\n\tUniversidad José Antonio Páez")
    print("\t   Facultad de Ingeniería")
    print("\t   Escuela de Computación")
    print("\t   Facultad de Ingeniería")
    print("\n\t  Camino Óptimo en Grafo")
    print("\n\tRealizado por: Romina Betancourt")
    opc = input ("\n1.-Ingresar nodos \n2.-Recorrer grafo por cámino óptimo \n3.-Salir \nElige una opcion-> ")
    opc = int(opc)

    if opc == 1:
        vertices = int(input("\n\tIngrese la cantidad de vértices a recibir por el grafo: "))
        for i in range(vertices):
            print("\nINGRESE LOS NODOS Y SU PESO \n")
            origen  = input("Ingresa el origen: a,b,c,...z  ")
            destino = input("Ingresa el destino: a,b,c,...z ")
            peso    = input("Ingresa el peso: 1,2,3,...,n   ")
            peso = int(peso)
       
            ###VERIFICA QUE NO ESTE REPETIDO EL VERTICE ORIGEN Y DESTINO INGRESADO
            repetido = False
            for orig, lista in grafo.items():
                for destin, pesos in grafo[orig]:
                    if orig == origen and destin == destino and pesos == peso:
                        print("\nEL VERTICE YA EXISTE\n")
                        repetido = True
            #SI NO ESTÁ REPETIDO INGRESA A VALIDAR SI LOS NODOS ORIGEN Y DESTINO EXISTEN
            if repetido == False:
                if origen in grafo:
                    if destino in grafo:
                        lista = grafo[origen]
                        grafo[origen] = lista + [(destino, peso)]
                        lista = grafo [destino]
                        lista.append((origen, peso))
                        grafo[destino] = lista
                    else:
                        grafo[destino] = [(origen, peso)]
                        lista = grafo [origen]
                        lista.append((destino, peso))
                        grafo[origen] = lista
                elif destino in grafo:
                    grafo[origen] = [(destino, peso)]
                    lista = grafo [destino]
                    lista.append((origen, peso))
                    grafo[destino] = lista
                else:
                    grafo[destino] = [(origen, peso)]
                    grafo[origen] = [(destino, peso)]
                print()
        #SI EL GRAFO TIENE NODOS LO MUESTRA
        if len(grafo) > 0:
            for key, lista in grafo.items():
                print("Ahora observe el Grafo Completo\n")
                print(key)
                print(lista)
        else:
            print("El grafo esta vacio...")
    print()
    if opc == 2:
        visitados = []
        pila = []

        origen = input("Ingresa un nodo a recorrer: ")
        print("\nLista de del recorrido del nodo por ruta óptima\n")
        #Paso 1: SE COLOCA EL VÉRTICE ORIGEN EN UNA PILA
        pila.append(origen)
        #Paso 2: MIENTRAS LA PILA NO ESTE VACÍA
        while pila:
                #paso 3: DESAPILAR UN VÉRTICE, ESTE SERÁ AHORA EL VÉRTICE ACTUAL
                actual = pila.pop()
                #FORMA ALTERNATIVA PARA DESAPILAR:
                #actual = pila[-1]
                #pila.remove(pila[-1])

                #paso 4: SI EL VÉRTICE ACTUAL NO HA SIDO VISITADO
                if actual not in visitados:
                    #paso 5: PROCESAR (IMPRIMIR) EL VÉRTICE ACTUAL
                    print("Vertice actual -> ", actual)
                    #paso 6: COLOCAR VÉRTICE ACTUAL EN LA LISTA DE VISITADOS
                    visitados.append(actual)
                #paso 7: PARA CADA VÉRTICE QUE EL VÉRTICE ACTUAL TIENE COMO DESTINO,
                #        Y QUE NO HA SIDO VISITADO:
                #        APILAR EL VERTICE
                for key, lista in grafo[actual]:
                    if key not in visitados:
                            pila.append(key)

print()
os.system("pause")