Dijkstra's Algorithm

 Dijkstra's Algorithm

Dijkstra's algorithm is a shortest path algorithm that finds the shortest path between a starting node and all other nodes in a weighted graph.

python

# Dijkstra's algorithm function

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_vertex = heapq.heappop(queue)

        if current_distance > distances[current_vertex]:

            continue

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

            distance = current_distance + weight

            if distance < distances[neighbor]:

                distances[neighbor] = distance

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

    return distances