Data Structure & Algorithms
Caminos mínimos con BFS, Dijkstra, Bellman-Ford, Floyd-Warshall y relajación en DAGs según pesos y alcance de la consulta.
Un shortest path minimiza el costo de llegar desde un vértice hasta otro. El algoritmo correcto depende de la representación, de si buscas una fuente o todas las parejas y, sobre todo, de las propiedades de los pesos.
No existe un algoritmo único para todos los grafos.
En un grafo sin pesos, cada arista cuesta una unidad. La ruta más corta usa la menor cantidad de aristas.
En un grafo ponderado, el costo es la suma de los pesos:
A ─4→ B ─2→ D costo 6
A ─1→ C ─9→ D costo 10Un camino puede tener más aristas y aun así costar menos.
La operación central de muchos algoritmos es relajar una arista.
Para u → v con peso w:
si distance[u] + w < distance[v]
distance[v] = distance[u] + w
parent[v] = uLa relajación mejora una cota conocida. El orden y la cantidad de veces que se relajan las aristas determinan el algoritmo.
BFS visita vértices por cantidad creciente de aristas desde la fuente. La primera vez que descubre un vértice obtiene su distancia mínima.
function shortestUnweighted(
graph: Map<string, string[]>,
source: string,
): Map<string, number> {
const distance = new Map<string, number>([[source, 0]]);
const queue = [source];
let head = 0;
while (head < queue.length) {
const node = queue[head];
head += 1;
for (const neighbor of graph.get(node) ?? []) {
if (distance.has(neighbor)) continue;
distance.set(neighbor, distance.get(node)! + 1);
queue.push(neighbor);
}
}
return distance;
}Usar un índice head evita Array.shift(), cuyo desplazamiento puede ser lineal en JavaScript.
Tiempo: O(V + E) con adjacency list. Memoria: O(V) adicional, además del grafo.
Dijkstra resuelve shortest paths desde una fuente cuando todos los pesos son no negativos.
Modelo mental:
La garantía depende de que los pesos no sean negativos. Una arista negativa podría descubrir más tarde una ruta mejor hacia un vértice ya finalizado.
type WeightedEdge = {
to: number;
weight: number;
};
type HeapEntry = {
node: number;
distance: number;
};
function dijkstra(
graph: WeightedEdge[][],
source: number,
push: (entry: HeapEntry) => void,
pop: () => HeapEntry | undefined,
): number[] {
const distance = Array(graph.length).fill(Infinity);
distance[source] = 0;
push({ node: source, distance: 0 });
while (true) {
const current = pop();
if (!current) break;
if (current.distance !== distance[current.node]) continue;
for (const edge of graph[current.node]) {
const candidate = current.distance + edge.weight;
if (candidate < distance[edge.to]) {
distance[edge.to] = candidate;
push({ node: edge.to, distance: candidate });
}
}
}
return distance;
}El heap se inyecta para mantener el foco en el algoritmo. En una implementación real usarías una priority queue con comparador por distance.
Con adjacency list y binary heap:
O((V + E) log V), frecuentemente escrito O(E log V) en grafos conectados;O(V + E) según las entradas acumuladas en el heap.Esta versión permite entradas obsoletas en el heap y las ignora. Evita necesitar una operación decrease-key.
S ─2→ A
S ─5→ B
B ─-10→ ADijkstra puede finalizar A con costo 2 antes de procesar B, pero la ruta S → B → A cuesta -5.
No basta con que “casi todos” los pesos sean positivos.
Bellman-Ford admite pesos negativos y detecta ciclos negativos alcanzables desde la fuente.
Relaja todas las aristas V - 1 veces. Un camino simple contiene como máximo V - 1 aristas. Si todavía puede mejorar en una pasada adicional, existe un ciclo negativo alcanzable.
type DirectedEdge = {
from: number;
to: number;
weight: number;
};
function bellmanFord(
vertexCount: number,
edges: DirectedEdge[],
source: number,
): { distance: number[]; hasNegativeCycle: boolean } {
const distance = Array(vertexCount).fill(Infinity);
distance[source] = 0;
for (let pass = 1; pass < vertexCount; pass += 1) {
let changed = false;
for (const edge of edges) {
if (distance[edge.from] === Infinity) continue;
const candidate = distance[edge.from] + edge.weight;
if (candidate < distance[edge.to]) {
distance[edge.to] = candidate;
changed = true;
}
}
if (!changed) break;
}
const hasNegativeCycle = edges.some(
(edge) =>
distance[edge.from] !== Infinity &&
distance[edge.from] + edge.weight < distance[edge.to],
);
return { distance, hasNegativeCycle };
}Tiempo: O(VE). Memoria adicional: O(V).
Un ciclo negativo no hace indefinidas todas las distancias: solo afecta vértices alcanzables desde ese ciclo y desde la fuente relevante.
Calcula shortest paths entre todas las parejas mediante DP.
dist[i][j] = mejor costo de i a j usando intermediarios permitidosPara cada posible intermediario k:
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])O(V³);O(V²);Es útil para grafos relativamente pequeños o densos cuando se necesitan muchas consultas entre pares.
En un directed acyclic graph puedes ordenar topológicamente los vértices y relajar cada arista una vez. Admite pesos negativos porque no existen ciclos.
Tiempo: O(V + E).
| Algoritmo | Condición | Alcance | Tiempo típico |
|---|---|---|---|
| BFS | Sin pesos o peso uniforme | Una fuente | O(V + E) |
| Dijkstra | Pesos no negativos | Una fuente | O((V + E) log V) |
| Bellman-Ford | Pesos negativos permitidos | Una fuente | O(VE) |
| Floyd-Warshall | Muchas parejas, grafo pequeño | Todas las parejas | O(V³) |
| DAG relaxation | Grafo acíclico | Una fuente | O(V + E) |
Guarda parent[neighbor] = current al mejorar una distancia. Después recorre desde el destino hasta la fuente y revierte la secuencia.
Si solo guardas distancias, conoces el costo, no necesariamente el camino.
Infinity.Infinity sin validar en lenguajes donde puede overflow.La propiedad de los pesos decide el algoritmo. Antes de implementar, pregunta: ¿hay pesos?, ¿pueden ser negativos?, ¿hay ciclos negativos?, ¿una fuente o todas las parejas?, ¿grafo disperso o denso?
¿Por qué BFS puede finalizar una distancia al descubrir un vértice, mientras Dijkstra necesita una priority queue?
En BFS todas las aristas tienen el mismo costo, así que la cola procesa capas de distancia creciente. En un grafo ponderado, una ruta con más aristas puede costar menos; Dijkstra necesita elegir la menor distancia tentativa global.