Algoritmo de dijkstra en php: cómo implementarlo

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,
   nameVARCHAR(100) UNIQUE NOT NULL,
   created_at  TIMESTAMP DEFAULT CURRENT_TIMESTAMP
   );
   
   CREATE TABLE IF NOT EXISTS routes (
   id INT AUTO_INCREMENT PRIMARY KEY,
   from_cityVARCHAR(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).