ALGORITMO DE DIJKSTRA EN PHP: CÓMO IMPLEMENTARLO

Después de hablar del algoritmo de Dijkstra toca implementarlo en PHP. En este ejemplo se va a usar una base de datos MySQL:
  1. Estructura de la Base de Datos (MySQL): Esta estructura permite almacenar ciudades de forma centralizada y guardar rutas bidireccionales con distancias reales.

    CREATE TABLE IF NOT EXISTS cities (
    id     INT AUTO_INCREMENT PRIMARY KEY,
    name   VARCHAR(100) UNIQUE NOT NULL,
    created_at  TIMESTAMP DEFAULT CURRENT_TIMESTAMP
);

CREATE TABLE IF NOT EXISTS routes (
    id     INT AUTO_INCREMENT PRIMARY KEY,
    from_city   VARCHAR(100) NOT NULL,
    to_city     VARCHAR(100) NOT NULL,
    distance_km INT NOT NULL,
    created_at  TIMESTAMP DEFAULT CURRENT_TIMESTAMP,
    
    FOREIGN KEY (from_city) REFERENCES cities(name),
    FOREIGN KEY (to_city)   REFERENCES cities(name),
    
    UNIQUE KEY unique_route (from_city, to_city)
);
  2. Clase GRAPH

    class GraphFromDB {
    private PDO $pdo;

    public function __construct(PDO $pdo) {
   $this->pdo = $pdo;
    }

    /**
     * Carga todo el grafo desde la base de datos
     * Devuelve un array asociativo: ['Madrid' => ['Valencia' => 350, 'Barcelona' => 620], ...]
     */
    public function loadGraph(): array {
   $graph = [];

   // Obtener todas las rutas
   $stmt = $this->pdo->query("
  SELECT from_city, to_city, distance_km 
  FROM routes 
  ORDER BY from_city
   ");

   while ($row = $stmt->fetch(PDO::FETCH_ASSOC)) {
  $from = $row['from_city'];
  $to   = $row['to_city'];
  $dist = (int)$row['distance_km'];

  // Añadir en ambas direcciones (grafo no dirigido)
  $graph[$from][$to] = $dist;
  $graph[$to][$from] = $dist;
   }

   return $graph;
    }

    /**
     * (Opcional) Insertar datos de ejemplo una sola vez
     */
    public function insertExampleData(): void {
   // Insertar ciudades
   $cities = ['Madrid', 'Barcelona', 'Valencia', 'Zaragoza', 'Bilbao', 'Sevilla', 'Málaga'];
   foreach ($cities as $city) {
  $this->pdo->prepare("INSERT IGNORE INTO cities (name) VALUES (?)")->execute([$city]);
   }

   // Insertar rutas (distancias aproximadas reales)
   $routes = [
  ['Madrid', 'Barcelona', 620],
  ['Madrid', 'Valencia', 350],
  ['Madrid', 'Zaragoza', 320],
  ['Madrid', 'Bilbao', 400],
  ['Madrid', 'Sevilla', 530],
  ['Barcelona', 'Valencia', 350],
  ['Barcelona', 'Zaragoza', 300],
  ['Barcelona', 'Bilbao', 620],
  ['Valencia', 'Zaragoza', 300],
  ['Valencia', 'Sevilla', 650],
  ['Valencia', 'Málaga', 600],
  ['Zaragoza', 'Bilbao', 300],
  ['Sevilla', 'Málaga', 160],
   ];

   $stmt = $this->pdo->prepare("INSERT IGNORE INTO routes (from_city, to_city, distance_km) VALUES (?, ?, ?)");
   foreach ($routes as $route) {
  $stmt->execute($route);
   }
   echo 'Datos de ejemplo insertados correctamente.';
    }
}
  3. Clase Dijkstra

    class Dijkstra {
    private array $graph;

    public function __construct(array $graph) {
   $this->graph = $graph;
    }

    /**
     * Encuentra la ruta más corta y devuelve todo automáticamente
     */
    public function findShortestPath(string $source, string $target): array {
   if (!isset($this->graph[$source]) || !isset($this->graph[$target])) {
  throw new Exception("El origen o destino no existe en el grafo.");
   }

   $dist = [];
   $prev = [];
   $queue = new SplPriorityQueue();

   // Inicialización
   foreach (array_keys($this->graph) as $node) {
  $dist[$node] = INF;
  $prev[$node] = null;
   }

   $dist[$source] = 0;
   $queue->insert($source, 0);

   while (!$queue->isEmpty()) {
  $current = $queue->extract();

  if (!isset($dist[$current])) continue;

  foreach ($this->graph[$current] as $neighbor => $weight) {
      if ($weight < 0) {
     throw new Exception("Dijkstra no soporta pesos negativos.");
      }

      $alt = $dist[$current] + $weight;

      if ($alt < $dist[$neighbor]) {
     $dist[$neighbor] = $alt;
     $prev[$neighbor] = $current;
     $queue->insert($neighbor, -$alt);
      }
  }
   }

   // Reconstruir el camino
   $path = [];
   $current = $target;
   while ($current !== null) {
  array_unshift($path, $current);
  $current = $prev[$current] ?? null;
   }

   $success = (!empty($path) && $path[0] === $source);

   return [
  'success'     => $success,
  'path'   => $success ? $path : [],
  'distance'    => $success ? $dist[$target] : INF,
  'distance_km' => $success ? $dist[$target] . " km" : "Inalcanzable",
  'source' => $source,
  'target' => $target
   ];
    }
}

$graphDB = new GraphFromDB($pdo);

// Descomenta la primera vez para insertar datos de ejemplo:
// $graphDB->insertExampleData();

$graph = $graphDB->loadGraph();

$dijkstra = new Dijkstra($graph);

try {
    $result = $dijkstra->findShortestPath('Madrid', 'Málaga');

    echo 'RUTA MÁS CORTA DESDE BASE DE DATOS';
    echo "Origen:  {$result['source']}";
    echo "Destino: {$result['target']}";

    if ($result['success']) {
   echo "Ruta óptima: " . implode(" → ", $result['path']) . "\n";
   echo "Distancia:   {$result['distance_km']}\n";
    } else {
   echo 'No se encontró una ruta válida.';
    }

} catch (Exception $e) {
    echo 'Error: ' . $e->getMessage();
}

Explicación Detallada del Código

  1. Clase GraphFromDB
    • loadGraph(): Lee todas las rutas de la tabla routes y construye el grafo en memoria.
    • insertExampleData(): Inserta ciudades y rutas una sola vez (usa INSERT IGNORE para evitar duplicados).
  2. Clase Dijkstra Recibe el grafo cargado desde MySQL.
    • Usa SplPriorityQueue para mejor rendimiento.
    • Devuelve automáticamente el camino completo + distancia.
  3. Ventajas de esta aproximación
    • Fácil de mantener: solo añades filas en la tabla routes.
    • Escalable: puedes tener cientos de ciudades.
    • Bidireccional por defecto (se puede cambiar fácilmente si solo se necesitan rutas de un solo sentido).