Algoritmo de Dijkstra en PHP


El algoritmo de Dijkstra o también conocido como el algoritmo de caminos mínimos fue descrito por el informático holandés Edsger Dijkstra en 1956 y publicado en 1959. Es un algoritmo de búsqueda gráfica que resuelve el problema del camino más corto dado un vértice origen al resto de vértices en un grafo con pesos en cada arista.

Sea G = (V, E) un digrafo ponderado con pesos positivos de n vértices, suponiendo que a y z son dos vértices que pertenecen a V, de manera que z sea diferente de y que existe al menos un camino de a hasta z. El algoritmo de Dijkstra se encargará de encontrar un camino entre estos dos puntos con un coste mínimo. Su complejidad es O(n^2).

El algoritmo en PHP es el siguiente:

dijkstra

Anuncios

Acerca de silvercorp

Blog personal de Ye§i creado el 18/Ag/06 enfocado al diseño gráfico, tecnología y programación.

Publicado el diciembre 1, 2013 en Programación. Añade a favoritos el enlace permanente. 7 comentarios.

  1. Hola disculpa cheque tu código y por alguna razón no funciona, no se si se le tiene que agregar algo extra aparte del código que utilizas

  2. Excelente función !!!

  3. Amigo, disculpen la molestia pero tengo un problema, estuve revisando bastante y… no encuentro el motivo, la gran duda, ¿Cúal es el error?.

    Muchas gracias por la ayuda!

    He aquí el error:

    Notice: Array to string conversion in C:\xampp\htdocs\prueba\algoritmo\dijkstra\Dijkstra.php on line 13

    Warning: Illegal offset type in C:\xampp\htdocs\prueba\algoritmo\dijkstra\Dijkstra.php on line 17
    Warning: Illegal offset type in C:\xampp\htdocs\prueba\algoritmo\dijkstra\Dijkstra.php on line 18
    Warning: Illegal offset type in C:\xampp\htdocs\prueba\algoritmo\dijkstra\Dijkstra.php on line 26
    Warning: Illegal offset type in C:\xampp\htdocs\prueba\algoritmo\dijkstra\Dijkstra.php on line 27
    Warning: Illegal offset type in C:\xampp\htdocs\prueba\algoritmo\dijkstra\Dijkstra.php on line 26
    Warning: Illegal offset type in C:\xampp\htdocs\prueba\algoritmo\dijkstra\Dijkstra.php on line 27

    Notice: Array to string conversion in C:\xampp\htdocs\prueba\algoritmo\dijkstra\Dijkstra.php on line 32

    Notice: Array to string conversion in C:\xampp\htdocs\prueba\algoritmo\dijkstra\Dijkstra.php on line 32
    Warning: Illegal offset type in C:\xampp\htdocs\prueba\algoritmo\dijkstra\Dijkstra.php on line 33
    Warning: Illegal offset type in isset or empty in C:\xampp\htdocs\prueba\algoritmo\dijkstra\Dijkstra.php on line 37
    … infinito…

    El código:

    $edge[1], ‘cost’ => $edge[2]);
    }

    $vertices = array_unique($vertices);
    //$vertices = implode(array_unique($vertices)) ;

    foreach ($vertices as $vertex) {
    $dist[$vertex] = INF;
    $previous[$vertex] = NULL;
    }

    $dist[$source] = 0;
    $g = $vertices;
    while (count($g) > 0) {
    $min = INF;
    foreach ($g as $vertex) {
    if ($dist[$vertex] < $min) {
    $min = $dist[$vertex];
    $u = $vertex;
    }
    }

    $g = array_diff($g, array($u));
    if ($dist[$u] == INF or $u == $tarjet) {
    break;
    }

    if (isset($neighbours[$u])) {
    foreach ($neighbours as $arr) {
    $alt = $dist[$u] + $arr["cost"];
    if ($alt

    • Parece que el texto fue demasiado largo por ende no ha habido cabida para el código completo.

      El resto del código desde unas cuatro lineas antes:

      if (isset($neighbours[$u])) {
      foreach ($neighbours as $arr) {
      $alt = $dist[$u] + $arr[“cost”];
      if ($alt

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: