find shortest path

shortestPath.py

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)))