# 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

**Exercise 1: Implementing Dijkstra's Algorithm**

- 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**

- 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))