Skip to content

Instantly share code, notes, and snippets.

@econchick
Last active December 22, 2023 13:32
Show Gist options
  • Save econchick/4666413 to your computer and use it in GitHub Desktop.
Save econchick/4666413 to your computer and use it in GitHub Desktop.
Python implementation of Dijkstra's Algorithm
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.distance[(min_node, edge)]
if edge not in visited or weight < visited[edge]:
visited[edge] = weight
path[edge] = min_node
return visited, path
@ankur619158
Copy link

I am not able to understand what to pass in the second argument (initial) for dijsktra function. Can anyone please help me?

it is the starting node which has no parent that's why 0

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment