Después de haber repasado los fundamentos de los grafos: cómo se almacenan mediante matrices o listas de adyacencia, cómo se mantienen conectados mediante el algoritmo de Prim o Kruskal.. llegamos al algoritmo de Dijkstra.
Con este algoritmo, que nos sirve tanto para grafos dirigidos como no dirigidos, podemos saber cuál es el camino de menor coste desde un nodo origen a todos los demás. Usa la estrategia de programación voraz, mediante la cual, vamos construyendo la solución sin tener que volver atrás en cada decisión que vamos tomando.
Las aplicaciones de este algorimo son muchas más que los algoritmos predecesores. Por ejemplo, para calcular rutas en un mapa de carreteras, para conectar llamadas telefónicas mediante circuitos virtuales, enrutamiento de paquetes de red, coger varios autobuses/trenes/aviones minimizando coste o tiempo, buscar el mejor camino hasta el punto de recarga de un robot aspiradora, y un largo etcétera..
Estructura del algoritmo
Se basa en la selección arbitraria de un nodo origen, en el uso de un conjunto de nodos pendientes de estudiar, un vector especial que almacena el coste de llegar a cada nodo, y un vector de predecesores que guarda el nodo anterior para llegar a cada posición.
Mediante estas estructuras de datos, vamos estudiando las aristas entre nodo y nodo. Así de esta manera, se van recalculando el vector de los costes y el de los predecesores. En este ejemplo se parte del nodo inicial 0. Y se van estudiando nodo a nodo, los caminos posibles hasta el siguiente nodo en estudio. Cuando ya hemos estudiado todos los nodos, tendremos el camino de menor coste a cualquier nodo desde el nodo origen.
Por ejemplo
En este caso está configurado el script para generar grafos dirigidos:
0 --> 1(3) 1 --> 3(4) --> 2(1) 2 --> 5(2) --> 3(1) 3 --> 1(1) --> 4(4) 4 --> 6(1) 5 --> 3(5) 6 --> 4(1) INITIAL> Not used nodes: 1-2-3-4-5-6 INITIAL> Special: 3-INF-INF-INF-INF-INF INITIAL> Predecessor: 0-#-#-#-#-# >>>> Found min edge! $adjacentList[0][1]=3 >>>> Next min node to use is 1 Not used nodes: 2-3-4-5-6 Special: 3-4-7-INF-INF-INF Predecessor: 0-1-1-#-#-# >>>> Found min edge! $adjacentList[1][2]=1 >>>> Next min node to use is 2 Not used nodes: 3-4-5-6 Special: 3-4-5-INF-6-INF Predecessor: 0-1-2-#-2-# >>>> Found min edge! $adjacentList[1][3]=4 >>>> Found min edge! $adjacentList[2][3]=1 >>>> Next min node to use is 3 Not used nodes: 4-5-6 Special: 3-4-5-9-6-INF Predecessor: 0-1-2-3-2-# >>>> Found min edge! $adjacentList[2][5]=2 >>>> Next min node to use is 5 Not used nodes: 4-6 Special: 3-4-5-9-6-INF Predecessor: 0-1-2-3-2-# >>>> Found min edge! $adjacentList[3][4]=4 >>>> Next min node to use is 4 Not used nodes: 6 Special: 3-4-5-9-6-10 Predecessor: 0-1-2-3-2-4 FINAL> Special: 3-4-5-9-6-10 FINAL> Predecessor: 0-1-2-3-2-4
El resultado final son los dos vectores de las dos últimas líneas. El vector especial, nos indica el coste hasta el nodo i. Por ejemplo, veamos el camino desde el nodo 0 al 4. Tiene un coste de 9 unidades y su camino se construye de atrás a adelante 4-3-2-1-0, mediante el vector predecesor. Es decir, el camino de mínimo coste posible es el 0-1-2-3-4. Si estudiamos las opciones podemos ver que así es.
El código
<?php define('NUMBER_OF_NODES', 7);
define('NUMBER_OF_EDGES_PER_NODE', 2);
define('IS_DIRECTED_GRAPH', true);
$adjacentList = array();
fillRandomCosts($adjacentList);
printToScreen($adjacentList);
$special = $predecessor = array();
dijkstra($adjacentList, $special, $predecessor);
echo 'FINAL> Special: '.implode('-', $special).PHP_EOL
.'FINAL> Predecessor: '.implode('-', $predecessor).PHP_EOL;
function dijkstra($adjacentList, &$special, &$predecessor)
{
// Fill C with not used nodes.
$C = array();
for ($i = 1; $i < NUMBER_OF_NODES; ++$i) {
$C[] = $i;
}
// Fill special distances.
for ($i = 1; $i < NUMBER_OF_NODES; ++$i) {
$special[$i] = distanceFromTo($adjacentList, 0, $i);
if ($special[$i] < INF) {
$predecessor[$i] = 0;
} else {
$predecessor[$i] = '#';
}
}
echo 'INITIAL> Not used nodes: '.implode('-', $C).PHP_EOL
.'INITIAL> Special: '.implode('-', $special).PHP_EOL
.'INITIAL> Predecessor: '.implode('-', $predecessor).PHP_EOL;
// Study nodes in C to update $special and predecessor vectors.
while (count($C) > 1) {
$v = selectNextNodeThatMinimizesSpecial($adjacentList, $C, $special);
$C = array_diff($C, array($v));
if ($v == -1) {
echo 'IMPOSSIBLE TO FIND DIJKSTRA WITH ALL NODES! Cannot achieve all nodes!'.PHP_EOL;
exit;
}
foreach ($C as $w) {
if ($special[$w] > $special[$v] + distanceFromTo($adjacentList, $v, $w)) {
$special[$w] = $special[$v] + distanceFromTo($adjacentList, $v, $w);
$predecessor[$w] = $v;
}
}
echo 'Not used nodes: '.implode('-', $C).PHP_EOL
.'Special: '.implode('-', $special).PHP_EOL
.'Predecessor: '.implode('-', $predecessor).PHP_EOL;
}
}
function selectNextNodeThatMinimizesSpecial($adjacentList, &$C, &$special)
{
$minCost = INF;
$minNode = -1;
for ($i = 0; $i < NUMBER_OF_NODES; ++$i) {
foreach ($C as $node) {
if (!in_array($i, $C)
and isset($adjacentList[$i][$node])
and $adjacentList[$i][$node] < $minCost) {
echo '>>>> Found min edge! $adjacentList['.$i.']['.$node.']='.$adjacentList[$i][$node].PHP_EOL;
$minCost = $adjacentList[$i][$node];
$minNode = $node;
}
}
}
echo '>>>> Next min node to use is '.$minNode.PHP_EOL;
return $minNode;
}
function distanceFromTo($adjacentList, $from, $to)
{
if (isset($adjacentList[$from][$to])) {
return $adjacentList[$from][$to];
} else {
return INF;
}
}
function fillRandomCosts(&$adjacentList)
{
for ($i = 0; $i < NUMBER_OF_NODES; ++$i) {
$added = false;
while (!$added) {
for ($j = 0; $j < NUMBER_OF_EDGES_PER_NODE; ++$j) {
$adjacentNode = rand(0, NUMBER_OF_NODES - 1);
if ($adjacentNode != $i and $adjacentNode != $j) {
$adjacentNodeCost = rand(1, 5);
$adjacentList[$i][$adjacentNode] = $adjacentNodeCost;
if (!IS_DIRECTED_GRAPH) {
$adjacentList[$adjacentNode][$i] = $adjacentNodeCost;
}
$added = true;
}
}
}
}
}
function printToScreen($adjacentList)
{
for ($i = 0; $i < NUMBER_OF_NODES; ++$i) { echo $i; foreach ($adjacentList[$i] as $key => $value) {
echo ' --> '.$key.'('.$value.')';
}
echo PHP_EOL;
}
}
