Unrelated to code:
- This is my first project in Python using classes and algorithms.
- I have spent the last week self teaching myself about queues and stacks, so I am NOT trying to use any Python libraries for this as I would like to know how to implement my own priority queue
About the code:
- Dictionary used for priority queue.
- Priority queue should be its own class, but I dont know how to call a method from one class to another, I did research this and came across
staticmethod
but was unsure of its implementation. - This was all done on one single file.
What I would like from this:
- A way to get the input for graph without having it already 'created' when code is run. I had an idea to get user input for each node and its arc length to every other node, but this is inefficient for larger graphs.
- General advice/feedback/issues with my code/logic
class Graph:
def __init__(self):
self.nodes = {}
def add_node(self, key, neighbours):
self.nodes[key] = neighbours
def shortest_path(self, start, finish):
distance = {} # stores distance to start node of a vertex
visited = {} # stores previously visited node
queue = {} # PQ that gives the shortest value from start to a vertex
for node in self.nodes:
if node == start:
distance[node] = 0 # as distance from start node is 0
queue[node] = 0 # value of root node to root node is 0
else:
distance[node] = 1000 # set unvisited nodes arc length to large value
queue[node] = 1000
while len(queue) != 0:
if start == finish:
print("start node and end node are same so distance is 0")
break
# works out arc with lowest weight
lowest = 1000
lowest_key = None
for key in queue:
if queue[key] < lowest:
lowest = queue[key]
lowest_key = key
del queue[lowest_key]
if distance[lowest_key] == 1000:
print("No traversable paths left")
break
elif lowest_key == finish:
shortest_path = []
while True:
temp_val = visited[lowest_key]
shortest_path.append(temp_val)
lowest_key = visited[lowest_key]
if lowest_key == start:
break
print(shortest_path)
else:
for neighbour in self.nodes[lowest_key].keys(): # checks neighbours of node released from pq
# adds value of neighbour arc to distance of previous node
alt_path = distance[lowest_key] + self.nodes[lowest_key][neighbour]
# if new path is shorter than distance of node in pq , then pq should be updated
if alt_path < distance[neighbour]:
distance[neighbour] = alt_path # changes distance
visited[neighbour] = lowest_key # adds this node to visited dict
# now changes are made to pq
for node in queue.keys():
if node == neighbour:
queue[node] = alt_path
g = Graph()
g.add_node('A', {'B': 5, 'C': 1})
g.add_node('B', {'D': 2, 'A': 5})
g.add_node('C', {'D': 9, 'A': 1})
g.add_node('D',{'B': 2, 'C': 9})
g.shortest_path("A",'D')