Implementación del algoritmo de Dijkstra en Python
Lo he implementado Dijkstra's algorithmpara mi investigación sobre un modelo económico, usando Python. En mi investigación, estoy investigando dos funciones y las diferencias entre ellas. Cada función toma como entrada dos parámetros: F(a,b)y Z(a,b).
Cada celda de la matriz se define como: $$M[a][b]=|F(a,b)-Z(a,b)|$$
El propósito de esto es encontrar la ruta de diferencia mínima entre las ecuaciones que será correcta para cada entrada. a
Todas las implementaciones en línea del algoritmo de Dijkstra usaban bordes ponderados, mientras que yo tenía vértices ponderados.
Pseudocódigo:
function Dijkstra(Graph, source):
create vertex set Q
for each vertex v in Graph:
dist[v] ← INFINITY
prev[v] ← UNDEFINED
add v to Q
dist[source] ← 0
while Q is not empty:
u ← vertex in Q with min dist[u]
remove u from Q
for each neighbor v of u: // only v that are still in Q
alt ← dist[u] + length(u, v)
if alt < dist[v]:
dist[v] ← alt
prev[v] ← u
return dist[], prev[]
Entrada:
- Matriz 2d donde el valor de cada celda es su peso
- tupla fuente (x, y)
Salida:
matriz de distancia donde cada celda contiene la distancia desde la fuente hasta el vértice (i, j)
matriz anterior donde cada celda contiene su padre. Rastreando desde (98,98) puedo encontrar el camino más corto.
Implementación:
MAX_DISTANCE = 99999
RANGE_ARR = [x for x in range(1, 1001)]
def dijkstra_get_min(Q, dist):
min = MAX_DISTANCE + 1
u = None
for vertex in Q:
if dist[vertex[0], vertex[1]] <= min:
min = dist[vertex[0], vertex[1]]
u = vertex
return u
def dijkstra(graph, src=(0, 0)):
dist = np.array([np.array([0 for x in RANGE_ARR], dtype=float) for y in RANGE_ARR])
prev = np.array([np.array([(0, 0) for x in RANGE_ARR], dtype='i,i') for y in RANGE_ARR])
Q = []
for i in RANGE_ARR_0:
for j in RANGE_ARR_0:
dist[i, j] = MAX_DISTANCE
prev[i, j] = (0, 0)
Q.append((i, j))
dist[0][0] = 0
while Q:
u = dijkstra_get_min(Q, dist)
Q.remove(u)
moves = [x for x in ( (u[0], u[1] + 1), (u[0] + 1, u[1]), (u[0] + 1, u[1] + 1) ) if x in Q]
for v in moves:
alt = dist[u[0]][u[1]] + graph[v[0]][v[1]]
if alt < dist[v[0]][v[1]]:
dist[v[0], v[1]] = alt
prev[v[0], v[1]] = u
return dist, prev
¿Alguna opinión sobre su corrección?
Respuestas
Su código parece correcto en general, pero ignora srcy solo busca en dirección positiva. Además, se puede limpiar y optimizar significativamente.
Primero, algunos comentarios generales:
- Use nombres completos de variables en el código que expresen significado / propósito. No hay un costo significativo por usar nombres significativos, pero pueden hacer que el código sea mucho más fácil de digerir.
- Tenga en cuenta las características y los estándares del idioma anfitrión. Evite reutilizar los nombres de las incorporaciones (por ejemplo
min) y trate de adherirse a los estándares de estilo de codificación . - Evítelo a
numpymenos que utilice sus funciones integradas. El usonumpy.arraypara acceso directo suele ser más lento quelist/set/ ... porque los valores se convierten en objetos de Python completos en cada acceso.
No haga suposiciones sobre las características de sus datos. En concreto, evite estos:
MAX_DISTANCE = 99999
RANGE_ARR = [x for x in range(1, 1001)]
Estos fallan para gráficos con distancia> 99999 o más de 1000 elementos. Calcúlelos para su entrada o use límites superiores verdaderos.
Dado que los números tienen un "máximo" bien definido, podemos usarlo con seguridad:
INFINITY = float('int')
Dado que la entrada graphes una matriz nxn, podemos consultar su tamaño.
# inside `def dijkstra(graph, source):`
indices = range(len(graph))
Comencemos con vertex in Q with min dist[u]/ dijkstra_get_min. Su algoritmo es correcto, pero podemos aprovechar que la función incorporada de Python minya permite pesos personalizados. El se for vertex in Q:convierte en el argumento principal de min, se if dist[vertex[0], vertex[1]] <= min:convierte en el peso key.
def dijkstra_get_min(vertices, distances):
return min(vertices, key=lambda vertex: distance[vertex[0]][vertex[1]])
El Dijkstraalgoritmo consta de dos partes: inicialización y búsqueda. Su código se vuelve más claro si dividimos estas dos partes: su línea dist[0][0] = 0es la transición de una a la otra.
def dijkstra(graph, src=(0, 0)):
# dist, prev, Q
distances, prev_nodes, unvisited = dijkstra_initial(len(graph))
# set starting point
distances[src[0]][src[1]] = 0
dijkstra_search(graph, distances, prev_nodes, unvisited)
return distances, prev_nodes
El propósito de la inicialización es que cada punto tenga el mismo valor. Esto significa que podemos crear directamente las matrices con su valor final. Además, dado que el algoritmo no utiliza el "nodo anterior", podemos inicializarlo en un marcador de posición económico.
def dijkstra_initial(size):
distances = [[INFINITY] * size for _ in range(size)]
prev_nodes = [[None] * size for _ in range(size)]
unvisited = {(x, y) for x in range(size) for y in range(size)}
# dist, prev, Q
return distances, prev_nodes, unvisited
En lugar de rastrear los nodos visitados como una lista ( [..., ...]), usamos un conjunto ( {..., ...}). Un conjunto no está ordenado y admite pruebas de membresía O (1), en comparación con las pruebas de membresía de la lista O (n). Esto lo hace más adecuado para la contabilidad de nodos visitados / no visitados.
Para buscar en el gráfico, visitaremos a los vecinos repetidamente. Esta es una parte clave que se puede hacer mal fácilmente: a menos que la implementación de Graph lo proporcione, puede valer la pena implementarlo explícitamente.
def neighbours(node):
x, y = node
return [
(x + x_offset, y + y_offset)
for x_offset in (-1, 0, 1)
for y_offset in (-1, 0, 1)
if not (x_offset == y_offset == 0) # reject node itself
]
El núcleo del algoritmo permanece lógicamente igual: ajustamos algunos nombres para que sean más hablados (por ejemplo, u-> node, v-> neighbour). Usamos la neighboursexpresión preparada en lugar de la larga.
def dijkstra_search(graph, distances, prev_nodes, unvisited):
while unvisited:
node = dijkstra_get_min(unvisited, dist)
unvisited.remove(node)
for neighbour in neighbours(node):
if neighbour not in unvisited:
continue
alt = distances[node[0]][node[1]] + graph[neighbour[0]][neighbour[1]]
if alt < distances[neighbour[0]][neighbour[1]]:
distances[neighbour[0]][neighbour[1]] = alt
prev_nodes[neighbour[0]][neighbour[1]] = node
En este punto, el código debería ser más rápido y más fácil de mantener. El defecto más evidente que todavía tenemos es el manejo explícito de las dimensiones. En lugar de acceder manualmente a cada dimensión, sería mejor si pudiéramos acceder directamente a los puntos.
# currently
distances[neighbour[0]][neighbour[1]]
# desirable
distances[neighbour]
Esto se puede "arreglar" usando diccionarios ( {point: value, ...}) en lugar de listas anidadas ( [[value, ...], ...]). Una desventaja inmediata es que esto cambia la memoria por la simplicidad.
Sin embargo, se puede utilizar para reducir realmente el uso de memoria: los diccionarios pueden ser naturalmente escasos, lo que nos permite simplemente no almacenar campos indeterminados. Dado que cualquier nodo visitado se vuelve irrelevante para las distancias, incluso podemos borrar los distancesnodos que ya están procesados.
[x for x in range(1, 1001)]se puede escribir como justo list(range(1, 1001)).
Sería bueno darle 1001un nombre a eso también.
Del mismo modo, [0 for x in RANGE_ARR]se puede escribir como [0] * len(RANGE_ARR). Multiplicar cualquier tipo de secuencia por un número entero repite los elementos dentro de la secuencia. Como beneficio adicional, de algunas evaluaciones comparativas rápidas que acabo de hacer, también es más de 10 veces más rápido:
from timeit import timeit
N = int(1e6)
TRIALS = int(1e3)
print(timeit(lambda: [0] * N, number=TRIALS), "seconds")
print(timeit(lambda: [0 for x in range(N)], number=TRIALS), "seconds")
2.9889957 seconds
38.1463017 seconds
Sin embargo, tenga en cuenta que no debe usar esto cuando el tipo de elemento es mutable (como [[0]] * 5). Multiplicar una secuencia crea múltiples referencias al mismo objeto; no hace copias.
Parece que Qdebería ser un conjunto. No le importa el orden, y lo único que lo usa es para rastrear la membresía de un conjunto. Los conjuntos serán significativamente más rápidos aquí. Los únicos dos cambios necesarios son:
Q = set()
. . .
Q.add((i, j))
El único cambio que puedo ver que está haciendo es que dijkstra_get_mintécnicamente se basa en el orden de Q. Si dos elementos con los mismos valores mínimos están en Q, su algoritmo elige la última instancia. Dado que los conjuntos pueden usar un orden diferente, esto puede cambiar qué vértice se devuelve.
Parece que MAX_DISTANCEestá destinado a ser un número arbitrariamente grande al que todo lo demás será menor. Es posible que desee intentar usar np.infpara eso. Al codificar el límite superior, corre el riesgo de que el problema "crezca" más adelante y potencialmente supere ese máximo; causando un comportamiento erróneo.