Scribd
Upload
2 views2 pages

Dijkstra's Algorithm for Shortest Paths

The document explains Dijkstra's Algorithm for finding the shortest path from a single source vertex to all other vertices in a weighted graph with non-negative weights. It outlines the algorithm's steps, provides Python code for implementation, and includes an example graph with sample output. The time complexity is O(E log V) and space complexity is O(V + E).

Uploaded by

ashaay1309
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
2 views2 pages

Dijkstra's Algorithm for Shortest Paths

The document explains Dijkstra's Algorithm for finding the shortest path from a single source vertex to all other vertices in a weighted graph with non-negative weights. It outlines the algorithm's steps, provides Python code for implementation, and includes an example graph with sample output. The time complexity is O(E log V) and space complexity is O(V + E).

Uploaded by

ashaay1309
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

SESSION 6: DIJKSTRA'S ALGORITHM (SINGLE SOURCE SHORTEST PATH)

Q1. Implement Dijkstra's Algorithm for finding the shortest path from a single source vertex to all other

vertices in a weighted graph.

Answer:

Dijkstra's algorithm finds the shortest path from a source vertex to all other vertices in a weighted graph

(non-negative weights) using a greedy approach.

Algorithm Steps:

1. Assign dist[source] = 0, others = INF.

2. Select vertex u with smallest temporary distance.

3. For each neighbor v of u, if dist[v] > dist[u] + weight(u,v), update it.

4. Repeat until all vertices are processed.

Python Code:

import heapq

def dijkstra(graph, start):

dist = {v: float('inf') for v in graph}

dist[start] = 0

pq = [(0, start)]

while pq:

d, u = [Link](pq)

if d > dist[u]:

continue

for v, w in graph[u]:

if dist[v] > d + w:

dist[v] = d + w

[Link](pq, (dist[v], v))

return dist

# Example graph
graph = {

'A': [('B', 4), ('C', 2)],

'B': [('C', 1), ('D', 5)],

'C': [('D', 8), ('E', 10)],

'D': [('E', 2)],

'E': []

result = dijkstra(graph, 'A')

print("Shortest distances from A:", result)

Sample Output:

Shortest distances from A: {'A': 0, 'B': 3, 'C': 2, 'D': 8, 'E': 10}

Explanation:

- Initially, distance from A to all vertices = INF except A = 0.

- After processing neighbors, updates continue until shortest paths are found.

- Final distances: A=0, B=3, C=2, D=8, E=10

Time Complexity: O(E log V)

Space Complexity: O(V + E)

You might also like