Dijkstra's Algorithm for finding shortest paths in a graph

Demonstration with a simple weighted graph

def dijkstra(graph, start): # Initialize distances with infinity for all nodes except start distances = {node: float('infinity') for node in graph} distances[start] = 0

# Set of unvisited nodes
unvisited = list(graph.keys())

# Path tracking
previous = {node: None for node in graph}

while unvisited:
    # Find the unvisited node with minimum distance
    current = min(unvisited, key=lambda node: distances[node])
    
    # If we're processing a node with infinite distance, 
    # it means the remaining nodes are unreachable
    if distances[current] == float('infinity'):
        break
        
    # Remove the current node from unvisited set
    unvisited.remove(current)
    
    # Check all neighbors of current node
    for neighbor, weight in graph[current].items():
        # Calculate potential new distance
        distance = distances[current] + weight
        
        # If we found a better path, update the distance
        if distance < distances[neighbor]:
            distances[neighbor] = distance
            previous[neighbor] = current

return distances, previous

Function to reconstruct the path from start to end

def get_path(previous, start, end): path = [] current = end

while current != start:
    path.append(current)
    current = previous[current]
    if current is None:
        return []  # No path exists

path.append(start)
return path[::-1]  # Reverse to get path from start to end

Example graph represented as an adjacency list with weights

graph = { 'A': {'B': 4, 'C': 2}, 'B': {'A': 4, 'C': 1, 'D': 5}, 'C': {'A': 2, 'B': 1, 'D': 8, 'E': 10}, 'D': {'B': 5, 'C': 8, 'E': 2, 'F': 6}, 'E': {'C': 10, 'D': 2, 'F': 3}, 'F': {'D': 6, 'E': 3} }

start_node = 'A' distances, previous = dijkstra(graph, start_node)

Print the shortest distances from the start node

print(f"Shortest distances from node {start_node}:") for node, distance in distances.items(): print(f" To {node}: {distance}") path = get_path(previous, start_node, node) print(f" Path: {' -> '.join(path)}") print()

Dijkstra's Algorithm Demonstration

Dijkstra's Algorithm for finding shortest paths in a graph

Demonstration with a simple weighted graph

Function to reconstruct the path from start to end

Example graph represented as an adjacency list with weights

Print the shortest distances from the start node