Algoritmo de Dijkstra

import heapq

mapa = {}


def carretera(a, b, km):
    mapa.setdefault(a, {})[b] = km
    mapa.setdefault(b, {})[a] = km


carretera("Madrid", "Zaragoza", 315)   # km aproximados
carretera("Zaragoza", "Barcelona", 300)
carretera("Madrid", "Valencia", 355)
carretera("Valencia", "Barcelona", 350)
carretera("Madrid", "Bilbao", 400)
carretera("Bilbao", "Zaragoza", 305)
carretera("Madrid", "Granada", 420)
carretera("Granada", "Málaga", 125)
carretera("Madrid", "Sevilla", 530)
carretera("Sevilla", "Málaga", 205)
carretera("Sevilla", "Granada", 250)
carretera("Valencia", "Murcia", 240)
carretera("Murcia", "Granada", 280)

dist = {"Madrid": 0}
previa = {}
fijas = {}                                          # un dict conserva el orden: el de fijarse
cola = [(0, "Madrid")]
while cola:
    km, ciudad = heapq.heappop(cola)                # la más cercana de las pendientes
    if ciudad in fijas:
        continue                                    # entrada vieja: ya estaba fijada
    fijas[ciudad] = km
    for vecina, tramo in mapa[ciudad].items():
        nueva = km + tramo
        if nueva < dist.get(vecina, float("inf")):
            dist[vecina] = nueva
            previa[vecina] = ciudad
            heapq.heappush(cola, (nueva, vecina))

print("Orden en que se fijan las ciudades:")
for c, km in fijas.items():
    print(f"  {c}: {km} km")
for destino in ["Barcelona", "Málaga"]:
    camino = []
    c = destino
    while c is not None:
        camino.insert(0, c)
        c = previa.get(c)
    print(f"Madrid → {destino}: " + " → ".join(camino))

const mapa = new Map();

function carretera(a, b, km) {
    if (!mapa.has(a)) mapa.set(a, new Map());
    if (!mapa.has(b)) mapa.set(b, new Map());
    mapa.get(a).set(b, km);
    mapa.get(b).set(a, km);
}

carretera("Madrid", "Zaragoza", 315);   // km aproximados
carretera("Zaragoza", "Barcelona", 300);
carretera("Madrid", "Valencia", 355);
carretera("Valencia", "Barcelona", 350);
carretera("Madrid", "Bilbao", 400);
carretera("Bilbao", "Zaragoza", 305);
carretera("Madrid", "Granada", 420);
carretera("Granada", "Málaga", 125);
carretera("Madrid", "Sevilla", 530);
carretera("Sevilla", "Málaga", 205);
carretera("Sevilla", "Granada", 250);
carretera("Valencia", "Murcia", 240);
carretera("Murcia", "Granada", 280);

const dist = new Map([["Madrid", 0]]);
const previa = new Map();
const fijas = new Set();                            // un Set conserva el orden: el de fijarse
const cola = [[0, "Madrid"]];                       // sin cola de prioridad en la biblioteca: un array que se ordena
while (cola.length > 0) {
    cola.sort((x, y) => x[0] - y[0]);
    const [km, ciudad] = cola.shift();              // la más cercana de las pendientes
    if (fijas.has(ciudad)) continue;                // entrada vieja: ya estaba fijada
    fijas.add(ciudad);
    for (const [vecina, tramo] of mapa.get(ciudad)) {
        const nueva = km + tramo;
        if (nueva < (dist.get(vecina) ?? Infinity)) {
            dist.set(vecina, nueva);
            previa.set(vecina, ciudad);
            cola.push([nueva, vecina]);
        }
    }
}
console.log("Orden en que se fijan las ciudades:");
for (const c of fijas) console.log(`  ${c}: ${dist.get(c)} km`);
for (const destino of ["Barcelona", "Málaga"]) {
    const camino = [];
    for (let c = destino; c !== undefined; c = previa.get(c)) camino.unshift(c);
    console.log(`Madrid → ${destino}: ${camino.join(" → ")}`);
}

using System;
using System.Collections.Generic;

class Program {
    static readonly Dictionary<string, Dictionary<string, int>> mapa = new();

    static void Carretera(string a, string b, int km) {
        if (!mapa.ContainsKey(a)) mapa[a] = new Dictionary<string, int>();
        if (!mapa.ContainsKey(b)) mapa[b] = new Dictionary<string, int>();
        mapa[a][b] = km;
        mapa[b][a] = km;
    }

    static void Main() {
        Carretera("Madrid", "Zaragoza", 315);   // km aproximados
        Carretera("Zaragoza", "Barcelona", 300);
        Carretera("Madrid", "Valencia", 355);
        Carretera("Valencia", "Barcelona", 350);
        Carretera("Madrid", "Bilbao", 400);
        Carretera("Bilbao", "Zaragoza", 305);
        Carretera("Madrid", "Granada", 420);
        Carretera("Granada", "Málaga", 125);
        Carretera("Madrid", "Sevilla", 530);
        Carretera("Sevilla", "Málaga", 205);
        Carretera("Sevilla", "Granada", 250);
        Carretera("Valencia", "Murcia", 240);
        Carretera("Murcia", "Granada", 280);

        var dist = new Dictionary<string, int> { ["Madrid"] = 0 };
        var previa = new Dictionary<string, string>();
        var fijas = new List<string>();                       // en el orden en que se fijan
        var cola = new PriorityQueue<string, int>();
        cola.Enqueue("Madrid", 0);
        while (cola.TryDequeue(out var ciudad, out int km)) {  // la más cercana de las pendientes
            if (fijas.Contains(ciudad)) continue;              // entrada vieja: ya estaba fijada
            fijas.Add(ciudad);
            foreach (var (vecina, tramo) in mapa[ciudad]) {
                int nueva = km + tramo;
                if (nueva < dist.GetValueOrDefault(vecina, int.MaxValue)) {
                    dist[vecina] = nueva;
                    previa[vecina] = ciudad;
                    cola.Enqueue(vecina, nueva);
                }
            }
        }
        Console.WriteLine("Orden en que se fijan las ciudades:");
        foreach (string c in fijas) Console.WriteLine(
quot;  {c}: {dist[c]} km");
        foreach (string destino in new[] { "Barcelona", "Málaga" }) {
            var camino = new List<string>();
            for (string? c = destino; c != null; c = previa.GetValueOrDefault(c)) camino.Insert(0, c);
            Console.WriteLine(
quot;Madrid → {destino}: {string.Join(" → ", camino)}");
        }
    }
}

<?php
$mapa = [];

function carretera(array &$mapa, string $a, string $b, int $km): void {
    $mapa[$a][$b] = $km;
    $mapa[$b][$a] = $km;
}

carretera($mapa, "Madrid", "Zaragoza", 315);   // km aproximados
carretera($mapa, "Zaragoza", "Barcelona", 300);
carretera($mapa, "Madrid", "Valencia", 355);
carretera($mapa, "Valencia", "Barcelona", 350);
carretera($mapa, "Madrid", "Bilbao", 400);
carretera($mapa, "Bilbao", "Zaragoza", 305);
carretera($mapa, "Madrid", "Granada", 420);
carretera($mapa, "Granada", "Málaga", 125);
carretera($mapa, "Madrid", "Sevilla", 530);
carretera($mapa, "Sevilla", "Málaga", 205);
carretera($mapa, "Sevilla", "Granada", 250);
carretera($mapa, "Valencia", "Murcia", 240);
carretera($mapa, "Murcia", "Granada", 280);

$dist = ["Madrid" => 0];
$previa = [];
$fijas = [];                                       // las claves conservan el orden: el de fijarse
$cola = new SplPriorityQueue();                    // saca la MAYOR prioridad: se usa -km
$cola->insert(["Madrid", 0], 0);
while (!$cola->isEmpty()) {
    [$ciudad, $km] = $cola->extract();             // la más cercana de las pendientes
    if (isset($fijas[$ciudad])) continue;          // entrada vieja: ya estaba fijada
    $fijas[$ciudad] = $km;
    foreach ($mapa[$ciudad] as $vecina => $tramo) {
        $nueva = $km + $tramo;
        if ($nueva < ($dist[$vecina] ?? PHP_INT_MAX)) {
            $dist[$vecina] = $nueva;
            $previa[$vecina] = $ciudad;
            $cola->insert([$vecina, $nueva], -$nueva);
        }
    }
}
echo "Orden en que se fijan las ciudades:\n";
foreach ($fijas as $c => $km) echo "  $c: $km km\n";
foreach (["Barcelona", "Málaga"] as $destino) {
    $camino = [];
    for ($c = $destino; $c !== null; $c = $previa[$c] ?? null) array_unshift($camino, $c);
    echo "Madrid → $destino: " . implode(" → ", $camino) . "\n";
}

import heapq

NODOS = ["A", "B", "C", "D"]
ARISTAS = [("A", "B", 2), ("A", "C", 5), ("C", "B", -4), ("B", "D", 1)]
INF = float("inf")


def dijkstra(origen):
    dist = {n: INF for n in NODOS}
    dist[origen] = 0
    fijos = set()
    cola = [(0, origen)]
    while cola:
        d, u = heapq.heappop(cola)
        if u in fijos:
            continue
        fijos.add(u)
        for de, a, peso in ARISTAS:
            if de == u and d + peso < dist[a]:
                dist[a] = d + peso
                heapq.heappush(cola, (d + peso, a))
    return dist


def bellman_ford(origen):
    """Relaja TODAS las aristas V − 1 veces. Más lento, pero admite pesos negativos."""
    dist = {n: INF for n in NODOS}
    dist[origen] = 0
    for _ in range(len(NODOS) - 1):
        for de, a, peso in ARISTAS:
            if dist[de] != INF and dist[de] + peso < dist[a]:
                dist[a] = dist[de] + peso
    return dist


def texto(dist):
    return " ".join(f"{n}={d}" for n, d in dist.items())


print("Dijkstra:     " + texto(dijkstra("A")))
print("Bellman-Ford: " + texto(bellman_ford("A")))
print("D sale mal con Dijkstra: B se fijó con 2 y, cuando C → B lo bajó a 1, ya no se propagó a D.")

const NODOS = ["A", "B", "C", "D"];
const ARISTAS = [["A", "B", 2], ["A", "C", 5], ["C", "B", -4], ["B", "D", 1]];

function dijkstra(origen) {
    const dist = new Map(NODOS.map((n) => [n, Infinity]));
    dist.set(origen, 0);
    const fijos = new Set();
    const cola = [[0, origen]];                     // un array que se ordena hace de cola de prioridad
    while (cola.length > 0) {
        cola.sort((x, y) => x[0] - y[0]);
        const [d, u] = cola.shift();
        if (fijos.has(u)) continue;
        fijos.add(u);
        for (const [de, a, peso] of ARISTAS)
            if (de === u && d + peso < dist.get(a)) {
                dist.set(a, d + peso);
                cola.push([d + peso, a]);
            }
    }
    return dist;
}

/** Bellman-Ford: relaja TODAS las aristas V − 1 veces. Más lento, pero admite pesos negativos. */
function bellmanFord(origen) {
    const dist = new Map(NODOS.map((n) => [n, Infinity]));
    dist.set(origen, 0);
    for (let i = 1; i < NODOS.length; i++)
        for (const [de, a, peso] of ARISTAS)
            if (dist.get(de) !== Infinity && dist.get(de) + peso < dist.get(a)) dist.set(a, dist.get(de) + peso);
    return dist;
}

const texto = (dist) => [...dist].map(([n, d]) => `${n}=${d}`).join(" ");

console.log("Dijkstra:     " + texto(dijkstra("A")));
console.log("Bellman-Ford: " + texto(bellmanFord("A")));
console.log("D sale mal con Dijkstra: B se fijó con 2 y, cuando C → B lo bajó a 1, ya no se propagó a D.");

using System;
using System.Collections.Generic;
using System.Linq;

class Program {
    static readonly string[] Nodos = { "A", "B", "C", "D" };
    static readonly (string De, string A, int Peso)[] Aristas = { ("A", "B", 2), ("A", "C", 5), ("C", "B", -4), ("B", "D", 1) };

    static Dictionary<string, int> Dijkstra(string origen) {
        var dist = Nodos.ToDictionary(n => n, _ => int.MaxValue);
        dist[origen] = 0;
        var fijos = new HashSet<string>();
        var cola = new PriorityQueue<string, int>();
        cola.Enqueue(origen, 0);
        while (cola.TryDequeue(out var u, out int d)) {
            if (!fijos.Add(u)) continue;
            foreach (var (de, a, peso) in Aristas)
                if (de == u && d + peso < dist[a]) {
                    dist[a] = d + peso;
                    cola.Enqueue(a, d + peso);
                }
        }
        return dist;
    }

    // Bellman-Ford: relaja TODAS las aristas V − 1 veces. Más lento, pero admite pesos negativos.
    static Dictionary<string, int> BellmanFord(string origen) {
        var dist = Nodos.ToDictionary(n => n, _ => int.MaxValue);
        dist[origen] = 0;
        for (int i = 1; i < Nodos.Length; i++)
            foreach (var (de, a, peso) in Aristas)
                if (dist[de] != int.MaxValue && dist[de] + peso < dist[a]) dist[a] = dist[de] + peso;
        return dist;
    }

    static string Texto(Dictionary<string, int> dist) => string.Join(" ", dist.Select(p => 
quot;{p.Key}={p.Value}"));

    static void Main() {
        Console.WriteLine("Dijkstra:     " + Texto(Dijkstra("A")));
        Console.WriteLine("Bellman-Ford: " + Texto(BellmanFord("A")));
        Console.WriteLine("D sale mal con Dijkstra: B se fijó con 2 y, cuando C → B lo bajó a 1, ya no se propagó a D.");
    }
}

<?php
const NODOS = ["A", "B", "C", "D"];
const ARISTAS = [["A", "B", 2], ["A", "C", 5], ["C", "B", -4], ["B", "D", 1]];

function dijkstra(string $origen): array {
    $dist = array_fill_keys(NODOS, PHP_INT_MAX);
    $dist[$origen] = 0;
    $fijos = [];
    $cola = new SplPriorityQueue();                // saca la MAYOR prioridad: se usa -distancia
    $cola->insert([$origen, 0], 0);
    while (!$cola->isEmpty()) {
        [$u, $d] = $cola->extract();
        if (isset($fijos[$u])) continue;
        $fijos[$u] = true;
        foreach (ARISTAS as [$de, $a, $peso])
            if ($de === $u && $d + $peso < $dist[$a]) {
                $dist[$a] = $d + $peso;
                $cola->insert([$a, $d + $peso], -($d + $peso));
            }
    }
    return $dist;
}

/** Bellman-Ford: relaja TODAS las aristas V − 1 veces. Más lento, pero admite pesos negativos. */
function bellmanFord(string $origen): array {
    $dist = array_fill_keys(NODOS, PHP_INT_MAX);
    $dist[$origen] = 0;
    for ($i = 1; $i < count(NODOS); $i++)
        foreach (ARISTAS as [$de, $a, $peso])
            if ($dist[$de] !== PHP_INT_MAX && $dist[$de] + $peso < $dist[$a]) $dist[$a] = $dist[$de] + $peso;
    return $dist;
}

function texto(array $dist): string {
    return implode(" ", array_map(fn($n, $d) => "$n=$d", array_keys($dist), $dist));
}

echo "Dijkstra:     " . texto(dijkstra("A")) . "\n";
echo "Bellman-Ford: " . texto(bellmanFord("A")) . "\n";
echo "D sale mal con Dijkstra: B se fijó con 2 y, cuando C → B lo bajó a 1, ya no se propagó a D.\n";