Algoritmos de Camino Más Corto en Grafos

Introducción

En competencias de programación y algorítmica, con frecuencia nos encontramos con problemas que requieren encontrar el camino más corto en grafos. Aunque inicialmente podríamos considerar usar DFS o BFS, estos algoritmos tienen limitaciones significativas: DFS tiene una complejidad temporal demasiado alta para grafos grandes, mientras que BFS solo es aplicable bajo condiciones específicas. Por ello, es necesario desarrollar algoritmos especializados para resolver eficientemente estos problemas.

Es importante destacar que los algoritmos de camino más corto no solo sirven para encontrar rutas óptimas, sino que también pueden aplicarse para resolver sistemas de desigualdades, conocidos como restricciones de diferencia.

Nota importante: Antes de estudiar este material, asegúrate de tener conocimientos básicos en teoría de grafos.

Caminos más cortos desde un origen único

Cuando necesitamos encontrar la distancia más corta desde un nodo específico a todos los demás nodos del grafo, estamos resolviendo un problema de camino más corto desde un origen único. Para este tipo de problemas, generalmente utilizamos dos algoritmos principales: Dijkstra y SPFA. Ambos algoritmos pueden resolver el problema de manera eficiente, pero tienen características y condiciones de aplicación distintas.

Algoritmo de Dijkstra

Para comprender mejor el algoritmo, consideremos un ejemplo práctico.

Ejemplo 1 - Camino más corto

Descripción del problemaDado un grafo dirigido con ponderación que contiene n nodos y m aristas, encontrar la longitud del camino más corto desde el nodo 1 hasta el nodo n.

Formato de entradaLa primera línea contiene dos enteros positivos n, m (1 ≤ n,m ≤ 2×10^5) Las siguientes m líneas contienen tres enteros u,v,w (1 ≤ u,v ≤ n, w ≤ 1000) que representan una arista dirigida desde u hasta v con peso w.

Formato de salidaUn entero que representa la longitud del camino más corto. Si no existe solución, imprimir "No solution".

Entrada de ejemplo

5 10
3 2 8
5 4 7
1 4 8
2 5 3
3 4 8
3 5 2
4 3 6
4 1 1
5 3 6
5 1 9

Salida de ejemplo

16
Análisis

¿Cómo abordaríamos este problema? Intentar una solución con DFS sería ineficiente debido a su alta complejidad temporal. Por lo tanto, debemos utilizar el algoritmo de Dijkstra.

Proceso del algoritmo de Dijkstra

Dividimos todos los nodos en dos conjuntos: aquellos para los cuales ya hemos encontrado la distancia mínima (denotado como V) y aquellos para los cuales aún no hemos determinado la distancia mínima (denotado como E). Además, mantenemos un array de distancias llamado "dist".

Inicializamos el array "dist" con valores infinitos positivos. La distancia del nodo de inicio (st) se establece en 0. Desde el conjunto E, seleccionamos el nodo más cercano al origen (denotado como u), lo movemos al conjunto V y recorremos todos los nodos adyacentes a u (denotados como v). Actualizamos la distancia de v basándonos en la distancia de u (esta operación se conoce como "relajación"). Los nodos actualizados se agregan al conjunto E. Repetimos este proceso hasta que E esté vacío. En este punto, la distancia al nodo n será nuestra respuesta.

Para hacerlo más concreto, consideremos un ejemplo:

Sea "matriz[x][y]" la longitud del camino de x a y. Inicializamos todas las distancias como infinitas positivas. La distancia del nodo 1 es 0.

Comenzamos desde el nodo 1, lo agregamos al conjunto V. Los nodos adyacentes son 2, 3, 5. ∵ dist[2] > dist[1] + matriz[1][2] ∴ dist[2] = dist[1] + matriz[1][2] = 3 De manera similar, dist[3] = dist[1] + matriz[1][3] = 3, dist[5] = dist[1] + matriz[1][5] = 6 Agregamos estos nodos al conjunto E. E = {2,3,5}

Seleccionamos el nodo 2 del conjunto E, lo movemos a V. Desde 2, podemos llegar a 4 y 5. ∵ dist[4] > dist[2] + matriz[2][4] ∴ dist[4] = dist[2] + matriz[2][4] = 5 ∵ dist[5] < dist[2] + matriz[2][5] ∴ dist[5] = dist[5] Agregamos estos nodos a E, reemplazando el nodo 5 existente. E = {3,4,5}

Seleccionamos el nodo 3, lo movemos a V. No hay nodos adyacentes nuevos, por lo que lo omitimos. E = {4,5}

Seleccionamos el nodo 4, lo movemos a V. Desde 4 podemos llegar a 5 y 6. dist[5] = min(dist[5], dist[4] + matriz[4][5]) = 6 dist[6] = min(dist[6], dist[4] + matriz[4][6]) = 6 Reemplazamos 5 y agregamos 6 a E. E = {5,6}

Seleccionamos el nodo 5, lo movemos a V. Desde 5 podemos llegar a 3 y 6, pero 3 ya está en V. dist[6] = min(dist[6], dist[5] + matriz[5][6]) = 6 Reemplazamos 6. E = {6}

Seleccionamos el nodo 6, lo movemos a V. No hay nodos adyacentes nuevos. E está vacío, terminamos el algoritmo. La respuesta es dist[6].

Ahora deberías entender el proceso. Si no está claro, intenta simularlo manualmente.

Complejidad temporal y código del algoritmo de Dijkstra

Sin optimizaciones, la complejidad temporal es O(n²), ya que cada iteración requiere O(n) tiempo para encontrar el mínimo en E, y tenemos n iteraciones.

Código de ejemplo

const int INF=1e4+10;
struct Nodo{
  int v, peso;
};
vector<Nodo> grafo[INF];
int distancia[INF],visitado[INF];
int n;
void dijkstra(int inicio){
	memset(distancia,0x3f,sizeof(distancia));
	distancia[inicio]=0;
	for (int i=1;i<=n;i++){
		int u=0,minimo=INT_MAX;
		for (int j=1;j<=n;j++){
			if (!visitado[j] && distancia[j]<minimo)u=j,minimo=distancia[j];
		}
		visitado[u]=1;
		int tamano=grafo[u].size();
		for (int i=0;i<tamano;i++){
			int v=grafo[u][i].v,w=grafo[u][i].peso;
			if (distancia[v]>distancia[u]+w)distancia[v]=distancia[u]+w;
		}
	}
}

Para optimizar, podemos usar una cola de prioridad. La complejidad temporal se reduce a O((n+m) log n), pero en grafos densos (m ≈ n²) puede ser peor que la versión sin optimizar.

#include<bits/stdc++.h>
using namespace std;
const long long INF=2e5+10,MAXN=1e18;
struct Nodo{
	long long nodo,dist;
	bool operator <(const Nodo &b)const{
		return dist>b.dist;
	}
};
priority_queue<Nodo> cola;
long long n,m,inicio,distancia[INF],visitado[INF];
vector<Nodo> grafo[INF];

void dijkstra(int x){
	distancia[x]=0,cola.push({x,0});
	while (!cola.empty()){
		int u=cola.top().nodo;
		cola.pop();
		if (visitado[u]!=0)continue;
		visitado[u]=1;
		int tamano=grafo[u].size();
		for (int i=0;i<tamano;i++){
			long long v=grafo[u][i].nodo,w=grafo[u][i].dist;
			if (distancia[v]>distancia[u]+w){
				distancia[v]=distancia[u]+w;
				cola.push({v,distancia[v]});
			}
		}
	}
}

void limpiar(){
	for (int i=0;i<=n;i++)grafo[i].clear();
	for (int i=0;i<=n;i++)distancia[i]=MAXN;
	for (int i=0;i<=n;i++)visitado[i]=0;
}
int main(){
	int T;
	cin>>T;
	while (T--){
		cin>>n>>m>>inicio;
		limpiar();
		for (int i=1;i<=m;i++){
			int u,v,w;
			cin>>u>>v>>w;
			grafo[u].push_back({v,w});
		}
		dijkstra(inicio);
		for (int i=1;i<=n;i++){
			if (distancia[i]>=MAXN)cout<<2147383647<<" ";
			else cout<<distancia[i]<<" ";
		}	
		cout<<endl;
	}
	return 0;
}

Conteo de caminos más cortos con Dijkstra

Si además de encontrar la longitud del camino más corto, necesitamos contar cuántos caminos mínimos existen entre nodos, podemos modificar el algoritmo. La clave está en la operación de relajación.

Cuando relajamos una arista (u,v), hay tres casos posibles:

  1. La nueva distancia es menor que la distancia actual: actualizamos la distancia y el contador de caminos.
  2. La nueva distancia es igual a la distancia actual: incrementamos el contador de camminos.
  3. La nueva distancia es mayor: no hacemos nada.
#include<bits/stdc++.h>
using namespace std;

struct Nodo{
	int nodo,dist;
	bool operator <(const Nodo &a)const{
		return dist>a.dist;
	}
};
const int INF=1e5+10;
vector<int> grafo[INF];
priority_queue<Nodo> cola;
int distancia[INF],caminos[INF],visitado[INF];

void dijkstra(int x){
	distancia[x]=0,caminos[x]=1,cola.push({x,distancia[x]});
	while (!cola.empty()){
		int u=cola.top().nodo;cola.pop();
		if (visitado[u])continue;
		visitado[u]=1;
		int tamano=grafo[u].size();
		for (int i=0;i<tamano;i++){
			int v=grafo[u][i];
			if (distancia[v]>distancia[u]+1){// Caso 1
				distancia[v]=distancia[u]+1;
				caminos[v]=caminos[u];
				cola.push({v,distancia[v]});
			}else if (distancia[v]==distancia[u]+1){// Caso 2
				caminos[v]+=caminos[u];
				caminos[v]%=100003;
			}
		}
	}
}

int n,m;
void limpiar(){
	for (int i=0;i<=n;i++){
		distancia[i]=1e8;
	}
}
int main(){
	cin>>n>>m;
	limpiar();
	for (int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		grafo[u].push_back(v);
		grafo[v].push_back(u); 
	}
	dijkstra(1);
	for (int i=1;i<=n;i++){
		cout<<caminos[i]<<endl;
	}
	return 0;
}

El algoritmo de Dijkstra tiene una limitación importante: no funciona con grafos que contengan aristas con pesos negativos. En estos casos, debemos utilizar otro algoritmo: SPFA.

Algoritmo SPFA

SPFA es una optimización del algoritmo Bellman-Ford. Aunque originalmente se pensaba que tenía una complejidad cercana a O(n), en realidad puede alcanzar O(nm) en ciertas estructuras de grafo como los grafos de margarita.

Proceso del algoritmo SPFA

Al igual que Dijkstra, realizamos operaciones de relajación, pero sin la restricción de pesos no negativos. La idea básica es:

  1. Inicializar todas las distancias como infinitas, excepto el nodo de inicio que es 0.
  2. Colocar el nodo de inicio en una cola.
  3. Mientras la cola no esté vacía, sacar un nodo u y relajar todas sus aristas salientes.
  4. Si la distancia a un nodo vecino v se actualiza, y v no está en la cola, agregarlo a la cola.

Complejidad temporal y código de SPFA

En grafos dispersos, la complejidad es O(km) donde k es una pequeña constante (generalmente k<2). En grafos densos puede ser O(nm).

#include<bits/stdc++.h>
using namespace std;
const long long INF=5e3+10,MAXN=1e18;

struct Nodo{
	int nodo,peso;
};
long long distancia[INF],cuenta[INF];
int n,m,origen,destino,visitado[INF];
vector<Nodo> grafo[INF];
void spfa(int x){
	queue<int> cola;
	distancia[x]=0,cola.push(x),visitado[x]=1;
	while (!cola.empty()){
		int u=cola.front();cola.pop();
		visitado[u]=0;
		int tamano=grafo[u].size();
		for (int i=0;i<tamano;i++){
			long long v=grafo[u][i].nodo,w=grafo[u][i].peso;
			if (distancia[v]>distancia[u]+w){
				distancia[v]=distancia[u]+w;
				if (!visitado[v]){
					cola.push(v);visitado[v]=1;
				}
			}
		}
	}
}

void limpiar(){
	for (int i=0;i<=n;i++)distancia[i]=MAXN;
}
int main(){
	ios::sync_with_stdio();
	cin.tie(0),cout.tie(0);
	cin>>n>>m>>origen>>destino;
	limpiar();
	for (int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		grafo[u].push_back({v,w});
	} 
	spfa(origen);
	cout<<distancia[destino];
	return 0;
}

Detección de ciclos negativos con SPFA

Si un nodo es relajado n veces (donde n es el número de nodos), indica la presencia de un ciclo negativo en el grafo.

#include<bits/stdc++.h>
using namespace std;
const long long INF=5e3+10,MAXN=1e18;

struct Nodo{
	int nodo,peso;
};
long long distancia[INF],cuenta[INF];
int n,m,origen,destino,visitado[INF];
vector<Nodo> grafo[INF];
void spfa(int x){
	queue<int> cola;
	distancia[x]=0,cola.push(x),visitado[x]=1;
	while (!cola.empty()){
		int u=cola.front();cola.pop();
		visitado[u]=0;
		int tamano=grafo[u].size();
		for (int i=0;i<tamano;i++){
			long long v=grafo[u][i].nodo,w=grafo[u][i].peso;
			if (distancia[v]>distancia[u]+w){
				distancia[v]=distancia[u]+w;
				if (!visitado[v]){
					if (++cuenta[v]>=n){// Si hay ciclo negativo
						cout<<"YES"<<endl;
						exit(0);
					}
					cola.push(v);
					visitado[v]=1;
				}
			}
		}
	}
	cout<<"NO"<<endl;
	return;
}
void limpiar(){
	for (int i=0;i<=n;i++)distancia[i]=MAXN; 
	for (int i=0;i<=n;i++)cuenta[i]=0;
	for (int i=0;i<=n;i++)grafo[i].clear();
}
int main(){
	ios::sync_with_stdio();
	cin.tie(),cout.tie();
	int T;
	cin>>T;
	while (T--){
		cin>>n>>m;
		limpiar();
		for (int i=1;i<=m;i++){
			int u,v,w;
			cin>>u>>v,w;
			grafo[u].push_back({v,w});
			if (w>=0)grafo[v].push_back({u,w});
		}
		spfa(1);
	}
	return 0;
}

Ejemplos de caminos más cortos desde un origen único

P2951 [USACO09OPEN] Hide and Seek S

DescripciónBessie está jugando al escondite (un juego en el que varios jugadores se esconden y un jugador (el buscador) intenta encontrarlos). Ella debe decidir en cuál de N granjas debe esconderse. FJ (el buscador) comienza en la granja 1. Todas las granjas están conectadas por M caminos bidireccionales. Bessie decidirá esconderse en la granja que tenga la mayor distancia de la granja 1.

Formato de entradaPrimera línea: dos enteros N y M Siguientes líneas: M líneas con dos enteros A_i y B_i que indican un camino entre las granjas A_i y B_i

Formato de salidaUna línea con tres enteros: el índice de la granja más lejana, la distancia mínima a esa granja, y el número de granjas a esa distancia.

AnálisisEste problema es sencillo: calculamos las distancias desde el nodo 1 y encontramos el nodo con mayor distancia.

#include<bits/stdc++.h>
using namespace std;
const int INF=2e4+10;
int cnt,maxn=INT_MIN,ans=INT_MAX;
struct Nodo{
	int nodo,dist;
	bool operator <(const Nodo &a)const{
		return dist>a.dist;
	}
};

int distancia[INF],visitado[INF];
int n,m;
vector<int> grafo[INF];
priority_queue<Nodo> cola;
void dijkstra(int x){
	distancia[x]=0;cola.push({x,0});
	while (!cola.empty()){
		int u=cola.top().nodo;cola.pop();
		if (visitado[u]==1)continue;
		visitado[u]=1;
		int tamano=grafo[u].size();
		for (int i=0;i<tamano;i++){
			int v=grafo[u][i];
			if (distancia[v]>distancia[u]+1){
				distancia[v]=distancia[u]+1;
				if (maxn<distancia[v])maxn=distancia[v],cnt=1,ans=v;
				else if (maxn==distancia[v])cnt++,ans=min(ans,v);
				cola.push({v,distancia[v]});
			}
		}
	}
}
void limpiar(){
	for (int i=0;i<=n;i++)distancia[i]=INT_MAX;
}
int main(){
	cin>>n>>m;
	limpiar();
	for (int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		grafo[u].push_back(v);
		grafo[v].push_back(u);
	} 
	dijkstra(1);
	cout<<ans<<" "<<maxn<<" "<<cnt;
	return 0;
}
P1576 Gasto mínimo

DescripciónEntre n personas, algunas cuentas bancarias pueden transferirse entre sí. Cada transferencia tiene una comisión diferente. Dadas las comisiones porcentuales para transferir entre personas, ¿cuánto dinero necesita A como mínimo para que B reciba 100 yuanes después de las transferencias?

AnálisisPodemos resolver el problema inversamente: comenzamos con B recibiendo 100 yuanes y calculamos cuánto necesita A para lograr esto.

#include<bits/stdc++.h>
using namespace std;
const int INF=2e5+10,MAXN=1e8;
struct Nodo{
	int nodo;
	double dist;
	bool operator <(const Nodo &a)const{
		return dist>a.dist;
	}
};

vector<Nodo> grafo[INF];
double distancia[INF];
int n,m,visitado[INF];

priority_queue<Nodo> cola;
void dijkstra(int x){
	distancia[x]=100.0,cola.push({x,0});
	while (!cola.empty()){
		int u=cola.top().nodo;cola.pop();
		if (visitado[u]==1)continue;
		visitado[u]=1;
		int tamano=grafo[u].size();
		for (int i=0;i<tamano;i++){
			int v=grafo[u][i].nodo,w=grafo[u][i].dist;
			if (distancia[v]>distancia[u]/(1.0-(w*0.01))){
				distancia[v]=distancia[u]/(1.0-(w*0.01));
				cola.push({v,distancia[v]});
			}
		}
	}
}

void limpiar(){
	for (int i=0;i<=n;i++)distancia[i]=MAXN;
}
int main(){
	cin>>n>>m;
	limpiar();
	for (int i=1;i<=m;i++){
		int x,y;double z;
		cin>>x>>y>>z;
		grafo[x].push_back({y,z});
		grafo[y].push_back({x,z});
	}
	int inicio,fin;
	cin>>inicio>>fin;
	dijkstra(fin);
	printf("%.8lf",distancia[inicio]);
	return 0;
}
P3385 【Plantilla】 Ciclo negativo

DescripciónDado un grafo dirigido con n nodos, determinar si existe un ciclo negativo alcanzable desde el nodo 1.

AnálisisEste es un problema directo de detección de ciclos negativos usando SPFA.

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e8,INF=1e5;

struct Nodo{
	int nodo,peso;
};

int n,m;
int cuenta[INF],distancia[INF],visitado[INF];
vector<Nodo> grafo[INF];

void spfa(int x){
	queue<int> cola;
	distancia[x]=0,cola.push(x),visitado[x]=1;
	while (!cola.empty()){
		int u=cola.front();cola.pop();
		visitado[u]=0;
		int tamano=grafo[u].size();
		for (int i=0;i<tamano;i++){
			int v=grafo[u][i].nodo,w=grafo[u][i].peso;
			if (distancia[v]>distancia[u]+w){
				distancia[v]=distancia[u]+w;
				if (!visitado[v]){
					if (++cuenta[v]>=n){
						cout<<"YES"<<endl;
						return;
					}
					cola.push(v);
					visitado[v]=1;
				}
			}
		}
	}
	cout<<"NO"<<endl;
	return;
}
void limpiar(){
	for (int i=0;i<=n;i++)visitado[i]=0;
	for (int i=0;i<=n;i++)distancia[i]=MAXN; 
	for (int i=0;i<=n;i++)cuenta[i]=0;
	for (int i=0;i<=n;i++)grafo[i].clear();
}
int main(){
	ios::sync_with_stdio();
	cin.tie(),cout.tie();
	int T;
	cin>>T;
	while (T--){
		cin>>n>>m;
		limpiar();
		for (int i=1;i<=m;i++){
			int u,v,w;
			cin>>u>>v>>w;
			grafo[u].push_back({v,w});
			if (w>=0)grafo[v].push_back({u,w});
		}
		spfa(1);
	}
	return 0;
}

Caminos más cortos entre todos los pares de nodos

Cuando necesitamos encontrar el camino más corto entre todos los pares de nodos, estamos resolviendo un problema de camino más corto entre todos los pares. Para este tipo de problemas, principalmente utilizamos dos algoritmos: Floyd y Johnson.

Algoritmo Floyd

El algoritmo de Floyd calcula los caminos más cortos entre todos los pares de nodos en un grafo. A diferencia de Dijkstra, puede manejar grafos con pesos negativos (pero no ciclos negativos).

Proceso del algoritmo Floyd

El algoritmo utiliza programación dinámica. La idea es considerar cada nodo como punto intermedio potencial en el camino entre otros dos nodos.

Definimos dp[k][i][j] como la longitud del camino más corto de i a j usando solo nodos con índice ≤ k como puntos intermedios.

La ecuación de transición es: dp[k][i][j] = min(dp[k-1][i][j], dp[k-1][i][k] + dp[k-1][k][j])

Podemos optimizar el espacio al notar que solo necesitamos la iteración anterior, por lo que podemos reducir a una matriz 2D.

Complejidad temporal y código de Floyd

La complejidad temporal es O(n³) debido a los tres bucles anidados.

for (int k=1;k<=n;k++){
	for (int i=1;i<=n;i++){
		for (int j=1;j<=n;j++){
			distancia[i][j]=min(distancia[i][j],distancia[i][k]+distancia[k][j]);
		}
	}
}

Encontrando el ciclo mínimo con Floyd

Si necesitamos encontrar el ciclo más pequeño en un grafo, podemos modificar el algoritmo de Floyd. Durante la ejecución, calculamos: min(ciclo[i][j] + arista[j][k] + arista[k][i]) para 1 ≤ i < j < k

Este valor representa la longitud del ciclo mínimo que incluye el nodo k.

#include<bits/stdc++.h>
using namespace std;
const long long INF=1e13;
long long matriz[310][310],distancia[310][310];
long long n,m,ans=INF;
int main(){
	cin>>n>>m;
	memset(distancia,0x3f3f,sizeof(distancia));
	memset(matriz,0x3f3f,sizeof(matriz));
	for (int i=0;i<=n+5;i++){
		matriz[i][i]=0;
		distancia[i][i]=0;
	}
	for (int i=1;i<=m;i++){
		long long x,y,z;
		cin>>x>>y>>z;
		matriz[x][y]=matriz[y][x]=min(matriz[x][y],z);
		distancia[x][y]=distancia[y][x]=matriz[x][y];
	}
	for (int k=1;k<=n;k++){
		// Calcular ciclo mínimo
		for (int i=1;i<k;i++){
			for (int j=i+1;j<k;j++){
				ans=min(distancia[i][j]+matriz[i][k]+matriz[k][j],ans);
			}
		}
		// Calcular Floyd
		for (int i=1;i<=n;i++){
			for (int j=1;j<=n;j++){
				distancia[i][j]=min(distancia[i][j],distancia[i][k]+distancia[k][j]);
			}
		}
	}
	if (ans==INF)cout<<"No solution.";
	else cout<<ans;
	return 0;
}

Algoritmo Johnson

El algoritmo Johnson es eficiente para grafos dispersos con pesos negativos. Combina el algoritmo de Bellman-Ford con Dijkstra.

Proceso del algoritmo Johnson

  1. Agregar un nodo virtual con aristas de peso 0 a todos los demás nodos.
  2. Usar Bellman-Ford (o SPFA) para calcular las distancias mínimas desde el nodo virtual.
  3. Re-pesar las aristas usando: nuevo_peso = antiguo_peso + h[u] - h[v]
  4. Ejecutar Dijkstra desde cada nodo en el grafo re-pesado.
  5. Convertir las distancias de vuelta a las originales: distancia_original = distancia_repesada - h[u] + h[v]

Complejidad temporal y código de Johnson

La complejidad es O(nm log n), eficiente para grafos dispersos pero no para grafos densos.

#include<bits/stdc++.h>
using namespace std;
const long long INF=3e3+10,MAXN=1e9;
struct Nodo{
	long long nodo,peso;
	bool operator <(const Nodo &a)const{
		return peso>a.peso;
	}
};
vector<Nodo> grafo[INF];
long long h[INF],cuenta[INF],visitado[INF],distancia[INF];
int n,m;

void limpiar(long long t[],long long p){
	for (int i=0;i<=n;i++)t[i]=p;
}
bool spfa(int x){
	limpiar(h,MAXN);
	queue<long long> cola;
	h[x]=0,cuenta[x]=1,cola.push(x);
	while (!cola.empty()){
		long long u=cola.front();cola.pop();
		visitado[u]=0;
		int tamano=grafo[u].size();
		for (int i=0;i<tamano;i++){
			long long v=grafo[u][i].nodo,w=grafo[u][i].peso;
			if (h[v]>h[u]+w){
				h[v]=h[u]+w;
				if (!visitado[v]){
					if (++cuenta[v]>n)return false;
					cola.push(v);
					visitado[v]=1;
				}
			}
		}
	}
	return true;
}

void dijkstra(int x){
	priority_queue<Nodo> cola;
	distancia[x]=0;cola.push({x,0});
	while (!cola.empty()){
		long long u=cola.top().nodo;cola.pop();
		if (visitado[u])continue;
		visitado[u]=1;
		int tamano=grafo[u].size();
		for (int i=0;i<tamano;i++){
			long long v=grafo[u][i].nodo,w=grafo[u][i].peso;
			if (distancia[v]>distancia[u]+w){
				distancia[v]=distancia[u]+w;
				cola.push({v,distancia[v]});
			} 
		}
	}
}
int main(){
	cin>>n>>m;
	for (int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		grafo[u].push_back({nodo,v,peso});// Construir grafo normal 
	}
	for (int i=1;i<=n;i++){// Agregar nodo virtual
		grafo[0].push_back({nodo,i,peso:0});
	}
	if (!spfa(0)){// Si hay ciclo negativo
		cout<<-1;
		return 0;
	}
	for (int i=1;i<=n;i++){
		int tamano=grafo[i].size();
		for (int j=0;j<tamano;j++)grafo[i][j].peso+=h[i]-h[grafo[i][j].nodo];// Re-pesar
	}
	for (int i=1;i<=n;i++){
		limpiar(visitado,0);
		limpiar(distancia,MAXN);
		dijkstra(i);
		for (int j=1;j<=n;j++){
			if (distancia[j]>=MAXN)cout<<"No hay camino";
			else cout<<distancia[j]+h[j]-h[i];
		}
	} 
	return 0;
}

Ejemplos de caminos más cortos entre todos los pares

P1690 Copy codicioso

DescripciónCopy debe recoger todos los tesoros en un área con n regiones y salir por la región n. Encontrar la ruta más corta desde la región 1 que recoja todos los tesoros y termine en la región n.

AnálisisPrimero usamos Floyd para precomputar todas las distancias mínimas, luego usamos DFS para encontrar la ruta óptima que recoja todos los tesoros.

#include<bits/stdc++.h>
using namespace std;
const long long INF=1e18;
long long distancia[110][110],tesoro[20];
int visitado[110],n,p;
long long ans=INT_MAX;
void dfs(int x,int num,long long total){
	if (num==p+1){
		ans=min(ans,total+distancia[x][n]);
		return;
	}
	for (int i=1;i<=p;i++){
		if (visitado[i]==0){
			visitado[i]=1;
			dfs(tesoro[i],num+1,total+distancia[x][tesoro[i]]);
			visitado[i]=0;
		}
	}
	return;
}
int main(){
	for (int i=0;i<=100;i++){
		for (int j=0;j<=100;j++){
			if (i!=j)distancia[i][j]=INF;
		}
	}
	cin>>n;
	for (int i=1;i<=n;i++){
		for (int j=1;j<=n;j++){
			cin>>distancia[i][j];
		}
	}
	cin>>p;
	for (int i=1;i<=p;i++){
		cin>>tesoro[i];
	}
	for (int k=1;k<=n;k++){
		for (int i=1;i<=n;i++){
			for (int j=1;j<=n;j++){
				distancia[i][j]=min(distancia[i][j],distancia[i][k]+distancia[k][j]);
			}
		}
	}
	dfs(1,1,0);
	cout<<ans;
	return 0;
}
P10927 Sightseeing trip

DescripciónEncontrar el ciclo simple (sin nodos repetidos) de longitud mínima en un grafo.

AnálisisEste es un problema directo de encontrar el ciclo mínimo usando Floyd.

P5905 【Plantilla】 Camino más corto entre todos los pares (Johnson)

DescripciónEncontrar todas las distancias más cortas entre pares de nodos en un grafo dirigido con pesos posibles negativos.

AnálisisEste problema requiere implementar el algoritmo Johnson completo.

#include<bits/stdc++.h>
using namespace std;
const long long INF=3e3+10,MAXN=1e9;
struct Nodo{
	long long nodo,peso;
	bool operator <(const Nodo &a)const{
		return peso>a.peso;
	}
};
vector<Nodo> grafo[INF];
long long h[INF],cuenta[INF],visitado[INF],distancia[INF];
int n,m;

void limpiar(long long t[],long long p){
	for (int i=0;i<=n;i++)t[i]=p;
}
bool spfa(int x){
	limpiar(h,MAXN);
	queue<long long> cola;
	h[x]=0,cuenta[x]=1,cola.push(x);
	while (!cola.empty()){
		long long u=cola.front();cola.pop();
		visitado[u]=0;
		int tamano=grafo[u].size();
		for (int i=0;i<tamano;i++){
			long long v=grafo[u][i].nodo,w=grafo[u][i].peso;
			if (h[v]>h[u]+w){
				h[v]=h[u]+w;
				if (!visitado[v]){
					if (++cuenta[v]>n)return false;
					cola.push(v);
					visitado[v]=1;
				}
			}
		}
	}
	return true;
}

void dijkstra(int x){
	priority_queue<Nodo> cola;
	distancia[x]=0;cola.push({x,0});
	while (!cola.empty()){
		long long u=cola.top().nodo;cola.pop();
		if (visitado[u])continue;
		visitado[u]=1;
		int tamano=grafo[u].size();
		for (int i=0;i<tamano;i++){
			long long v=grafo[u][i].nodo,w=grafo[u][i].peso;
			if (distancia[v]>distancia[u]+w){
				distancia[v]=distancia[u]+w;
				cola.push({v,distancia[v]});
			} 
		}
	}
}
int main(){
	cin>>n>>m;
	for (int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		grafo[u].push_back({nodo,v,peso});// Construir grafo normal 
	}
	for (int i=1;i<=n;i++){// Agregar nodo virtual
		grafo[0].push_back({nodo,i,peso:0});
	}
	if (!spfa(0)){// Si hay ciclo negativo
		cout<<-1;
		return 0;
	}
	for (int i=1;i<=n;i++){
		int tamano=grafo[i].size();
		for (int j=0;j<tamano;j++)grafo[i][j].peso+=h[i]-h[grafo[i][j].nodo];// Re-pesar
	}
	for (int i=1;i<=n;i++){
		limpiar(visitado,0);
		limpiar(distancia,MAXN);
		dijkstra(i);
		long long ans=0;
		for (int j=1;j<=n;j++){
			if (distancia[j]>=MAXN)ans+=j*MAXN;
			else ans+=j*(distancia[j]+h[j]-h[i]);
		} 
		cout<<ans<<endl;
	} 
	return 0;
}

Este artículo ha cubierto los algoritmos fundamentales para resolver problemas de camino más corto en grafos, incluyendo sus aplicaciones, implementaciones y análisis de complejidad.

Etiquetas: grafos algoritmos dijkstra floyd SPFA

Publicado el 7-2 21:31

Etiquetas populares

©2026 Friki Work