Page

$2$

class Graph:

# graph dictionary contains all the adjacent nodes of each as key and value pair

# cost$\_$dict contains cost of each edge traversal of $(u,v)$

# final$\_$dict contains all the possible paths from start node s to goal node $g$ with total cost def $\_($self$)$:

self.graph $=$ dict$()$

self.cost$\_$dict$=$dict$()$

self.final$\_$dict$=$dict$()$

# $u$ and $v$ are nodes: edge $uv$ with cost $c$

def addEdge$($self$,u,v,c)$:

if $u$ not in self.graph:

$qu=Q.$PriorityQueue$()$

self.graph.update$(\{$u:qu$\})$

self.graph$[$u$].$put$($v$)$

self.cost$\_$dict.update$(\{($u$,$v$)$:c$\})$

# Makes a list to keep track of visited nodes

def tnode$($self$,n)$:

self.visited $=[$ False ${]}^{**}n$

def UCS$\_$util$($self$,$s$,$visited, path,goal,value$)$:

# Appending node to the current path

path.append$($s$)$

# Marking that node is visited

visited$[$s$]=$True

# If goal node is reached save the path and return

if goal$==$s:

self.final$\_$dict.update$(\{$tuple$($path$)$:value$\})$

return

# Checking if the adjacent node is been visited and explore the new path if haven't

for $i$ in self.graph$[$s$].$queue:

if visited$[$i$]==$False:

# When new path is being explored add the cost of that path to cost of

entire course traversal

self.cost$\_$dict$[$s$,$i$])$

# Send a copy of path list to avoid sending it by reference

self.UCS$\_$util$($i$,$copy.deepcopy$($visited$),$copy.deepcopy$($path$),$goal,value $+$

def UCS$($self$,$ s$,$goal$)$:

self.visited$[$s$]=$ True

Page

$3$

# List to hold all the nodes visited in path from start node to goal node path $=[s]$

for i in self.graph$[$s$].$queue:

if self.visited$[$i$]==$ False:

# Make a variable to hold the cost of traversal value $=$ self.cost$\_$dict$[,i$

self.UCS$\_$util$($i$,$copy.deepcopy$($self$.$visited$),$copy.deepcopy$($path$),$goal,value$)$

# Display all the paths that is been discovered from start node to Goal node def all$\_$paths$($self$)$:

# Check if there is any path

if bool$($self$.$final$\_$dict$)$:

print$("$All the paths: $")$

for $1$ in self.final$\_$dict:

print$("$path: $",$i$,$"cost: $",$self.final$\_$dict$[$i$])$

else:

print$("$No Path exist between start and goal node"$)$

# Find the most optimal path between start node to goal node

def optimal$\_$path$($self$)$:

if bool$($self$.$final$\_$dict$)$:

print$("$best path: $",$ min$($self$.$final$\_$dict, key$=$self.final$\_$dict.get$)$

else:

print$("$No Path exist between start and goal node"$)$