UCS(Dijkstra)

 import heapq

def uniform_cost_search(graph, start, goal):

    # Priority queue to hold nodes and their cumulative cost

    priority_queue = [(0, start)]  # (cost, node)

    visited = set()  # To keep track of visited nodes

    cost_so_far = {start: 0}  # Track the shortest cost to each node

    while priority_queue:

        current_cost, current_node = heapq.heappop(priority_queue)

        # If the goal is reached, return the cost and path

        if current_node == goal:

            return current_cost

        if current_node in visited:

            continue

        visited.add(current_node)

        # Explore neighbors

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

            new_cost = current_cost + weight

            if neighbor not in cost_so_far or new_cost < cost_so_far[neighbor]:

                cost_so_far[neighbor] = new_cost

                heapq.heappush(priority_queue, (new_cost, neighbor))

    return float('inf')  # If no path is found, return infinity

# Example usage:

graph = {

    'A': [('B', 1), ('C', 4)],

    'B': [('A', 1), ('D', 2), ('E', 5)],

    'C': [('A', 4), ('F', 3)],

    'D': [('B', 2), ('E', 1)],

    'E': [('B', 5), ('D', 1), ('F', 2)],

    'F': [('C', 3), ('E', 2)]

}

start_node = 'A'

goal_node = 'F'

cost = uniform_cost_search(graph, start_node, goal_node)

print(f"Minimum cost from {start_node} to {goal_node}: {cost}")