Dijkstra's algorithm using a dictionary for the priority queue

Unrelated to code:

1. This is my first project in Python using classes and algorithms.
2. 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

1. Dictionary used for priority queue.
2. 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.
3. This was all done on one single file.

What I would like from this:

1. 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.
2. 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')

• Could you post the working shortest path function? It does not matter if it is longer, we review working code Commented Sep 28, 2016 at 20:19
• As it is the code works as I simply add the root node on the end , but I will add modified version as well. Commented Sep 28, 2016 at 20:20
• Should be on there now. Commented Sep 28, 2016 at 20:25
• The priority queue data structure is implemented in the python library in the "heapq" module. You can do Djikstra without it, and just brute force search for the shortest next candidate, but that will be significantly slower on a large graph. You say you want to code your own. That should be in a list/array which follows the heap invariant. (want more info on implementing heap?) Commented Sep 28, 2016 at 23:59
• I have rolled back the last edit. Please see What to do when someone answers. Commented Oct 18, 2016 at 13:40

A bug

For the shortest path from A to D, your implementation shows [B, A], which is wrong.

Indentation error

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)


should be indented once to the right; otherwise your code does not compile.

Efficiency

Use the priority queue in order to speed up your implementation:

import heapq

class HeapEntry:
def __init__(self, node, priority):
self.node = node
self.priority = priority

def __lt__(self, other):
return self.priority < other.priority

class Graph:
def __init__(self):
self.nodes = {}

def add_node(self, key, neighbours):
self.nodes[key] = neighbours

def traceback_path(self, target, parents):
path = []
while target:
path.append(target)
target = parents[target]
return list(reversed(path))

def shortest_path(self, start, finish):
OPEN = [HeapEntry(start, 0.0)]
CLOSED = set()
parents = {start: None}
distance = {start: 0.0}

while OPEN:
current = heapq.heappop(OPEN).node

if current is finish:
return self.traceback_path(finish, parents)

if current in CLOSED:
continue

for child in self.nodes[current].keys():
if child in CLOSED:
continue
tentative_cost = distance[current] + self.nodes[current][child]

if child not in distance.keys() or distance[child] > tentative_cost:
distance[child] = tentative_cost
parents[child] = current
heap_entry = HeapEntry(child, tentative_cost)
heapq.heappush(OPEN, heap_entry)

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})
print(g.shortest_path("A", 'D'))


Note also that we do not need anymore

for node in self.nodes:
if node == start:
distance[node] = 0
queue[node] = 0
else:
distance[node] = 1000
queue[node] = 1000


Think about what happens if the graph is large but the terminal nodes are close to each other: you waste a lot of CPU cycles.

Hope that helps.