Menu iconMenu iconAlgorithms and Data Structures with Python
Algorithms and Data Structures with Python

Chapter 8: Networks and Paths: Advanced Graph Algorithms

Chapter 8: Practical Exercises of Networks and Paths: Advanced Graph Algorithms

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].items():
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))

    return distances

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

Exercise 2: Finding Bridges in a Graph

  • Implement an algorithm to find all bridges in an undirected graph.
  • Example graph: Use the graph from Exercise 1.

Solution:

from collections import defaultdict

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = defaultdict(list)
        self.time = 0

    def add_edge(self, u, v):
        self.graph[u].append(v)
        self.graph[v].append(u)

    def bridge_util(self, u, visited, low, disc, parent, bridges):
        visited[u] = True
        disc[u] = self.time
        low[u] = self.time
        self.time += 1

        for v in self.graph[u]:
            if not visited[v]:
                parent[v] = u
                self.bridge_util(v, visited, low, disc, parent, bridges)
                low[u] = min(low[u], low[v])

                if low[v] > disc[u]:
                    bridges.append((u, v))
            elif v != parent[u]:
                low[u] = min(low[u], disc[v])

    def find_bridges(self):
        visited = [False] * self.V
        disc = [float("Inf")] * self.V
        low = [float("Inf")] * self.V
        parent = [-1] * self.V
        bridges = []

        for i in range(self.V):
            if not visited[i]:
                self.bridge_util(i, visited, low, disc, parent, bridges)
        return bridges

# Example Usage
g = Graph(4)
g.add_edge(0, 1)
g.add_edge(1, 2)
g.add_edge(2, 3)
print(g.find_bridges())  # Output: [(2, 3)]

Exercise 3: Implementing the Floyd-Warshall Algorithm

  • Create a function to find the shortest distances between every pair of vertices in a given weighted graph.
  • Example graph: Use the graph from Exercise 1.

Solution:

def floyd_warshall(graph):
    keys = list(graph.keys())
    n = len(keys)
    dist = {k: {k2: float('inf') for k2 in keys} for k in keys}
    for key in keys:
        dist[key][key] = 0
    for key, val in graph.items():
        for adj, weight in val.items():
            dist[key][adj] = weight

    for k in keys:
        for i in keys:
            for j in keys:
                if dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]

    return dist

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

Chapter 8: Practical Exercises of Networks and Paths: Advanced Graph Algorithms

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].items():
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))

    return distances

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

Exercise 2: Finding Bridges in a Graph

  • Implement an algorithm to find all bridges in an undirected graph.
  • Example graph: Use the graph from Exercise 1.

Solution:

from collections import defaultdict

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = defaultdict(list)
        self.time = 0

    def add_edge(self, u, v):
        self.graph[u].append(v)
        self.graph[v].append(u)

    def bridge_util(self, u, visited, low, disc, parent, bridges):
        visited[u] = True
        disc[u] = self.time
        low[u] = self.time
        self.time += 1

        for v in self.graph[u]:
            if not visited[v]:
                parent[v] = u
                self.bridge_util(v, visited, low, disc, parent, bridges)
                low[u] = min(low[u], low[v])

                if low[v] > disc[u]:
                    bridges.append((u, v))
            elif v != parent[u]:
                low[u] = min(low[u], disc[v])

    def find_bridges(self):
        visited = [False] * self.V
        disc = [float("Inf")] * self.V
        low = [float("Inf")] * self.V
        parent = [-1] * self.V
        bridges = []

        for i in range(self.V):
            if not visited[i]:
                self.bridge_util(i, visited, low, disc, parent, bridges)
        return bridges

# Example Usage
g = Graph(4)
g.add_edge(0, 1)
g.add_edge(1, 2)
g.add_edge(2, 3)
print(g.find_bridges())  # Output: [(2, 3)]

Exercise 3: Implementing the Floyd-Warshall Algorithm

  • Create a function to find the shortest distances between every pair of vertices in a given weighted graph.
  • Example graph: Use the graph from Exercise 1.

Solution:

def floyd_warshall(graph):
    keys = list(graph.keys())
    n = len(keys)
    dist = {k: {k2: float('inf') for k2 in keys} for k in keys}
    for key in keys:
        dist[key][key] = 0
    for key, val in graph.items():
        for adj, weight in val.items():
            dist[key][adj] = weight

    for k in keys:
        for i in keys:
            for j in keys:
                if dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]

    return dist

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

Chapter 8: Practical Exercises of Networks and Paths: Advanced Graph Algorithms

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].items():
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))

    return distances

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

Exercise 2: Finding Bridges in a Graph

  • Implement an algorithm to find all bridges in an undirected graph.
  • Example graph: Use the graph from Exercise 1.

Solution:

from collections import defaultdict

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = defaultdict(list)
        self.time = 0

    def add_edge(self, u, v):
        self.graph[u].append(v)
        self.graph[v].append(u)

    def bridge_util(self, u, visited, low, disc, parent, bridges):
        visited[u] = True
        disc[u] = self.time
        low[u] = self.time
        self.time += 1

        for v in self.graph[u]:
            if not visited[v]:
                parent[v] = u
                self.bridge_util(v, visited, low, disc, parent, bridges)
                low[u] = min(low[u], low[v])

                if low[v] > disc[u]:
                    bridges.append((u, v))
            elif v != parent[u]:
                low[u] = min(low[u], disc[v])

    def find_bridges(self):
        visited = [False] * self.V
        disc = [float("Inf")] * self.V
        low = [float("Inf")] * self.V
        parent = [-1] * self.V
        bridges = []

        for i in range(self.V):
            if not visited[i]:
                self.bridge_util(i, visited, low, disc, parent, bridges)
        return bridges

# Example Usage
g = Graph(4)
g.add_edge(0, 1)
g.add_edge(1, 2)
g.add_edge(2, 3)
print(g.find_bridges())  # Output: [(2, 3)]

Exercise 3: Implementing the Floyd-Warshall Algorithm

  • Create a function to find the shortest distances between every pair of vertices in a given weighted graph.
  • Example graph: Use the graph from Exercise 1.

Solution:

def floyd_warshall(graph):
    keys = list(graph.keys())
    n = len(keys)
    dist = {k: {k2: float('inf') for k2 in keys} for k in keys}
    for key in keys:
        dist[key][key] = 0
    for key, val in graph.items():
        for adj, weight in val.items():
            dist[key][adj] = weight

    for k in keys:
        for i in keys:
            for j in keys:
                if dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]

    return dist

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

Chapter 8: Practical Exercises of Networks and Paths: Advanced Graph Algorithms

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].items():
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))

    return distances

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

Exercise 2: Finding Bridges in a Graph

  • Implement an algorithm to find all bridges in an undirected graph.
  • Example graph: Use the graph from Exercise 1.

Solution:

from collections import defaultdict

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = defaultdict(list)
        self.time = 0

    def add_edge(self, u, v):
        self.graph[u].append(v)
        self.graph[v].append(u)

    def bridge_util(self, u, visited, low, disc, parent, bridges):
        visited[u] = True
        disc[u] = self.time
        low[u] = self.time
        self.time += 1

        for v in self.graph[u]:
            if not visited[v]:
                parent[v] = u
                self.bridge_util(v, visited, low, disc, parent, bridges)
                low[u] = min(low[u], low[v])

                if low[v] > disc[u]:
                    bridges.append((u, v))
            elif v != parent[u]:
                low[u] = min(low[u], disc[v])

    def find_bridges(self):
        visited = [False] * self.V
        disc = [float("Inf")] * self.V
        low = [float("Inf")] * self.V
        parent = [-1] * self.V
        bridges = []

        for i in range(self.V):
            if not visited[i]:
                self.bridge_util(i, visited, low, disc, parent, bridges)
        return bridges

# Example Usage
g = Graph(4)
g.add_edge(0, 1)
g.add_edge(1, 2)
g.add_edge(2, 3)
print(g.find_bridges())  # Output: [(2, 3)]

Exercise 3: Implementing the Floyd-Warshall Algorithm

  • Create a function to find the shortest distances between every pair of vertices in a given weighted graph.
  • Example graph: Use the graph from Exercise 1.

Solution:

def floyd_warshall(graph):
    keys = list(graph.keys())
    n = len(keys)
    dist = {k: {k2: float('inf') for k2 in keys} for k in keys}
    for key in keys:
        dist[key][key] = 0
    for key, val in graph.items():
        for adj, weight in val.items():
            dist[key][adj] = weight

    for k in keys:
        for i in keys:
            for j in keys:
                if dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]

    return dist

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