                             PRACTICAL NO:4
            UNIFORM COST SEARCH ALGORITHM
Uniform Cost Search (UCS) is an uninformed search algorithm used to find the lowest-cost path between a start node and a goal node in a weighted graph. It systematically explores paths based on their cumulative cost, making it suitable for cost-sensitive pathfinding problems.
Consider the total path cost rather than the number of steps taken.
Guarantees the optimal solution when all edge costs are non-negative.
Uses a priority queue to efficiently select the next node with the lowest cost.
MAP:
ALGORITHM:
CODE:
from queue import PriorityQueue
GRAPH={\
    'oradea':{'zerind':71,'sibiu':151},\
    'zerind':{'arad':75},\
    'arad':{'timisoara':118,'sibiu':140},\
    'timisoara':{'lugoj':111},\
    'lugoj':{'mehadia':70},\
    'mehadia':{'drobeta':75},\
    'drobeta':{'craiova':120},\
    'craiova':{'riminicu':146,'pitesti':138},\
    'riminicu':{'sibiu':80,'pitesti':97},\
    'sibiu':{'fagaras':99},\
    'fagaras':{'bucharest':211},\
    'bucharest':{'giurgiu':90,'urziceni':85},\
    'urziceni':{'vaslui':142,'hirsova':98},\
    'hirsova':{'eforie':86},\
    'vaslui':{'iasi':92},\
    'iasi':{'neamt':87},\
    'pitesti':{'bucharest':101},\
    'eforie':{'hirsova':86},\
    'giurgiu':{'bucharest':90},\
     'neamt':{'iasi':87}
 }
heu_value={
    }
def ucs (source, destination):
    priority_queue, visited=PriorityQueue(), {}
    priority_queue.put((0, source, [source]))
    visited[source] = 0
    while not priority_queue.empty():
        (cost, vertex, path) = priority_queue.get()
        if vertex== destination:
            return cost, path
        for next_node in GRAPH[vertex].keys():
            current_cost=cost + GRAPH[vertex][next_node]
            if not next_node in visited or visited[next_node] >= current_cost:
                visited[next_node]=current_cost
                priority_queue.put((current_cost, next_node, path+[next_node]))
def main():
    """Main function"""
    print('ENTER SOURCE:', end=' ')
    source = input().strip()
    print('ENTER GOAL:', end=' ')
    goal = input().strip()
    if source not in GRAPH or goal not in GRAPH:
        print('ERROR: CITY DOES NOT EXIST.')
    else:
        print('\nCHEAPEST PATH:')
        cost, cheapest_path = ucs(source, goal)
        print('PATH COST', cost)
        print(' -> '.join(city for city in cheapest_path))
if __name__=='__main__' :
     main()                
OUTPUT: