import heapq
def dijkstra(graph, start, end):
# Priority queue: (cost, current_node)
queue = [(0, start)]
distances = {node: float('inf') for node in graph}
distances[start] = 0
predecessors = {node: None for node in graph}
while queue:
current_cost, current_node = heapq.heappop(queue)
if current_node == end:
break
for neighbor, cost in graph[current_node].items():
new_cost = current_cost + cost
if new_cost < distances[neighbor]:
distances[neighbor] = new_cost
predecessors[neighbor] = current_node
heapq.heappush(queue, (new_cost, neighbor))
# Reconstruct shortest path
path = []
node = end
while node is not None:
path.insert(0, node)
node = predecessors[node]
return path, distances[end]
# Example graph (dictionary of dictionaries)
graph = {
'A': {'B': 2, 'C': 5},
'B': {'A': 2, 'C': 1, 'D': 4},
'C': {'A': 5, 'B': 1, 'D': 1},
'D': {'B': 4, 'C': 1}
}
# Usage
start_node = 'A'
end_node = 'D'
shortest_path, total_cost = dijkstra(graph, start_node, end_node)
print(f"Shortest path: {shortest_path}")
print(f"Total cost: {total_cost}")
Comments
Post a Comment