Scribd
Upload
5 views2 pages

Dijkstra's Algorithm Explained with Code

The document provides an overview of Dijkstra's Algorithm, which is used to find the shortest path from a source node to all other nodes in a weighted graph with non-negative weights. It outlines the algorithm's steps, including initializing distances, selecting the node with the smallest distance, and updating neighboring nodes. Additionally, it includes a Python implementation of the algorithm with an example graph.

Uploaded by

mohammadghouse9241607523
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
5 views2 pages

Dijkstra's Algorithm Explained with Code

The document provides an overview of Dijkstra's Algorithm, which is used to find the shortest path from a source node to all other nodes in a weighted graph with non-negative weights. It outlines the algorithm's steps, including initializing distances, selecting the node with the smallest distance, and updating neighboring nodes. Additionally, it includes a Python implementation of the algorithm with an example graph.

Uploaded by

mohammadghouse9241607523
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

Research on Algorithms (Enhanced with Code

Examples)

2. Dijkstra’s Algorithm (Enhanced)


Category: Graph Algorithm
Purpose: Find the shortest path from a source node to all other nodes in a weighted graph
(non-negative weights).

How It Works:
• Initializes distances from the source as infinity (except for the source itself).
• Picks the node with the smallest tentative distance.
• Updates neighbouring nodes’ distances.
• Repeats until all nodes have been visited.

Example Code (Python Implementation with Explanation):


import heapq

def dijkstra(graph, start):


# Initialize distances with infinity for all nodes except the start node
distances = {node: float('inf') for node in graph}
distances[start] = 0

# Priority queue to store (distance, node)


pq = [(0, start)]

while pq:
# Get node with smallest distance
current_distance, current_node = [Link](pq)

# If already found a shorter path, skip


if current_distance > distances[current_node]:
continue

# Explore neighbors
for neighbor, weight in graph[current_node].items():
new_distance = current_distance + weight
if new_distance < distances[neighbor]:
distances[neighbor] = new_distance
[Link](pq, (new_distance, neighbor))

return distances

# Example usage
graph = {
'A': {'B': 1, 'C': 4},
'B': {'A': 1, 'C': 2, 'D': 5},
'C': {'A': 4, 'B': 2, 'D': 1},
'D': {'B': 5, 'C': 1}
}
print(dijkstra(graph, 'A'))

You might also like