Ya vimos cómo realizar los algoritmos de Dijkstra & Floyd-Warshall en Matlab, Algoritmos Dijkstra & Floyd-Warshall, ahora veremos cómo hacer estos algoritmos en Python. Pero antes de empezar es importante conocer las siguientes librerías:
- NetworkX: Como dice su sitio oficial. Es un paquete de Python para la creación, manipulación y estudio de la estructura, dinámica y funciones de redes complejas. Pueden encontrar documentación de esta librería en: Overview – NetworkX
- Matplotlib: Es una biblioteca de trazado 2D de Python que produce figuras en una variedad de formatos y entornos. Lo utilizaremos para graficar el grafo, aunque no es tan intuitivo como las gráficas de Matlab. Matplotlib.
El código fuente está público en mi repositorio:
https://github.com/arturoverbel/graph_python
Ahora comenzemos
Dijkstra
El pseudocódigo de Dijkstra es:
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[]
El código en Python sería:
def dijkstra(self):
nodes = list(self.graph.nodes)
for i in nodes: #Set first values
dict_i = {}
for j in nodes:
if i == j:
dict_i[j] = 0
else:
dict_i[j] = float("inf")
self.distances[i] = dict_i
for oneNode in nodes: #Start algoritm
Q = []
for node in nodes: Q.append(node)
while len(Q) != 0:
v = 0
min = float("inf")
for node_q in Q:
if self.distances[oneNode][node_q] <= min:
min = self.distances[oneNode][node_q]
v = node_q
Q.remove(v)
neighbors = list(self.graph.neighbors(v))
for neighborV in neighbors:
w = self.graph[v][neighborV]['weight']
alt = self.distances[oneNode][v] + w
if alt < self.distances[oneNode][neighborV]:
self.distances[oneNode][neighborV] = alt
return self.distances
Debido a que el código original está en una clase en un archivo Python, nos referimos al grafo como self.graph y el resultado en un diccionario de Python como self.distances .
El código es más fácil de digerir que el código Matlab. Tener en cuenta que el algoritmo Dijkstra está diseñado para encontrar el camino más cerca de un nodo fuente a un nodo destino. Pero como en este ejercicio necesitamos calcular el camino más corto de todos los pares, entonces cojeremos uno por uno.
La obtención de los vecinos de un nodo como los pesos es mucho más fácil de encontrar que en Matlab pero la creación de un grafo es mucho más fácil en Matlab. Tenemos la función para generar un grafo:
def create_network(self, source, target, weight):
self.graph = nx.DiGraph()
count = len(source)
edges = []
for i in range(0, count):
edges.append( (source[i], target[i], weight[i]) )
self.graph.add_weighted_edges_from(edges)
return self.graph
Podemos entonces probar utilizando el siguiente código:
import matplotlib.pyplot as plt
import networkx as nx
import graph as g
import os
os.system('cls')
source = [1,2,2,2,3,4]
target = [2,1,3,4,4,3]
weight = [1,1,2,4,1,1]
G = g.graph()
G.create_network(source, target, weight)
print("Dijkstra\n")
G.dijkstra()
G.print_distances()
El código fuente puede ser descargado desde el repositorio de mi cuenta personal de GitHub:
https://github.com/arturoverbel/graph_python
El grafo de prueba sería:
Figura 1. Grafo generado con Python
Floyd Warshall
Pseudocódigo:
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
En Python:
def floyd_warshall(self):
nodes = list(self.graph.nodes)
for i in nodes:
dict_i = {}
for j in nodes:
if i == j:
dict_i[j] = 0
continue
try:
dict_i[j] = self.graph[i][j]['weight']
except:
dict_i[j] = float("inf")
self.distances[i] = dict_i
for i in nodes:
for j in nodes:
for k in nodes:
ij = self.distances[i][j]
ik = self.distances[i][k]
kj = self.distances[k][j]
if ij > ik + kj:
self.distances[i][j] = ik + kj
return self.distances
Para crear la primera versión de la matriz, el pseudocódigo utiliza dos ciclos para llenarlos con las aristas establecidas del grafo y los ceros ( tres ciclos si contamos rellenar con infinitos como en la primera linea) Este código crea la primera matriz con un solo ciclo y utliza una pequeña estrategía con la captura de excepciones, debido a que la librería de networkx no posee un método de verificación de aristas.
Los resultados para el grafo ejemplo tanto en Dijkstra como en Floyd-Warshall son exactamente iguales, podemos comprobarlos con el método para imprimir el diccionario resultado:
def print_distances(self):
printt = ""
for i in self.distances:
printt = printt + str(i) + ": \t"
for j in self.distances[i]:
printt = printt + str(self.distances[i][j]) + "\t"
printt = printt + "\n"
print("\n------------------------------------")
print(printt)
return
Los resultados:
Figura 2. Resultados
Comentarios