patternpythonMinor

Dijkstra's algorithm using a dictionary for the priority queue

Submitted by: @import:stackexchange-codereview·Mar 10, 2026·

Viewed 0 times

prioritythedijkstraalgorithmforusingdictionaryqueue

Problem

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]

Solution

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  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.

Code Snippets

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)

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

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

Context

StackExchange Code Review Q#142734, answer score: 4

Revisions (0)

No revisions yet.