Algorithms and Data Structures with Python

Practical Exercises for Chapter 8

These exercises are designed to enhance understanding of advanced graph algorithms, providing practical experience in applying these techniques to solve complex problems.

Exercise 1: Implementing Dijkstra's Algorithm

• Write a function to perform Dijkstra's algorithm for finding the shortest path from a single source to all other nodes in a weighted graph.
• Example graph: { 'A': {'B': 1, 'C': 4}, 'B': {'C': 2, 'D': 5}, 'C': {'D': 1}, 'D': {} }, and start node: 'A'.

Solution:

import heapq

 

def dijkstra(graph, start):

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

distances[start] = 0

pq = [(0, start)]

 

while pq:

current_distance, current_vertex = heapq.heappop(pq)

 

for neighbor, weight in graph[current_vertex ...