Dijkstra's algorithm using a dictionary for the priority queue

Question

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

About the code:

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')

Answer 1

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

            CLOSED.add(current)

            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.