Dijkstra’s algorithm is a popular algorithm for finding the shortest path between two nodes in a graph with non-negative edge weights.
AdityaBegginer
Write a Python program to find the shortest path in a weighted directed graph using Dijkstra’s algorithm?
Share
import sys
class Graph:
def __init__(self, vertices):
self.vertices = vertices
self.graph = [[0 for _ in range(vertices)] for _ in range(vertices)]
def min_distance(self, dist, visited):
min_dist = sys.maxsize
min_index = -1
for v in range(self.vertices):
if dist[v] < min_dist and not visited[v]:
min_dist = dist[v]
min_index = v
return min_index
def dijkstra(self, start):
dist = [sys.maxsize] * self.vertices
dist[start] = 0
visited = [False] * self.vertices
for _ in range(self.vertices):
u = self.min_distance(dist, visited)
visited[u] = True
for v in range(self.vertices):
if (
not visited[v]
and self.graph[u][v] != 0
and dist[u] != sys.maxsize
and dist[u] + self.graph[u][v] < dist[v]
):
dist[v] = dist[u] + self.graph[u][v]
self.print_solution(dist)
def print_solution(self, dist):
print(“Vertex\tDistance from Source”)
for v in range(self.vertices):
print(f”{v}\t\t{dist[v]}”)
# Example usage
graph = Graph(6)
graph.graph = [
[0, 2, 4, 0, 0, 0],
[0, 0, 1, 7, 0, 0],
[0, 0, 0, 0, 3, 0],
[0, 0, 0, 0, 0, 1],
[0, 0, 0, 2, 0, 5],
[0, 0, 0, 0, 0, 0]
]
start_vertex = 0
graph.dijkstra(start_vertex)
import heapq
def dijkstra(graph, start):
distances = {node: float(‘inf’) for node in graph}
distances[start] = 0
pq = [(0, start)]
while pq:
current_distance, current_node = heapq.heappop(pq)
# Skip if already visited
if current_distance > distances[current_node]:
continue
for neighbor, weight in graph[current_node].items():
distance = current_distance + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(pq, (distance, neighbor))
return distances
# Example usage
graph = {
‘A’: {‘B’: 5, ‘C’: 2},
‘B’: {‘D’: 4},
‘C’: {‘B’: 1, ‘D’: 7},
‘D’: {‘E’: 3},
‘E’: {}
}
start_node = ‘A’
shortest_distances = dijkstra(graph, start_node)
print(“Shortest distances from node”, start_node + “:”)
for node, distance in shortest_distances.items():
print(“To node”, node + “:”, distance)