La matriz de predecesores de un grafo nos indica el camino más corto de un nodo a otro para todos los nodos de un grafo. Hay una variedad de métodos para construir el camino más corto de un grafo, en esta ocasión usaremos los algoritmos de Dijkstra y Floyd-Warshall para construir la matriz de distancia para formar la matriz de predecesores.
Matriz de predecesores
Tenemos un grafo G representado en la figura 1:
Figura 1. Grafo G con 5 nodos
En este grafo la Matriz de predecesores sería:
Figura 2. Matriz de predecesores del grafo G
Para leerlo tomemos como ejemplo el nodo 0. En la primera fila podemos leer el camino más corto desde el nodo 0 a todas las demás. En la segunda columna aparece el 4, nos indica que el predecesor del nodo 1 para llegar al nodo 0 es el nodo 4. Si nos vamos a la columna del nodo 4 (quinta columna) vemos que el predecesor del nodo 4 para llegar al nodo 0 es el mismo nodo 0. De esta manera se puede armar el camino. Los que están marcados con -1 nos dice que no hay predecesor para llegar a tal nodo.
Dijkstra
El algoritmo para generar los predecesores de un nodo es el siguiente:
import numpy as np
def Dijkstra_PREV(source, graph):
Q = list(graph.nodes)
prev = np.full((graph.nodes.size), -1)
dist = np.full((graph.nodes.size), np.inf)
dist[source] = 0
while len(Q) > 0:
min, u, index = np.inf, 0, 0
for i, q in enumerate(Q):
if dist[q] < min:
min, u, index = dist[q], q, i
Q.pop(index)
u_targets, u_weights = graph.get_targets_from_source(u, return_weight=True)
for v, w_uv in zip(u_targets, u_weights):
aux = dist[u] + w_uv
if aux < dist[v]:
dist[v] = aux
prev[v] = u
return dist, prev
Para dijkstra solo agregamos la linea 7 y la linea 26. De esta manera nos devuelve tanto las distancia (cuánto cuesta llegar al nodo) como los predecesores con la variable prev.
Para correrlo, usaremos el mismo grafo anterior:
# Import modules... sources = [0, 0, 1, 1, 1, 2, 2, 2, 3, 4] targets = [3, 4, 2, 3, 4, 1, 3, 4, 4, 1] weights = [8, 6, 4, 5, 2, 9, 8, 5, 4, 2] graph = Graph(sources, targets, weights) graph.print_r() dist, prev = Dijkstra_PREV(0, graph) print(prev)
El resultado:
Figura 3. Resultados dijkstra con rpedecesores
Dijkstra APSP
El APSP de dijkstra es ejecutar el código por cada nodo del grafo, la función sería:
def Dijkstra_apsp_PREV(graph):
result = np.full((graph.nodes.size, graph.nodes.size), np.inf)
result_prev = np.full((graph.nodes.size, graph.nodes.size), -1)
total = len(graph.nodes)
for i, v in enumerate(graph.nodes):
result[i], result_prev[i] = Dijkstra_PREV(v, graph)
return result, result_prev
El resultado sería:
Figura 4. Resultados Dijkstra APSP por consola
Floyd-Warshall
Así como en Dijkstra, se agregan algunas nuevas lineas para conseguir la matriz de predecesores:
import numpy as np
def Floyd_Warshall_PREV(graph):
dist = np.full((graph.nodes.size, graph.nodes.size), np.inf)
prev = np.full((graph.nodes.size, graph.nodes.size), -1)
for idx in range(graph.source.size):
dist[graph.source[idx], graph.target[idx]] = graph.weight[idx]
prev[graph.source[idx], graph.target[idx]] = graph.source[idx]
for k in graph.nodes:
for i in graph.nodes:
if k == i:
dist[i, k] = 0
prev[i, k] = -1
for j in graph.nodes:
if dist[i, j] > dist[i, k] + dist[k, j]:
dist[i, j] = dist[i, k] + dist[k, j]
prev[i, j] = prev[k, j]
return dist, prev
Al correr tenemos el mismo resultado.
Código para test
import os
import sys
import numpy as np
myPath = os.path.dirname(os.path.abspath(__file__))
sys.path.insert(0, myPath + '/../')
from graph.Graph import Graph
from algorithms_prev.dijkstra_prev import *
from algorithms_prev.floyd_warshall_prev import *
sources = [0, 0, 1, 1, 1, 2, 2, 2, 3, 4]
targets = [3, 4, 2, 3, 4, 1, 3, 4, 4, 1]
weights = [8, 6, 4, 5, 2, 9, 8, 5, 4, 2]
#Grafo con más de una misma solución
"""
sources = [0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5]
targets = [1, 2, 5, 0, 3, 4, 5, 5, 3, 4, 0, 1, 0, 1, 4, 5, 0, 2, 3, 5, 1, 4]
weights = [9, 6, 3, 6, 8, 7, 5, 4, 4, 4, 5, 1, 4, 4, 9, 2, 9, 7, 1, 4, 6, 1]
"""
graph = Graph(sources, targets, weights)
#Grafos Aleatorios
"""
graph = Graph.creategraph(6, .8)
"""
graph.print_r()
dist, prev = Dijkstra_apsp_PREV(graph)
print(dist)
print(prev)
print("-----------------------------------------")
dist, prev2 = Floyd_Warshall_PREV(graph)
print(prev2)
Al descargar el repositorio se puede ejecutar el código anterior para usar usus propios grafos y realizar pruebas.
Código
Algoritmos: https://github.com/arturoverbel/graph_presentation/tree/master/algorithms_prev
Comentarios