I want to implement Djikstra's algorithm in Python. Thus, when I store nodes of a graph in a priority Queue, I want them to be sorted in the order of their distances from the source node. How can I change the priority function so that the nodes are sorted in this way? I am using the PriorityQueue Class in the queue module. By default, the integers entered are sorted in descending order, i.e., the priority of the smallest element is the highest. I want to enter a priority function which sorts nodes on the basis of the distance attribute in the node object. Following is the node class - class node node distance Can someone help me out here?
As the documentation explains, PriorityQueue's in python do not seem to accept custom comparison functions. However, you can use min and a regular list to achieve what you want since the min function call accepts a key function that decides what the smallest item is.
class node():
def __init__(self, dist):
self.dist = dist
def get_dist(node):
return node.dist
nodes = [node(4), node(413), node(2), node(14), node(5)]
out = min(nodes, key=get_dist)
nodes.remove(out)
print('popped out:', out.dist) # popped out: 2
out = min(nodes, key=get_dist)
nodes.remove(out)
print('popped out:', out.dist) # popped out: 4
out = min(nodes, key=get_dist)
nodes.remove(out)
print('popped out:', out.dist) # popped out: 5