Scribd
Upload
39 views3 pages

Dijkstra's Algorithm

The document presents a Python implementation of Dijkstra's algorithm for finding the shortest path in a graph. It includes user input for the number of nodes, edges, and their respective weights, followed by the calculation of shortest distances from a specified start node. The output displays the shortest distances from the start node to all other nodes in the graph.

Uploaded by

Harshada Atpadkar
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
39 views3 pages

Dijkstra's Algorithm

The document presents a Python implementation of Dijkstra's algorithm for finding the shortest path in a graph. It includes user input for the number of nodes, edges, and their respective weights, followed by the calculation of shortest distances from a specified start node. The output displays the shortest distances from the start node to all other nodes in the graph.

Uploaded by

Harshada Atpadkar
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 3

# Program to implement Dijkstra’s shortest

path in python
import heapq
def dijkstra(graph, start):

distances = {node: float('infinity') for node in graph}

distances[start] = 0

priority_queue = [(0, start)]

while priority_queue:
current_distance, current_node =
heapq.heappop(priority_queue)
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(priority_queue, (distance, neighbor))
return distances
graph = {}
n = int(input("Enter number of nodes: "))
for _ in range(n):

node = input("Enter node name: ")

graph[node] = {}

edges = int(input(f"Enter number of edges for node {node}: "))

for _ in range(edges):

neighbor, weight = input("Enter neighbor node and weight (space-


separated): ").split() graph[node][neighbor] = int(weight)
start_node = input("Enter start node: ")

shortest_distances = dijkstra(graph, start_node)

print("\nShortest distances from start node:")

for node, distance in shortest_distances.items():

print(f"Distance to {node}: {distance}")

Enter number of nodes: 4


Enter node name: A

Enter number of edges for node A: 2

Enter neighbor node and weight (space-separated): B 1

Enter neighbor node and weight (space-separated): C 4

Enter node name: B

Enter number of edges for node B: 2

Enter neighbor node and weight (space-separated): A 1

Enter neighbor node and weight (space-separated): D 2

Enter node name: C Enter number of edges for node C: 1

Enter neighbor node and weight (space-separated): D 3

Enter node name: D Enter number of edges for node D: 1

Enter neighbor node and weight (space-separated): B 2

Enter start node: A


Shortest distances from start node:

Distance to A: 0

Distance to B: 1

Distance to C: 4

Distance to D: 3

You might also like