You've learned this already. ✅
Click here to view the next lesson.
Capítulo 8: Redes y Caminos: Algoritmos Avanzados de Grafos
Ejercicios Prácticos para el Capítulo 8
Estos ejercicios están diseñados para mejorar la comprensión de algoritmos de grafos avanzados, brindando experiencia práctica en la aplicación de estas técnicas para resolver problemas complejos.
Ejercicio 1: Implementación del Algoritmo de Dijkstra
- Escriba una función para realizar el algoritmo de Dijkstra para encontrar el camino más corto desde una única fuente hasta todos los demás nodos en un grafo ponderado.
- Grafo de ejemplo:
{ 'A': {'B': 1, 'C': 4}, 'B': {'C': 2, 'D': 5}, 'C': {'D': 1}, 'D': {} }, y nodo de inicio:'A'.
Solución:
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}Ejercicio 2: Encontrar Puentes en un Grafo
- Implementar un algoritmo para encontrar todos los puentes en un grafo no dirigido.
- Grafo de ejemplo: Usa el grafo del Ejercicio 1.
Solución:
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)]Ejercicio 3: Implementación del Algoritmo de Floyd-Warshall
- Crear una función para encontrar las distancias más cortas entre cada par de vértices en un grafo ponderado dado.
- Grafo de ejemplo: Usa el grafo del Ejercicio 1.
Solución:
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))Ejercicios Prácticos para el Capítulo 8
Estos ejercicios están diseñados para mejorar la comprensión de algoritmos de grafos avanzados, brindando experiencia práctica en la aplicación de estas técnicas para resolver problemas complejos.
Ejercicio 1: Implementación del Algoritmo de Dijkstra
- Escriba una función para realizar el algoritmo de Dijkstra para encontrar el camino más corto desde una única fuente hasta todos los demás nodos en un grafo ponderado.
- Grafo de ejemplo:
{ 'A': {'B': 1, 'C': 4}, 'B': {'C': 2, 'D': 5}, 'C': {'D': 1}, 'D': {} }, y nodo de inicio:'A'.
Solución:
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}Ejercicio 2: Encontrar Puentes en un Grafo
- Implementar un algoritmo para encontrar todos los puentes en un grafo no dirigido.
- Grafo de ejemplo: Usa el grafo del Ejercicio 1.
Solución:
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)]Ejercicio 3: Implementación del Algoritmo de Floyd-Warshall
- Crear una función para encontrar las distancias más cortas entre cada par de vértices en un grafo ponderado dado.
- Grafo de ejemplo: Usa el grafo del Ejercicio 1.
Solución:
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))Ejercicios Prácticos para el Capítulo 8
Estos ejercicios están diseñados para mejorar la comprensión de algoritmos de grafos avanzados, brindando experiencia práctica en la aplicación de estas técnicas para resolver problemas complejos.
Ejercicio 1: Implementación del Algoritmo de Dijkstra
- Escriba una función para realizar el algoritmo de Dijkstra para encontrar el camino más corto desde una única fuente hasta todos los demás nodos en un grafo ponderado.
- Grafo de ejemplo:
{ 'A': {'B': 1, 'C': 4}, 'B': {'C': 2, 'D': 5}, 'C': {'D': 1}, 'D': {} }, y nodo de inicio:'A'.
Solución:
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}Ejercicio 2: Encontrar Puentes en un Grafo
- Implementar un algoritmo para encontrar todos los puentes en un grafo no dirigido.
- Grafo de ejemplo: Usa el grafo del Ejercicio 1.
Solución:
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)]Ejercicio 3: Implementación del Algoritmo de Floyd-Warshall
- Crear una función para encontrar las distancias más cortas entre cada par de vértices en un grafo ponderado dado.
- Grafo de ejemplo: Usa el grafo del Ejercicio 1.
Solución:
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))Ejercicios Prácticos para el Capítulo 8
Estos ejercicios están diseñados para mejorar la comprensión de algoritmos de grafos avanzados, brindando experiencia práctica en la aplicación de estas técnicas para resolver problemas complejos.
Ejercicio 1: Implementación del Algoritmo de Dijkstra
- Escriba una función para realizar el algoritmo de Dijkstra para encontrar el camino más corto desde una única fuente hasta todos los demás nodos en un grafo ponderado.
- Grafo de ejemplo:
{ 'A': {'B': 1, 'C': 4}, 'B': {'C': 2, 'D': 5}, 'C': {'D': 1}, 'D': {} }, y nodo de inicio:'A'.
Solución:
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}Ejercicio 2: Encontrar Puentes en un Grafo
- Implementar un algoritmo para encontrar todos los puentes en un grafo no dirigido.
- Grafo de ejemplo: Usa el grafo del Ejercicio 1.
Solución:
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)]Ejercicio 3: Implementación del Algoritmo de Floyd-Warshall
- Crear una función para encontrar las distancias más cortas entre cada par de vértices en un grafo ponderado dado.
- Grafo de ejemplo: Usa el grafo del Ejercicio 1.
Solución:
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))