Semanas 21 a 23 Grafos Ponderados

Semanas 21 a 23: Grafos Ponderados

Objetivo

Extender el bloque de grafos hacia caminos mínimos con pesos, detección de ciclos negativos, caminos mínimos entre todos los pares, árboles de expansión mínima y variantes aplicadas.

Estado del Avance Actual

• Problemas implementados acumulados: 116.
• Tests automatizados acumulados: 297.
• Módulo agregado: src/patterns/weighted_graphs.rs.
• Tests agregados: tests/weighted_graphs_test.rs.

Problemas Implementados

Problema	Patrón	API
Dijkstra Shortest Paths	Heap + relajación	dijkstra_shortest_paths
Network Delay Time	Dijkstra	network_delay_time
Bellman-Ford Shortest Paths	Relajación repetida	bellman_ford_shortest_paths
Floyd-Warshall All Pairs	Programación dinámica sobre grafos	floyd_warshall_all_pairs
Prim Minimum Spanning Tree	MST + heap	prim_minimum_spanning_tree_weight
Kruskal Minimum Spanning Tree	MST + Union-Find	kruskal_minimum_spanning_tree_weight
Cheapest Flights Within K Stops	Bellman-Ford limitado	cheapest_flight_within_k_stops
Path With Minimum Effort	Dijkstra sobre grid	minimum_effort_path
Critical Connections in a Network	Tarjan para puentes	critical_connections
Strongly Connected Components	Tarjan para SCC	strongly_connected_components
Min Cost to Connect All Points	MST con distancia Manhattan	min_cost_connect_points
Find Critical and Pseudo-Critical Edges in MST	Kruskal con arista forzada/prohibida	find_critical_and_pseudo_critical_edges

Ideas Clave

• BFS sirve cuando todas las aristas cuestan lo mismo.
• Dijkstra sirve con pesos no negativos y usa un heap para expandir el nodo pendiente más barato.
• Bellman-Ford soporta pesos negativos y detecta ciclos negativos alcanzables.
• Floyd-Warshall compara cada nodo como posible intermediario para calcular caminos mínimos entre todos los pares.
• Prim crece un árbol desde un nodo usando la arista frontera más barata.
• Kruskal ordena aristas y usa Union-Find para evitar ciclos al construir el MST.
• Vuelos con límite de paradas se resuelve relajando aristas por número máximo de vuelos permitidos.
• Minimum Effort Path usa Dijkstra, pero la distancia de una ruta es el mayor salto de altura visto hasta ese punto.
• Tarjan detecta puentes comparando el tiempo de descubrimiento de un nodo con el low-link de sus vecinos.
• Tarjan también encuentra componentes fuertemente conectados manteniendo una pila activa y cerrando una componente cuando low[node] == discovery[node].
• Conectar puntos con costo mínimo se modela como MST sobre un grafo completo implícito.
• Clasificar aristas de un MST requiere comparar el MST base contra ejecuciones de Kruskal excluyendo o forzando cada arista.
• Un nodo no alcanzable debe permanecer como None, no como una distancia falsa.
• En grafos ponderados, validar índices de nodos evita mezclar errores de datos con errores del algoritmo.

Complejidad

Algoritmo	Tiempo	Espacio
Dijkstra con heap	O((V + E) log V)	O(V + E)
Network Delay Time	O((V + E) log V)	O(V + E)
Bellman-Ford	O(V * E)	O(V)
Floyd-Warshall	O(V^3)	O(V^2)
Prim	O(E log V)	O(V + E)
Kruskal	O(E log E)	O(V) extra
Cheapest Flights Within K Stops	O(K * E)	O(V)
Path With Minimum Effort	O(m * n * log(m * n))	O(m * n)
Critical Connections	O(V + E)	O(V + E)
Strongly Connected Components	O(V + E)	O(V + E)
Min Cost to Connect All Points	O(n^2)	O(n)
Find Critical and Pseudo-Critical Edges	O(E^2 * α(V))	O(V + E)

Siguiente Paso

Iniciar la fase 4 con Fenwick Tree y Segment Tree para consultas por rangos.