I am trying to implement the Dijkstra algorithm as follows:
from collections import defaultdict
class Graph:
def __init__(self):
self.nodes = set()
self.edges = defaultdict(list)
self.distances = {}
def add_node(self, value):
self.nodes.add(value)
def add_edge(self, from_node, to_node, distance):
self.edges[from_node].append(to_node)
self.edges[to_node].append(from_node)
self.distances[(from_node, to_node)] = distance
def dijsktra(graph, initial):
visited = {initial: 0}
path = {}
nodes = set(graph.nodes)
while nodes:
min_node = None
for node in nodes:
if node in visited:
if min_node is None:
min_node = node
elif visited[node] < visited[min_node]:
min_node = node
if min_node is None:
break
nodes.remove(min_node)
current_weight = visited[min_node]
for edge in graph.edges[min_node]:
weight = current_weight + graph.distances[(min_node, edge)]
if edge not in visited or weight < visited[edge]:
visited[edge] = weight
path[edge] = min_node
return visited, path
I have 36 connecting nodes with directional weights. I have already made my graph. The nodes and connecting edges with weights are as follows:
print(g.nodes)
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24,
25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35}
print(g.distances)
{(1, 7): 2, (1, 2): 2, (2, 1): 1, (2, 3): 4, (3, 2): 2, (3, 9): 2, (5, 11): 1, (5, 6): 1,
(6, 5): 3, (6, 12): 2, (7, 1): 1, (7, 13): 3, (9, 3): 4, (9, 15): 1, (11, 5): 3, (11, 17):
3, (11, 12): 2, (12, 6): 1, (12, 11): 1, (12, 18): 2, (13, 7): 2, (13, 14): 2, (14, 13): 3,
(14, 20): 1, (14, 15): 1, (15, 9): 2, (15, 14): 2, (15, 21): 2, (15, 16): 4, (16, 15): 1,
(16, 22): 1, (16, 17): 3, (17, 11): 1, (17, 16): 4, (17, 18): 2, (18, 12): 2, (18, 17): 3,
(18, 24): 1, (20, 14): 2, (20, 26): 1, (20, 21): 2, (21, 15): 1, (21, 20): 1, (21, 27): 1,
(21, 22): 1, (22, 16): 4, (22, 21): 2, (24, 18): 2, (24, 30): 1, (25, 31): 1, (25, 26): 1,
(26, 20): 1, (26, 25): 2, (26, 27): 1, (27, 21): 2, (27, 26): 1, (27, 33): 4, (30, 24): 1,
(30, 36): 1, (31, 25): 2, (33, 27): 1, (33, 34): 2, (34, 33): 4, (34, 35): 2, (35, 34): 2,
(35, 36): 1, (36, 30): 1, (36, 35): 2}
But I am getting an error on execution. Seems like it is due to removing of None. I have tried changing None by inf. Still getting the same error. What should I do now?
Here is the function execution and error:
visited,path = dijsktra(g,0)
---------------------------------------------------------------------------
KeyError Traceback (most recent call last)
<ipython-input-44-c4a3ba9a32e3> in <module>
----> 1 parent,path=dijsktra(g,0)
<ipython-input-25-cd9030508fd7> in dijsktra(graph, initial)
34
35
---> 36 nodes.remove(min_node)
37 current_weight = visited[min_node]
38
KeyError: None
How can I remove the bug? Please anyone resolve this issue. It will be helpful.
Thank you!
Edits:
Here is the link to the code I used to generate the g.nodes and g.distances
I don't believe your dijskstra function is implementing the algorithm correctly. You normally initialize a dist (distance) dictionary where the keys are the graph's node values and its values are initialized to infinity (or suitable large value) except for the initial node that is initialized with 0. This dictionary represents the initial distance of every node from the initial node. Then every loop iteration looks for an unvisited node (which all nodes initially are) looking for the node with the minimal distance from the initial node). The first time through the loop this would be the initial node itself. This node is then removed from the unvisited nodes and the distance from this node to all nodes that neighbor this node are updated. Eventually, all nodes are removed from the unvisited node list and we are done. I have modified what the function returns. Since there is no longer a concept of a visited dictionary, it returns the dist dictionary giving the distance to every node:
from collections import defaultdict
class Graph:
def __init__(self):
self.nodes = set()
self.edges = defaultdict(list)
self.distances = {}
def add_node(self, value):
self.nodes.add(value)
def add_edge(self, from_node, to_node, distance):
self.edges[from_node].append(to_node)
self.edges[to_node].append(from_node)
self.distances[(from_node, to_node)] = distance
self.distances[(to_node, from_node)] = distance
def dijsktra(graph, initial): # should be dijkstra
nodes = set(graph.nodes) # unvisted nodes
path = {}
dist = {node: 999999999999999 for node in nodes} # assume this is larger than any actual distance
dist[initial] = 0
while nodes: # we still have unvisted nodes
min_node = None
for node in nodes:
if min_node is None:
min_node = node
elif dist[node] < dist[min_node]:
min_node = node
nodes.remove(min_node)
current_weight = dist[min_node]
for edge in graph.edges[min_node]:
weight = current_weight + graph.distances[(min_node, edge)]
if weight < dist[edge]:
dist[edge] = weight
path[edge] = min_node
return dist, path
"code to generate nodes:"
g=Graph()
g.add_node(1)
g.add_node(2)
g.add_node(3)
g.add_node(4)
g.add_edge(1, 2, 1)
g.add_edge(1, 3, 2)
g.add_edge(2, 4, 5)
g.add_edge(3, 4, 1)
print(dijsktra(g, 1))
Prints:
({1: 0, 2: 1, 3: 2, 4: 3}, {2: 1, 3: 1, 4: 3})
Update
I thought I would add a modified version that is more efficient. Instead of having all the nodes initially in our "unvisited list" of nodes to process, we maintain a list of nodes whose final distance from the initial node has been computed but its adjacent nodes not yet processed. From this list we always want to select the node whose distance from the initial node has the minimal value. To accomplish this, each node is now a tuple consisting of its distance from the initial node and its node value. These nodes are maintained in a heap queue that automatically yields the node with the minimal value:
from collections import defaultdict
from heapq import heappop, heappush
class Graph:
def __init__(self):
self.nodes = set()
self.edges = defaultdict(list)
self.distances = {}
def add_node(self, value):
self.nodes.add(value)
def add_edge(self, from_node, to_node, distance):
self.edges[from_node].append(to_node)
self.edges[to_node].append(from_node)
self.distances[(from_node, to_node)] = distance
self.distances[(to_node, from_node)] = distance
def dijkstra(graph, initial): # should be dijkstra
visited = set()
path = {}
priority_queue = []
INFINITY = float('inf')
distances = {node: INFINITY for node in graph.nodes}
dist[initial] = 0
heappush(priority_queue, (0, initial)) # (cost, initial)
while priority_queue:
_, min_node = heappop(priority_queue)
visited.add(min_node)
current_weight = dist[min_node]
for edge in graph.edges[min_node]: # this is really a node and not an edge
if edge in visited:
continue
weight = current_weight + graph.distances[(min_node, edge)]
if weight < dist[edge]:
dist[edge] = weight
path[edge] = min_node
heappush(priority_queue, (weight, edge))
return dist, path
g = Graph()
g.add_node(1)
g.add_node(2)
g.add_node(3)
g.add_node(4)
g.add_edge(1, 2, 1)
g.add_edge(1, 3, 2)
g.add_edge(2, 4, 5)
g.add_edge(3, 4, 1)
print(dijkstra(g, 1))