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

Popular posts from this blog

Pos using Seq to seq