-
Notifications
You must be signed in to change notification settings - Fork 0
/
UCS.py
89 lines (76 loc) · 2.09 KB
/
UCS.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
import sys
class Graph:
def __init__(self):
self.adjDict = dict()
self.start_node = "S"
self.goal_node = "S"
def add_edge(self, u, v, w):
if u not in self.adjDict:
self.adjDict[u] = list()
self.adjDict[u].append([w, v])
def print(self):
for key in self.adjDict:
print(key)
print(self.adjDict[key])
def set_start_node(self, node):
self.start_node = node
def set_goal_node(self, node):
self.goal_node = node
def ucs(self):
max_distance = sys.maxsize
q = list()
visited = list()
q.append([0, self.start_node])
# print(q)
while q:
# print(q)
edge = q.pop(0)
# print(q)
if edge[1] in visited:
continue
visited.append(edge[1])
if edge[1] == self.goal_node:
if edge[0] < max_distance:
max_distance = edge[0]
edges = []
if edge[1] in self.adjDict:
edges = self.adjDict[edge[1]]
for outEdge in edges:
# print(type(edge[0]))
# print(type(outEdge[0]))
q.append([edge[0] + outEdge[0], outEdge[1]])
q.sort()
print(f"min distance to goal node is: {max_distance}")
def main():
print("enter input")
graph = Graph()
while True:
tokens = input().split()
parent = tokens[0]
if parent == "-1":
break
children = tokens[1:]
for child in children:
# print(child)
# print(child.split(","))
graph.add_edge(parent, child.split(
",")[0], int(child.split(",")[1]))
# graph.print()
start_node = input("enter start node: ")
goal_node = input("enter goal node: ")
graph.set_start_node(start_node)
graph.set_goal_node(goal_node)
graph.ucs()
# graph.print()
main()
'''
enter input
S A,1 B,2
A C,2 D,3
B E,4 G,6
C G,3
-1
enter start node: S
enter goal node: G
min distance to goal node is: 6
'''