Los algortimos para saber la ruta más corta en realidad son varios, pero en esta entrada vamos a trabajar con 2 algortimos, el pseudocódigo, el código en Matlab, ejemplos y la eficiencia medido en tiempo de proceso.

¿Por qué Matlab?

Matlab tiene una excelente librería para grafos llamado Graph que permite relacionar los grafos en nodos (nodes) y aristas (edges) además de realizar buenas gráficas de estos grafos. También permite calcular el tiempo que se demora procesando de manera fácil. Para saber más de esta librería la documentación está completa en su link ofician de Graph and Network Algorithms.

Dijkstra

“También llamado algoritmo de caminos mínimos, es un algoritmo para la determinación del camino más corto dado un vértice origen al resto de los vértices en un grafo con pesos en cada arista.” – Wikipedia.

Este algoritmo fue descubierto por Edsger Dijkstra, un científico de la computación de los Paises bajos.

Pseudocódigo

   function Dijkstra(Graph, source):

       create vertex set Q

       for each vertex v in Graph:             // Initialization
           dist[v] ← INFINITY                  // Unknown distance from source to v
           add v to Q                         // All nodes initially in Q (unvisited nodes)

       dist[source] ← 0                // Distance from source to source

       while Q is not empty:
           u ← vertex in Q with min dist[u]    // Node with the least distance
                                               // will be selected first
           remove u from Q

           for each neighbor v of u:           // where v is still in Q.
               alt ← dist[u] + length(u, v)
               if alt < dist[v]:               // A shorter path to v has been found
                   dist[v] ← alt

       return dist[], prev[]

Realizaremos el pseudocódigo en Matlab, aunque este algoritmo está realizado partiendo de un nodo fuente, vamos a calcular el camino más corto de todos los pares. Suponamos el siguiente ejemplo:

Figura 1. Ejemplo 1

Para inicializar el código en Matlab sería:

names = {'A', 'B', 'C', 'D', 'E'};
s = [1 1 2 2 3 4];
t = [2 4 3 5 5 5];
w = [6 1 5 2 5 1];

G = graph(s,t, w, names);
p = plot(G);
labeledge(p,1:numedges(G),w);

Código Matlab Dijkstra

function dist = dijkstra(G)

    bidirection = 1;
    if string(class(G)) == 'digraph'
        bidirection = 0;
    end

    weights = G.Edges.Variables';
    totalNodes = numnodes(G);

    dist = zeros(totalNodes,totalNodes);

    for i = 1:totalNodes
       for j = 1:totalNodes
          if i ~= j
              dist(i,j) = Inf;
          end
       end
    end

    for oneNode = 1:totalNodes
       Q = [];
       for i = 1:totalNodes
           Q = [Q,i]; % add element
       end

       while numel(Q) ~= 0
           
           min = dist(oneNode,Q(1));
           for k = 1:numel(Q)
              if dist(oneNode,Q(k)) <= min
                 min = dist(oneNode,Q(k));
                 v = Q(k);
              end
           end

          Q = Q(Q~=v); % remove element
         
          if bidirection == 1
             N = neighbors(G,v)';
          else
             N = successors(G,v)';
          end

          for k = 1:numel(N)
             u = N(k);
             w = weights(findedge(G,v,u));

             alt = dist(oneNode,v) + w;
             if alt < dist(oneNode,u)
                dist(oneNode,u) = alt;
             end
          end
       end
   end 
end

• Identificamos en matlab si el grafo es bidireccional, solo para realizar ciertas funciones.
• Calculamos  un array de los pesos del grafo y el total de Nodos

• Declaramos la variable dist que será nuestra matriz de caminos más corto de todos los pares y el resultado final.
• Asignamos todos los caminos como infititos. excepto los caminos de un nodo al mismo nodo, estos se quedarán en 0. La matriz inicial entonces queda como en la Figura 1:

Figura 1. Matriz Inicial

Al realizar la primera iteración, es decir calcular los caminos más cortos para el nodo A en todos los pares quedaría como en la Figura 2:

Figura 2. Primera Iteración

Para completar la matriz de los caminos más cortos de todos los pares el resultado para el ejemplo 1 es como lo muestra la Figura 3:

Figura 3. Resultado

Floyd-Warshall

“Es un algoritmo para encontrar caminos más cortos en un gráfico ponderado con pesos de borde positivo o negativo (pero sin ciclos negativos).” – Wikipedia

Este algoritmo está diseñado para calcular los caminos cortos de todos los pares, a diferencia de Dijkstra el cual es necesario tener un nodo fuente origen.

Pseudocodigo:

let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)
for each vertex v
    dist[v][v] ← 0
for each edge (u,v)
   dist[u][v] ← w(u,v) // the weight of the edge (u,v)
for k from 1 to |V|
   for i from 1 to |V|
      for j from 1 to |V|
         if dist[i][j] == dist[i][k] + dist[k][j]
            dist[i][j] ← dist[i][k] + dist[k][j]
         end if

Código Matlab

function dist = floyd_warshall(G)

   weights = G.Edges.Variables';
   totalNodes = numnodes(G);
   dist = zeros(totalNodes,totalNodes);

   % Set first values
   for i = 1:totalNodes
      for j = 1:totalNodes
         if i ~= j
            dist(i,j) = Inf;
         end
         f = findedge(G,i,j);
         if f == 0
            continue;
         end
         dist(i,j) = weights(f);
      end
   end

   for k = 1:totalNodes
      for i = 1:totalNodes
         for j = 1:totalNodes

            ij = dist(i,j);
            ik = dist(i,k);
            kj = dist(k,j);

            if ij > ik + kj
               dist(i,j) = ik +kj;
            end
         end
      end
   end

end

Para el ejemplo 1 que trabajamos para Dijkstra nos tiene que dar el mismo resultado.

Fase Prueba

Ahora para realizar este ejemplo varias veces pero con algunas diferencias se realiza un programa en Matlab que genere aleatoriamente grafos con cierto número de nodos y conecte con ciertas probabilidades. Se realiza entonces la función randgraph que recibe el número de nodos, la probabilidad que tenga una arista con otro nodo y los pesos que se elijen aleatoriamente uniforme:

function G = randgraph(totalNodes, pro_edges, weights)

   nodes = zeros(totalNodes, totalNodes);

   for i = 1:totalNodes
      for k = 1:totalNodes
         if i ~= k
            p = 1 - pro_edges;
            hasEdge = va([0 1], [p pro_edges]);
            w = 0;
            if hasEdge == 1
               probabilities = zeros(1,numel(weights));
               probabilities = probabilities + (1/numel(weights));
               w = va(weights, probabilities);
            end

            nodes(i,k) = w;
         end
      end
   end
   G = digraph(nodes);
end

De esta manera podemos crear varis grafos parecidos al primero. Para probarlo corregmos el siguiente scrpit:

clc
numNodes = 5;
w = [1 2 3 4 5 6 7]; 
probabily = 0.45; 
G = randgraph(numNodes,probabily, w);
plot(G,'EdgeLabel',G.Edges.Weight);

Si corremos este script varias veces tendremos diferentes Grafos como en la Figura 4:

Figura 4. Grafos aleatoriemente generados con la función randgraph.

Ahora calculemos el tiempo promedio en que se demora procesando 500 grafos aleatorio y además que vaya subiendo el número de nodos cada 500 grafos usando el siguiente código:

clc
   minNodes = 3;
   maxNodes = 15;
   count = maxNodes-minNodes;
   w = [1 2 3 4 5 6];
   repeticiones = 500;

   meansDijk = zeros(1,count);
   meansFloy = zeros(1,count);

   for totalNodes = 1:count
      for r = 1:repeticiones
         G = randgraph(minNodes + totalNodes,0.8, w);

         tic;
         dijkstra(G);
         tiemposDijk(r) = toc;

         tic;
         floyd_warshall(G);
         tiemposFloy(r) = toc;

      end
      meansDijk(totalNodes) = mean(tiemposDijk);
      meansFloy(totalNodes) = mean(tiemposFloy);
   end

   disp("End");
   plot(meansDijk);
   hold on;
   plot(meansFloy);
   hold off;
   legend("Dijkstra">, "Floy-Warshall");

Corriendo este script (demora un poco) tenemos:

Figura 5. Tiempos de procesos entre Dijkstra y Floy-Warshall

Conclusiones

• Como se observa en la gráfica Dijkstra se demora mucho más que Floy-Warshall y la diferencia se hace más notable a medida que el grafo es más grande.
• Dijkstra tiene un aumento exponencial
• Aunque en la gráfica Floy-Warshall para ser una línea recta en realidad es una curva exponencial también. Incluso su complejidad algorítmica es Θ ( | V | 3 ).