Last active
December 15, 2022 01:35
-
-
Save isturiz/a31c1bacb53e8964c3be626e192765fa to your computer and use it in GitHub Desktop.
find shortest path
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
from heapq import heappush, heappop | |
def shortestPath(graph): | |
# Crea un diccionario para almacenar las distancias de los nodos desde "A" | |
distances = {} | |
# Crea una cola de prioridad que almacenará las distancias y nodos visitados | |
queue = [(0, 'A')] | |
# Mientras la cola no esté vacía, seguirá buscando el camino más corto | |
while queue: | |
# Obtiene el nodo con la distancia más corta | |
distance, node = heappop(queue) | |
# Si el nodo no ha sido procesado | |
if node not in distances: | |
# Agrega la distancia desde "A" al nodo | |
distances[node] = distance | |
# Procesando cada uno de sus vecinos | |
for neighbor, cost in graph[node].items(): | |
# Si el vecino no ha sido visitado | |
if neighbor not in distances: | |
# agrega su distancia a la cola de prioridad | |
heappush(queue, (distance + cost, neighbor)) | |
# Si hay varios arcos entre dos nodos | |
if (neighbor, node) in graph and cost > graph[neighbor][node]: | |
# Elige el de menor costo | |
heappush(queue, (distance + graph[neighbor][node], neighbor)) | |
return distances | |
def showGraph(distances): | |
# Obtiene la lista de claves del diccionario | |
keys = list(distances) | |
# Recorre la lista de claves y se concatenan en un string | |
path = "" | |
for key in keys: | |
if (key == keys[-1]): | |
path += key | |
else: | |
path += key + " -> " | |
# Imprime el texto concatenado y el valor del último elemento del diccionario | |
return (path + ": " + str(distances[keys[-1]])) | |
# Grafo: primer ejercicio | |
graph_1 = { | |
'A': {'B': 1, 'C': 2}, | |
'B': {'C': 1, 'D': 5, 'E': 2}, | |
'C': {'D': 2, 'E': 1, 'F': 4}, | |
'D': {'F': 6, 'G': 8}, | |
'E': {'F': 3, 'G': 7}, | |
'F': {'H': 2, 'G': 5}, | |
'G': {'H': 6}, | |
'H': {} | |
} | |
# Grafo: segundo ejercicio | |
graph_2 = { | |
'A': {'B': 5, 'C': 1}, | |
'B': {'D': 7, 'E': 7, 'F': 1}, | |
'C': {'B': 2, 'D': 6, 'E': 7}, | |
'D': {'C': 7, 'G': 6}, | |
'E': {'B': 6, 'G': 2}, | |
'F': {'D': 3, 'E': 5, 'G': 9}, | |
'G': {} | |
} | |
print(showGraph(shortestPath(graph_1))) | |
print(showGraph(shortestPath(graph_2))) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment