Publicado · en mejora
Guía de Camino mínimo y árbol generador mínimo · 3/6
Por ahora, este capítulo solo está disponible en inglés.
This chapter builds Dijkstra with a binary heap and Kruskal with union-find in Python, then shows the same Dijkstra routine in C++, Java and TypeScript. Vertices are numbered 0..n-1 and the graph is an adjacency list adj[u] = [(v, w), ...].
import heapq
from math import inf
def dijkstra(adj, source):
n = len(adj)
dist = [inf] * n
parent = [-1] * n
dist[source] = 0
heap = [(0, source)]
while heap:
d, u = heapq.heappop(heap)
if d > dist[u]: # stale entry, u already has a better distance
continue
for v, w in adj[u]:
nd = d + w
if nd < dist[v]:
dist[v] = nd
parent[v] = u
heapq.heappush(heap, (nd, v))
return dist, parent
def path_to(parent, target):
path = []
while target != -1:
path.append(target)
target = parent[target]
return path[::-1]
adj = [[(1, 4), (2, 1)], [(3, 1)], [(1, 2), (3, 5)], [(4, 3)], []]
dist, parent = dijkstra(adj, 0)
print(dist) # [0, 3, 1, 4, 7]
print(path_to(parent, 4)) # [0, 2, 1, 3, 4]Line by line:
heapq turns a plain list into a binary min-heap; tuples compare by their first item, so the smallest distance comes out first.dist starts at infinity, parent at -1 (no predecessor yet).if d > dist[u]: continue is the lazy-deletion check. Without it every stale pair would rescan u's edges and the running time would grow.dist[v] and parent[v] and push a new pair; the old pair stays in the heap and will be skipped.path_to walks the parent links back to the source. Check dist[target] != inf first; for an unreachable target it would return just [target].To answer a single-pair query, return as soon as the target is popped: its distance is final at that moment.
class DSU:
def __init__(self, n):
self.parent = list(range(n))
self.size = [1] * n
def find(self, x):
while self.parent[x] != x:
self.parent[x] = self.parent[self.parent[x]] # path halving
x = self.parent[x]
return x
def union(self, a, b):
a, b = self.find(a), self.find(b)
if a == b:
return False # would close a cycle
if self.size[a] < self.size[b]:
a, b = b, a
self.parent[b] = a # union by size
self.size[a] += self.size[b]
return True
def kruskal(n, edges):
dsu = DSU(n)
total, chosen = 0, []
for w, u, v in sorted(edges):
if dsu.union(u, v):
total += w
chosen.append((u, v, w))
if len(chosen) == n - 1:
break
return total, chosen
edges = [(1, 0, 1), (2, 1, 2), (3, 0, 2), (4, 2, 3), (5, 1, 3)] # (w, u, v)
print(kruskal(4, edges)) # (7, [(0, 1, 1), (1, 2, 2), (2, 3, 4)])Edges are stored as (w, u, v) so sorted orders them by weight. union returns False when both ends are already in the same component, which is exactly the "would form a cycle" test. If fewer than n - 1 edges are chosen, the graph is disconnected and the result is a minimum spanning forest.
std::priority_queue is a max-heap by default; greater turns it into a min-heap. Use long long so sums do not overflow.
#include <functional>
#include <limits>
#include <queue>
#include <vector>
using namespace std;
using ll = long long;
using State = pair<ll, int>;
vector<ll> dijkstra(const vector<vector<pair<int, ll>>>& adj, int src) {
vector<ll> dist(adj.size(), numeric_limits<ll>::max());
priority_queue<State, vector<State>, greater<State>> pq;
dist[src] = 0;
pq.push({0, src});
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (d > dist[u]) continue;
for (auto [v, w] : adj[u]) {
if (d + w < dist[v]) {
dist[v] = d + w;
pq.push({dist[v], v});
}
}
}
return dist;
}
// dijkstra(adj, 0) on the example graph returns {0, 3, 1, 4, 7}PriorityQueue is a min-heap ordered by the comparator. Here each entry is a long[] {distance, vertex}.
import java.util.*;
public class Dijkstra {
static long[] dijkstra(List<List<int[]>> adj, int src) {
long[] dist = new long[adj.size()];
Arrays.fill(dist, Long.MAX_VALUE);
dist[src] = 0;
PriorityQueue<long[]> pq = new PriorityQueue<>(Comparator.comparingLong(a -> a[0]));
pq.add(new long[] {0, src});
while (!pq.isEmpty()) {
long[] top = pq.poll();
long d = top[0];
int u = (int) top[1];
if (d > dist[u]) continue;
for (int[] e : adj.get(u)) {
int v = e[0];
if (d + e[1] < dist[v]) {
dist[v] = d + e[1];
pq.add(new long[] {dist[v], v});
}
}
}
return dist;
}
// dijkstra(adj, 0) on the example graph returns [0, 3, 1, 4, 7]
}JavaScript has no built-in priority queue, so we write a small binary heap: push sifts the new item up, pop moves the last item to the root and sifts it down.
type Item = [dist: number, vertex: number];
class MinHeap {
private a: Item[] = [];
get size() { return this.a.length; }
push(item: Item) {
const a = this.a;
a.push(item);
let i = a.length - 1;
while (i > 0) {
const p = (i - 1) >> 1;
if (a[p][0] <= a[i][0]) break;
[a[p], a[i]] = [a[i], a[p]];
i = p;
}
}
pop(): Item {
const a = this.a;
const top = a[0];
const last = a.pop()!;
if (a.length > 0) {
a[0] = last;
for (let i = 0; ; ) {
const l = 2 * i + 1, r = l + 1;
let m = i;
if (l < a.length && a[l][0] < a[m][0]) m = l;
if (r < a.length && a[r][0] < a[m][0]) m = r;
if (m === i) break;
[a[m], a[i]] = [a[i], a[m]];
i = m;
}
}
return top;
}
}
function dijkstra(adj: [number, number][][], src: number): number[] {
const dist = new Array<number>(adj.length).fill(Infinity);
const heap = new MinHeap();
dist[src] = 0;
heap.push([0, src]);
while (heap.size > 0) {
const [d, u] = heap.pop();
if (d > dist[u]) continue;
for (const [v, w] of adj[u]) {
if (d + w < dist[v]) {
dist[v] = d + w;
heap.push([dist[v], v]);
}
}
}
return dist;
}
console.log(dijkstra([[[1, 4], [2, 1]], [[3, 1]], [[1, 2], [3, 5]], [[4, 3]], []], 0)); // [ 0, 3, 1, 4, 7 ]parent array if you need the path, not just the distance.
0 comentarios
Iniciar sesión · Inicia sesión para dejar un comentario.
Sé el primero en comentar.