Caminos más cortos con pesos de arista no negativos

Casi todos los problemas de caminos más cortos de Oro involucran Dijkstra. Sin embargo, conviene aprender primero Bellman-Ford y Floyd-Warshall porque son más simples.

Bellman-Ford

Recursos
Fuente	Recurso	Notas
CPH	13.1 - Bellman-Ford	hasta, pero sin incluir, “Negative Cycles”

Floyd-Warshall

Tutorial

Recursos
Fuente	Recurso	Notas
CPH	13.3 - Floyd-Warshall	cálculo de ejemplo, código
cp-algo	Floyd-Warshall	código, por qué funciona
PAPS	12.3.3 - Floyd-Warshall	código, por qué funciona
CP2	4.5 - All-Pairs Shortest Paths

Floyd-Warshall incorrecto

De este artículo :

Un error habitual al implementar el algoritmo de Floyd–Warshall es desordenar los tres bucles anidados (el orden correcto es KIJ). Los algoritmos incorrectos IJK e IKJ no dan soluciones correctas para algunas instancias. Sin embargo, se puede demostrar que si se los repite tres veces, se obtienen las soluciones correctas.

Cabe enfatizar que estos arreglos (repetir algoritmos incorrectos tres veces) tienen la misma complejidad temporal que el algoritmo correcto de Floyd–Warshall salvo factores constantes. Por lo tanto, nuestros resultados sugieren que, si uno se confunde con el orden de los tres bucles anidados, se puede repetir el procedimiento tres veces por las dudas.

Problema

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	CSES	Shortest Routes II	Fácil	APSP	en el módulo

Explicación

Este problema pide calcular caminos más cortos entre cualquier par de vértices. Por eso Floyd-Warshall es adecuado, por el $N$ bajo ( $N \le 500$ ) y por la inclusión de pesos negativos.

Implementación

Complejidad temporal: $\mathcal{O}(N^3)$

C++JavaPython


#include <iostream>
#include <vector>
 
using std::cout;
using std::endl;
using std::vector;
 
constexpr long long BIG = 1e18;  // No podemos usar LLONG_MAX por desbordamiento
 
int main() {
	int n, m, q;
	std::cin >> n >> m >> q;
 
	vector<vector<long long>> min_dist(n, vector<long long>(n, BIG));
	for (int i = 0; i < m; i++) {
		int a, b;
		int c;
		std::cin >> a >> b >> c;
		a--;
		b--;
		if (c < min_dist[a][b]) { min_dist[a][b] = min_dist[b][a] = c; }
	}
 
	// Algoritmo de Floyd-Warshall
	for (int k = 0; k < n; k++) {
		for (int i = 0; i < n; i++) {
			for (int j = i + 1; j < n; j++) {
				long long new_dist = min_dist[i][k] + min_dist[k][j];
				if (new_dist < min_dist[i][j]) {
					min_dist[i][j] = min_dist[j][i] = new_dist;
				}
			}
		}
	}
 
	for (int i = 0; i < q; i++) {
		int a, b;
		std::cin >> a >> b;
		a--;
		b--;
 
		// Comprobar si los dos nodos son el mismo o no se pueden alcanzar
		if (a == b) {
			min_dist[a][b] = 0;
		} else if (min_dist[a][b] == BIG) {
			min_dist[a][b] = -1;
		}
 
		cout << min_dist[a][b] << '\n';
	}
}


import java.io.*;
import java.util.*;
 
public class ShortestRoutesII {
	// No podemos usar Long.MAX_VALUE por desbordamiento
	private static final long BIG = (long)1e18;
 
	public static void main(String[] args) {
		Kattio io = new Kattio();
 
		int n = io.nextInt();
		int m = io.nextInt();
		int q = io.nextInt();
 
		long[][] minDist = new long[n][n];
		for (int i = 0; i < n; i++) { Arrays.fill(minDist[i], BIG); }
		for (int i = 0; i < m; i++) {
			int a = io.nextInt() - 1;
			int b = io.nextInt() - 1;
			int c = io.nextInt();
			if (c < minDist[a][b]) { minDist[a][b] = minDist[b][a] = c; }
		}
 
		// Algoritmo de Floyd-Warshall
		for (int k = 0; k < n; k++) {
			for (int i = 0; i < n; i++) {
				for (int j = i + 1; j < n; j++) {
					long newDist = minDist[i][k] + minDist[k][j];
					if (newDist < minDist[i][j]) {
						minDist[i][j] = minDist[j][i] = newDist;
					}
				}
			}
		}
 
		for (int i = 0; i < q; i++) {
			int a = io.nextInt() - 1;
			int b = io.nextInt() - 1;
 
			// Comprobar si los dos nodos son el mismo o no se pueden alcanzar
			if (a == b) {
				minDist[a][b] = 0;
			} else if (minDist[a][b] == BIG) {
				minDist[a][b] = -1;
			}
 
			io.println(minDist[a][b]);
		}
 
		io.close();
	}
 
	// CodeSnip{Kattio}
}


# Se usa 1e18 en lugar de float('inf') por rendimiento
BIG = int(1e18)
 
n, m, q = map(int, input().split())
 
min_dist = [[BIG] * n for _ in range(n)]
 
for _ in range(m):
	a, b, c = map(int, input().split())
	a, b = a - 1, b - 1
	if c < min_dist[a][b]:
		min_dist[a][b] = min_dist[b][a] = c
 
# Algoritmo de Floyd-Warshall
for k in range(n):
	for i in range(n):
		for j in range(i + 1, n):
			new_dist = min_dist[i][k] + min_dist[k][j]
			if new_dist < min_dist[i][j]:
				min_dist[i][j] = min_dist[j][i] = new_dist
 
for _ in range(q):
	a, b = map(int, input().split())
	a, b = a - 1, b - 1
 
	# Comprobar si los dos nodos son el mismo o no se pueden alcanzar
	if a == b:
		min_dist[a][b] = 0
	elif min_dist[a][b] == BIG:
		min_dist[a][b] = -1
 
	print(min_dist[a][b])

Problemas

Este algoritmo se usa como primer paso de lo siguiente:

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	Gold	Moortal Cowmbat	Difícil	APSP, DP	Solución

Dijkstra

Tutorial

$\mathcal{O}(N^2)$

Recursos
Fuente	Recurso	Notas
cp-algo	Dijkstra (Dense Graphs)

$\mathcal{O}(M\log N)$

Recursos
Fuente	Recurso	Notas
CPH	13.2 - Dijkstra	código
cp-algo	Dijkstra (Sparse Graphs)
CPC	8 - Shortest Paths
CP2	4.4.3 - SSSP on Weighted Graph
alexyd88	Dijkstra Visualizer

Implementación $\mathcal{O}(M\log N)$

Recursos
Fuente	Recurso	Notas
Benq	Dijkstra

Problema

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	CSES	Shortest Routes I	Fácil	SP	en el módulo

Implementación

Complejidad temporal: $\mathcal{O}(N + M\log N)$

Aquí hay una animación de cómo funciona el algoritmo:

C++JavaPython

Recordemos del segundo módulo prerrequisito que podemos usar greater<> para hacer que el elemento del tope de una cola de prioridad sea el menor en lugar del mayor. Como alternativa, se pueden negar las distancias antes de ponerlas en la cola de prioridad.


#include <bits/stdc++.h>
using namespace std;
 
int main() {
	int n, m;
	cin >> n >> m;
 
	// Lista de adyacencia de (vecino, peso de arista)
	vector<vector<pair<int, int>>> neighbors(n);
	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		neighbors[a - 1].push_back({b - 1, c});
	}
 
	// Inicialmente fijamos todas las distancias en infinito
	vector<long long> dist(n, LLONG_MAX);
 
	// Algoritmo de Dijkstra
	using T = pair<long long, int>;
	priority_queue<T, vector<T>, greater<T>> pq;
 
	int start = 0;
	dist[start] = 0;  // El camino más corto de un nodo a sí mismo es 0
	pq.push({0, start});
 
	while (!pq.empty()) {
		const auto [cdist, node] = pq.top();
		pq.pop();
		if (cdist != dist[node]) { continue; }
		for (const pair<int, int> &i : neighbors[node]) {
			// Si podemos alcanzar un nodo vecino más rápido,
			// actualizamos su distancia mínima
			if (cdist + i.second < dist[i.first]) {
				pq.push({dist[i.first] = cdist + i.second, i.first});
			}
		}
	}
 
	for (int i = 0; i < n - 1; i++) { cout << dist[i] << ' '; }
	cout << dist[n - 1] << endl;
}


import java.io.*;
import java.util.*;
 
public class ShortestRoutesI {
	// BeginCodeSnip{Pair Class}
	static class Pair<K, V> {
		public K a;
		public V b;
 
		public Pair(K a, V b) {
			this.a = a;
			this.b = b;
		}
	}
	// EndCodeSnip
 
	public static void main(String[] args) {
		Kattio io = new Kattio();
 
		int n = io.nextInt();
		int m = io.nextInt();
 
		// Lista de adyacencia de (vecino, peso de arista)
		List<Pair<Integer, Integer>>[] neighbors = new ArrayList[n];
		for (int i = 0; i < n; i++) { neighbors[i] = new ArrayList<>(); }
		for (int i = 0; i < m; i++) {
			int a = io.nextInt() - 1;
			int b = io.nextInt() - 1;
			int c = io.nextInt();
			neighbors[a].add(new Pair<>(b, c));
		}
 
		// Inicialmente fijamos todas las distancias en infinito
		long[] dist = new long[n];
		Arrays.fill(dist, Long.MAX_VALUE);
 
		// Algoritmo de Dijkstra
		PriorityQueue<Pair<Long, Integer>> pq =
		    new PriorityQueue<>(Comparator.comparingLong(i -> i.a));
 
		int start = 0;
		dist[start] = 0;  // El camino más corto de un nodo a sí mismo es 0
		pq.add(new Pair<>(0L, start));
		while (!pq.isEmpty()) {
			Pair<Long, Integer> curr = pq.poll();
			long cdist = curr.a;
			int node = curr.b;
			if (cdist != dist[node]) { continue; }
			for (Pair<Integer, Integer> i : neighbors[node]) {
				// Si podemos alcanzar un nodo vecino más rápido,
				// actualizamos su distancia mínima
				if (cdist + i.b < dist[i.a]) {
					pq.add(new Pair<>(dist[i.a] = cdist + i.b, i.a));
				}
			}
		}
 
		for (int i = 0; i < n - 1; i++) { io.print(dist[i] + " "); }
		io.println(dist[n - 1]);
		io.close();
	}
 
	// CodeSnip{Kattio}
}


import heapq
 
n, m = map(int, input().split())
 
# Lista de adyacencia de (vecino, peso de arista)
graph = [[] for _ in range(n)]
for i in range(m):
	a, b, c = map(int, input().split())
	graph[a - 1].append((b - 1, c))
 
# Inicialmente fijamos todas las distancias en infinito
dist = [float("inf") for _ in range(n)]
 
# Algoritmo de Dijkstra
pq = []
 
start = 0
heapq.heappush(pq, (0, start))
dist[start] = 0  # El camino más corto de un nodo a sí mismo es 0
while pq:
	cdist, node = heapq.heappop(pq)
	if cdist != dist[node]:
		continue
	for i in graph[node]:
		# Si podemos alcanzar un nodo vecino más rápido,
		# actualizamos su distancia mínima
		if cdist + i[1] < dist[i[0]]:
			dist[i[0]] = cdist + i[1]
			heapq.heappush(pq, (dist[i[0]], i[0]))
 
for i in range(n):
	print(dist[i], end=" ")

Es importante incluir continue. Esto asegura que, cuando todos los pesos de arista son no negativos, nunca recorramos la lista de adyacencia de ningún vértice más de una vez. ¡Sacarlo causa TLE en el último caso de prueba del problema de arriba!

El último caso de prueba contiene 100000 destinos y 149997 vuelos. La ciudad 1 tiene vuelos a las ciudades 2 a 50000. Las ciudades 2 a 50000 tienen vuelos a la ciudad 50001. La ciudad 50001 tiene vuelos a las ciudades 50002 a 100000. Sin el continue, después de que el programa saque de la cola las ciudades 1 a 50000, la cola de prioridad contendrá 49999 rutas que terminan en la ciudad 50001. Cada una de las 49999 veces que se saca y procesa la ciudad 50001, hay que iterar sobre todos sus vuelos salientes (hacia las ciudades 50002 a 100000). Esto da un tiempo de ejecución de $\Theta(N^2\log N)$ , que causa TLE.

En cambio, si incluimos el continue, el programa nunca iterará por la lista de adyacencia de la ciudad 50001 después de procesarla por primera vez.

Dijkstra más rápido

Se puede hacer en $\mathcal{O}(M+N\log N)$ con heap de Fibonacci . En la práctica, sin embargo, rara vez es más rápido, porque el heap de Fibonacci tiene un mal factor constante.

Problemas

Fuente	Nombre	Dificultad	Tags	Solución
CSES	Flight Discount	Fácil	SP	Solución
Gold	Milk Pumping	Fácil	SP	Solución
Gold	Why Did the Cow Cross the Road	Fácil	SP	Solución
Gold	Fine Dining	Fácil	SP	Solución
Gold	Shortcut	Normal	SP	Solución
Gold	Telephone	Normal	SP	—
CF	Not Escaping	Normal	SP, Coordinate Compression, Binary Search, DP	Solución
CSES	★ Investigation	Normal	SP	Solución
Kattis	Robot Turtles	Normal	SP	Solución
CSES	Flight Routes	Normal	SP	Solución
AC	Remainder Game	Difícil	SP, Greedy	Solución
IOI	2011 - Crocodile	Difícil	SP	Solución
JOI	★ 2018 - Commuter Pass	Difícil	SP, DP	Solución
JOI	★ 2021 - Robot	Difícil	SP	Solución
APIO	Find the Path	Difícil	SP, Geometry	Solución
Balkan OI	★ 2012 - Shortest Paths	Difícil	SP	Solución
Balkan OI	2015 - Circus	Muy difícil	SP, Stack	Solución

Caminos más cortos con pesos de arista no negativos

Bellman-Ford

Floyd-Warshall

Tutorial

Problema

Explicación

Implementación

Problemas

Dijkstra

Tutorial

O(N2)\mathcal{O}(N^2)O(N2)

O(Mlog⁡N)\mathcal{O}(M\log N)O(MlogN)

Implementación O(Mlog⁡N)\mathcal{O}(M\log N)O(MlogN)

Problema

Implementación

Problemas

$\mathcal{O}(N^2)$

$\mathcal{O}(M\log N)$

Implementación $\mathcal{O}(M\log N)$