You've learned this already. ✅
Click here to view the next lesson.
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))