Esta artículo hablaremos de una mejora en el cálculo del algoritmo más corto para Dijkstra y Floyd-Warshall trabajados en el artículo anterior Algoritmos Dijkstra & Floyd-Warshall.

El algoritmo se puede encontrar en GitHub con una clase con todos los métodos necesarios hasta el momento y un archivo Live Script de Matlab.

Github: https://github.com/arturoverbel/graph_matlab/tree/master

Clase Graph PRO

Esta vez incluimos una clase en Matlab para cargar todas las propiedades y los métodos que necesitamos. Las propiedades de la clase son en código:

classdef Graph_pro
 % Graph pro - Proyect
 % Multiples functions and calculs for graph from file
 
 properties
 source; % List sources vertexes e.g: [1 2 2 3]
 target; % List target vertexes e.g: [2 3 4 4] 
 weight; % Weight for each edge e.g: [1 2 4 1]
 vertex; % List all vertex.
 
 undirected = 0; % Indicate Type graph. 1 - One Directed. 0 - Two directed.
 end
end

Para poner a pruebas podemos utilizar el siguiente código:

s = [1 2 2 3 ];
t = [2 3 4 4 ];
w = [1 2 4 2 ];

Gr = Graph_pro(s,t, w);
Gr = Gr.setUndirected(1);
Gr.floyd_warshall()

Definimos entonces el array de fuente (source) y el destino (target) con un peso correspondiente (weight). Lo pasamos por el constructor de la clase y determinamos el grafo como Undirected. Para respuesta sería:

ans = 
 0    1    3   4
 Inf  0    2   3
 Inf  Inf  0   1
 Inf  Inf  Inf 0

La clase también tiene la posibilidad de crear un grafo aleatorio. Si  nosotros escribimos:

clear;
Gr = Graph_pro();
Gr = Gr.creategraph(5,0.75,[1]

El cual nos dice que creemos un grafo con 5 nodos, 0.75 probabilidad de enlaze con otro nodo y los  pesos se distribuyan aleantoriamente entre [1].

Tenemos como resultado:

Gr = 
 Graph_pro with properties:
 source: [1 1 1 1 2 2 3 3 4]
 target: [2 3 4 5 4 5 4 5 5]
 weight: [1 1 1 1 1 1 1 1 1]
 vertex: [1 2 3 4 5]
 undirected: 0

Graficando con la función de Graph de Matlab sería:

Figure 1. Grafo con 5 nodos

Algoritmo Dijkstra

function dist = dijkstra(obj)

  totalVertex = numel(obj.vertex);

  dist = zeros(totalVertex,totalVertex);
  dist(:) = Inf;

  for oneNode = 1:totalVertex

    Q = 1:totalVertex;
    dist(oneNode,oneNode) = 0;
    while numel(Q) ~= 0

      [~, l] = min( dist(oneNode,Q) );
      vIndex = Q(l);
      vVertex = obj.vertex(vIndex);

      Q = Q(Q~=vIndex);

      %Get Neighbors
      N = obj.target( find(obj.source==vVertex) );
      if obj.undirected == 0
        N = [N obj.source( find(obj.target==vVertex) ) ];
      end

      for k = 1:numel(N)
        uVertex = N(k);
        uIndex = find(obj.vertex==uVertex);
        w = obj.getWeight(uVertex,vVertex);

        alt = dist(oneNode,vIndex) + w;
        if alt < dist(oneNode,uIndex)
          dist(oneNode,uIndex) = alt;
        end
      end
    end
  end
end

El algoritmo es más simple que el anterior y es más parecido al pseudocódigo de Dijkstra.

Algoritmo Floyd-Warshall

function dist = floyd_warshall(obj)

  totalVertex = numel(obj.vertex);
  dist = zeros(totalVertex,totalVertex);
  dist(:) = Inf;

  for k = 1:totalVertex+1:totalVertex*totalVertex
    dist(k) = 0;
  end

  for k = 1:numel(obj.source)

    w = obj.weight(k);
    uIndex = find(obj.vertex==obj.source(k));
    vIndex = find(obj.vertex==obj.target(k));

    dist( uIndex, vIndex ) = w;
    if obj.undirected == 0
      dist( vIndex, uIndex ) = w;
    end
  end

  for k = 1:totalVertex
    for i = 1:totalVertex
      for j = 1:totalVertex

        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

En ambos algoritmos tener en cuenta que se utiliza las variables que dicen el indice de un nodo. Esto se debe a que los nodos no necesariamente pueden ser los números consecutivos, así que se marca su ubicación en el array de todos los nodos de la variable dist.

Pruebas con múltiples grafos aleatorios

Se realiza una prueba entonces usando otro método de la clase llamado test_calc. El código a continuación:

function promedios = test_calc(obj, calc, numMinNodes, numMaxNodes, repeticiones)
 
  numScenarios = numMaxNodes-numMinNodes+1;
  promedios = zeros(1,numScenarios);
  for numNodes = numMinNodes:numMaxNodes
    w = [1 2 3 4 5 6];
    suma = 0;
    for caso = 1:repeticiones
 
      Gr = Graph_pro();
      Gr = Gr.creategraph(numNodes,0.75,w);
 
      tic;
      switch calc
        case "floyd_warshall"
          Gr.floyd_warshall();
        case "dijkstra"
          Gr.dijkstra();
      end
 
      time = toc;
      suma = suma + time;
    end
 
    promedioCalc = suma / repeticiones;
    promedios(numNodes-numMinNodes+1) = promedioCalc;
  end
end

Este método recibe como parametros,

• calc: El cálculo de camino más corto a evaluar
• numMinNodes: Mínimo número de nodos de los grafos a poner a prueba
• numMaxNodes: Máximo número de nodos de los grafos a poner a prueba
• repeticiones: Cuantas repetiones se realizarán para determinados grafos.

Esto retorne un array de promedio de cuánto duró resolviendo el algoritmo para cada grafo con número de nodos entre numMinNodes y numMaxNodes.

Podemos realizar una pequeña prueba resolviendo:

promediosDijkstra = Gr.test_calc("dijkstra", 5, 6, repeticiones);
promediosFloyd = Gr.test_calc("floyd_warshall", 5, 6, repeticiones);

Graficando los resultados tenemos:

Figura 2. Prueba entre 2 algoritmos con 1000 grafos de 5 y 6 nodos.

Realizemos las pruebas un poco más pesadas. Realizamos el siguiente test un poco más escalable:

minNodes = 5;
maxNodes = 15;
repeticiones = 1000;
Gr = Graph_pro();
promediosDijkstra = Gr.test_calc("dijkstra", minNodes, maxNodes, repeticiones);
promediosFloyd = Gr.test_calc("floyd_warshall", minNodes, maxNodes, repeticiones);
numNodes = minNodes:maxNodes;
plot(numNodes,promediosDijkstra, '-o');
hold on;
plot(numNodes,promediosFloyd, '-o');
hold off;
title('Tiempo de cálculo de camino más corto en Grafos aleatorios');
ylabel('Tiempo (seconds)');
legend(['Dijkstra'],[Floyd-Warshall']);
for k=1:numel(numNodes)
  t1 = text(numNodes(k),promediosDijkstra(k),[num2str(promediosDijkstra(k))]);
  t1.Color = 'red';
  t2 = text(numNodes(k),promediosFloyd(k),[num2str(promediosFloyd(k))]);
  t2.Color = 'blue';
end

El resultado sería:

Figura 3. Pruebas de tiempos de algoritmos con 1000 grafos de 5 a 15 nodos

Podemos ver por ejemplo que para grafos de 9 nodos con 1000 repeticiones del algoritmo el tiempo de cálculo para Dijkstra es 0.067 segundos mientras que en Floyd-Warshall es de 0.0004 segundos.

Además que a medida que crece el número de nodos en Dijkstra aumenta aparentemente exponencial. Mientras que en Floyd-Warshall no se distingue el aumento en tiempo. Acerquemos más la gráfica solo para Floyd-Warshall y esta vez realicemoslo con 3000 repeticiones cada una:

Floyd-Warshall

Figura 4. Prueba con 3000 repeticiones entre grafos de nodos entre 9 y 15 para el algoritmo Floyd-Warshall

Para grafos con 5 nodos tenemos en un tiempo de respuesta de 0.00011 y para grafos con 15 nodos tenemos en un tiempo de respuesta en promedio de 0.000425 lo que podemos ver que no aumenta demasiado con estos nodos.

Intentemos con nodos mucho más grandes, entre 10 y 50 nodos. Los resultados son:

Figura 5. Prueba con 1000 grafos de 10 y 50 nodos. Para Floyd-Warshall

Como se puede observar tiene una curva exponencial a medidad que sube el número de nodos de un grafo. Con 50 nodos, el tiempo de cálculo para Floyd-Warshall es de 0.0037 segundos en promedio.

Dijkstra

Para el algoritmo de Dijkstra tenemos la siguiente información:

Figura 6. Tiempos de Dijkstra para grados entre 9 y 30 nodos como 2000 repeticiones cada uno.

Podemos observar que para grafo de 9 nodos nos da un tiempo promedio de respuesta de 0.034 segundos. Este dato ya es mucho mayor para Floyd-Warshall con 50 nodos.

Para grafos con 30 nodos tenemos un tiempo promedio de respuesta de 1.2646 segundos.

 Prueba con datos reales

Se realizan pruebas en datos de facebook reales. El archivo está disponible en mi github personal: https://github.com/arturoverbel/graph_matlab/blob/master/data/facebook_combined.txt Para Dijkstra no hubo respuesta en mi computador, más de 6 horas. Pero para Floyd-Warshall el tiempo de respuesta fueron de 1457.456945 segundos, aproximadamente 23 minutos.