Dijkstra's Algorithm

Dijkstra's Algorithm is an essential algorithm for finding the shortest path in weighted graphs. It is widely used in various applications including mapping software, networking, and robotic path planning.

The algorithm works by maintaining a list of distances from the source node to all other nodes in the graph. It starts with an initial distance of infinity for all nodes except the source node, which has a distance of 0.

The algorithm then iteratively selects the node with the smallest distance from the current set of unvisited nodes. It updates the distances of its neighbors by considering the weight of the connecting edges and the current shortest path distance.

Here is an example implementation of Dijkstra's Algorithm in Python:

1{code}

In this example, we have a graph represented as an adjacency dictionary. The key-value pairs in the dictionary represent the connections between nodes and the corresponding edge weights. We start the algorithm from the source node 'A'. The output of the algorithm is a dictionary where the keys are the nodes and the values are the shortest distances from the source node.

xxxxxxxxxx

print(shortest_distances)

import heapq

​

def dijkstra(graph, start):

    distances = {node: float('inf') for node in graph}

    distances[start] = 0

    queue = [(0, start)]

​

    while queue:

        current_distance, current_node = heapq.heappop(queue)

​

        if current_distance > distances[current_node]:

            continue

​

        for neighbor, weight in graph[current_node].items():

            distance = current_distance + weight

​

            if distance < distances[neighbor]:

                distances[neighbor] = distance

                heapq.heappush(queue, (distance, neighbor))

​

    return distances

​

​

# Example usage

graph = {

    'A': {'B': 5, 'C': 2},

    'B': {'A': 5, 'C': 1, 'D': 3},

    'C': {'A': 2, 'B': 1, 'D': 1},

    'D': {'B': 3, 'C': 1}