Join our newsletter
Harsh Shah
Mar 18,2024
Djikstra's Algorithm In Python
Table of contents
- Djikstra's Algorithm
- Algorithm
- Implementation
- Time Complexity
Djikstra's Algorithm
Algorithm
- Initialize an empty matrix and in the first column set the distance of the source vertex to be and rest other vertices to
- Find the vertex with the least distance Mark as visited.
- Check the neighbours of and check whether they are unvisited. If the neighbout is not visited, then check for If it is the case, then assign this value to
- Repeat steps (3) and (4) for all the unvisited vertices.
Implementation
Using a NumPy Array
def DjikstraAlgorithm(adj, source):
rows, cols, x = adj.shape
visited = {k: False for k in adj[rows]}
distance = {k: float('inf') for k in adj[rows]}
distance[source] = 0
for u in range(rows):
next_dist = min([distance[v] for v in range(rows)
if not visited[v]
])
next_vertex_list = [v for v in range(rows)
if not visited[v]
and distance[v] == next_dist
]
if not next_vertex_list:
break
next_vertex = min(next_vertex_list)
visited[next_vertex] = True
for i in range(cols):
if (adj[next_vertex, i, 0] == 1) and (not visited[i]):
if dist[i] > adj[next_vertex, i, 1] + next_dist:
dist[i] = adj[next_vertex, i, 1]
return distance
Using an Adjacency List
def DjikstrasAlgorithm(adjList, source):
vertices = len(adjList.keys())
visited = {k: False for k in range(vertices)}
distance = {k: float('inf') for k in range(vertices)}
distance[source] = 0
for i in adjList:
next_dist = min([distance[v] for v in adjList
if not visited[v]
])
next_vertex_list = [v for v in adjList
if not visited[v]
and distance[v] == next_dist
]
if not next_vertex_list:
break
next_vertex = min(next_vertex_list)
visited[next_vertex] = True
for v in adjList:
for neighbour, weight in v:
if weight + next_dist < distance[neighbour]:
distance[neighbour] = weight + next_dist
return distance Time Complexity
The time complexity for <span class="font-extrabold" key=1> Djikstra's Algorithm </span> in either of the two cases is $O(n^2).$ You can minimise this using <span class="font-extrabold" key=3> Heaps </span> as discussed in further articles. <span class="font-extrabold" key=5> Note: </span> Djikstra's Algorithm does not allow the presence of negative edge weights in the graph.
Subscribe to our newsletter
Close
Harsh Shah
I write articles on web dev and more specifically on react and next js.