ucs.py

from collections import defaultdict

class PriorityQueue(object):
    def __init__(self):
        self.queue = []
  
    def __str__(self):
        return ' '.join([str(i) for i in self.queue])
  
    # for checking if the queue is empty
    def isEmpty(self):
        return len(self.queue) == 0
  
    # for inserting an element in the queue
    def insert(self, data):
        self.queue.append(data)
  
    # for popping an element based on Priority
    def pop_frontier(self):
        try:
            min = 0
            for i in range(len(self.queue)):
                if self.queue[i][0] < self.queue[min][0]:
                    min = i
            item = self.queue[min]
            del self.queue[min]
            return item
        except IndexError:
            print()
            exit()
    def pop(self, index):
        try:
            item = self.queue[index]
            del self.queue[index]
            return item
        except IndexError:
            print()
            exit()
    def clear(self):
      self.queue = []
  
class Graph:
    def __init__(self): 
        self.graph =  defaultdict(list)

    def add_edge(self, u, v, weight):
            value = (weight, v)
            self.graph[u].append(value)

g = Graph()
g.add_edge('S', 'A', 1)
g.add_edge('S', 'G', 12)
g.add_edge('A', 'B', 3)
g.add_edge('A', 'C', 1)
g.add_edge('C', 'D', 1)
g.add_edge('B', 'D', 3)
g.add_edge('C', 'G', 2)
g.add_edge('D', 'G', 3)


def uniform_cost_path(graph, start, goal):
    path = []
    explored_nodes = list()
    if start == goal:
        return path, explored_nodes
    path.append(start)
    path_cost = 0
    frontier = PriorityQueue()
    frontier.insert((path_cost, path))

    while not frontier.isEmpty():
        path_cost_till_now, path_till_now = frontier.pop_frontier()
        current_node = path_till_now[-1]
        explored_nodes.append(current_node)

        if current_node == goal:
            return path_till_now, path_cost_till_now

        neighbours = graph.graph[current_node]

        for i in range(len(neighbours)):
            path_to_neighbour = path_till_now.copy()
            path_to_neighbour.append(neighbours[i][1])

            neighbour_cost = neighbours[i][0] + path_cost_till_now
            new_element = (neighbour_cost, path_to_neighbour)
            if(neighbours[i][1] not in explored_nodes):
                frontier.insert(new_element)
    return None, None



res = uniform_cost_path(g, 'S', 'G')
print(res)