Implémentation de l'algorithme de Dijkstra en Python
J'ai implémenté Dijkstra's algorithmpour mes recherches sur un modèle économique, en utilisant Python. Dans mes recherches, j'étudie deux fonctions et les différences entre elles. Chaque fonction prend en entrée deux paramètres: F(a,b)et Z(a,b).
Chaque cellule de la matrice est définie comme: $$M[a][b]=|F(a,b)-Z(a,b)|$$
Le but de ceci est de trouver le chemin de la différence minimale entre les équations qui sera correct pour chaque entrée a
Les implémentations en ligne de l'algorithme de Dijkstra utilisaient toutes des arêtes pondérées alors que j'ai des sommets pondérés.
Pseudo-code:
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[]
Contribution:
- Tableau 2D où la valeur de chaque cellule est son poids
- tuple source (x, y)
Production:
matrice de distance où chaque cellule contient la distance de la source au sommet (i, j)
matrice précédente où chaque cellule contient son parent. En retraçant depuis (98,98), je peux trouver le chemin le plus court.
La mise en oeuvre:
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
Des opinions sur son exactitude?
Réponses
Votre code semble généralement correct, mais ignore srcet ne recherche que dans le sens positif. De plus, il peut être nettoyé et optimisé de manière significative.
Quelques remarques générales en premier:
- Utilisez des noms de variables complets dans le code qui expriment une signification / un but. Il n'y a pas de coût significatif à utiliser des noms significatifs, mais ils peuvent rendre le code beaucoup plus facile à digérer.
- Soyez conscient des fonctionnalités et des normes du langage hôte. Évitez de réutiliser les noms des fonctions intégrées (par exemple
min) et essayez de respecter les normes de style de codage . - Évitez à
numpymoins d'utiliser réellement ses fonctionnalités intégrées. L'utilisationnumpy.arraypour l'accès direct est généralement plus lente quelist/set/ ... car les valeurs sont converties en objets Python complets à chaque accès.
Ne faites pas d'hypothèses sur les caractéristiques de vos données. En particulier, évitez ceux-ci:
MAX_DISTANCE = 99999
RANGE_ARR = [x for x in range(1, 1001)]
Ceux-ci échouent pour les graphiques avec une distance> 99999 ou plus de 1000 éléments. Calculez-les pour votre entrée ou utilisez de vraies limites supérieures.
Puisque les nombres ont un "maximum" bien défini, nous pouvons l'utiliser en toute sécurité:
INFINITY = float('int')
Puisque l'entrée graphest une matrice nxn, nous pouvons simplement interroger sa taille.
# inside `def dijkstra(graph, source):`
indices = range(len(graph))
Commençons par vertex in Q with min dist[u]/ dijkstra_get_min. Votre algorithme est correct, mais nous pouvons exploiter le fait que la fonction intégrée de Python autorise mindéjà des pondérations personnalisées. Le for vertex in Q:devient l'argument principal de min, le if dist[vertex[0], vertex[1]] <= min:devient le poids key.
def dijkstra_get_min(vertices, distances):
return min(vertices, key=lambda vertex: distance[vertex[0]][vertex[1]])
L' Dijkstraalgorithme se compose de deux parties: l'initialisation et la recherche. Votre code devient plus clair si nous divisons ces deux parties - votre ligne dist[0][0] = 0est la transition de l'une à l'autre.
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
Le but de l'initialisation est que chaque point a la même valeur. Cela signifie que nous pouvons créer directement les matrices avec leur valeur finale. En outre, étant donné que l'algorithme n'utilise le « nœud précédent », on peut initialiser à un espace réservé pas cher.
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
Au lieu de suivre les nœuds visités sous forme de liste ( [..., ...]), nous utilisons un set ( {..., ...}). Un ensemble n'est pas ordonné et prend en charge les tests d'appartenance O (1), par rapport aux tests d'appartenance à la liste O (n). Cela le rend mieux adapté à la comptabilité des nœuds visités / non visités.
Pour parcourir le graphique, nous visiterons les voisins à plusieurs reprises. C'est un élément clé qui peut facilement être mal fait - à moins que l'implémentation Graph ne le fournisse, il peut être intéressant de l'implémenter explicitement.
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
]
Le cœur de l'algorithme reste logiquement le même: nous ajustons certains noms pour qu'ils soient plus parlants (par exemple u-> node, v-> neighbour). Nous utilisons l' neighboursexpression préparée au lieu de l'expression longue.
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
À ce stade, le code doit être à la fois plus rapide et plus facile à maintenir. Le défaut le plus flagrant que nous ayons encore est la gestion explicite des dimensions. Au lieu d'accéder manuellement à chaque dimension, il serait préférable que nous puissions accéder directement aux points.
# currently
distances[neighbour[0]][neighbour[1]]
# desirable
distances[neighbour]
Cela peut être "corrigé" en utilisant des dictionnaires ( {point: value, ...}) au lieu de listes imbriquées ( [[value, ...], ...]). Un inconvénient immédiat est que cela échange la mémoire pour la simplicité.
Cependant, il peut être utilisé pour réduire l'utilisation de la mémoire - les dictionnaires peuvent être naturellement rares, ce qui nous permet simplement de ne pas stocker des champs indéterminés. Comme tout nœud visité devient sans importance pour les distances, nous pouvons même éliminer les distancesnœuds déjà traités.
[x for x in range(1, 1001)]peut être écrit comme juste list(range(1, 1001)).
Ce serait bien de lui donner 1001un nom aussi.
De même, [0 for x in RANGE_ARR]peut être écrit comme [0] * len(RANGE_ARR). La multiplication de tout type de séquence par un entier répète les éléments de la séquence. En prime, d'après une analyse comparative rapide que je viens de faire, c'est aussi plus de 10 fois plus rapide:
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
Sachez cependant que vous ne devez pas l'utiliser lorsque le type d'élément est mutable (comme [[0]] * 5). La multiplication d'une séquence crée plusieurs références au même objet; il ne fait pas de copies.
Il semble que cela Qdevrait être un ensemble. Vous ne vous souciez pas de l'ordre, et la seule chose pour laquelle vous l'utilisez est de suivre l'appartenance à un ensemble. Les sets seront nettement plus rapides ici. Les deux seuls changements nécessaires sont:
Q = set()
. . .
Q.add((i, j))
Le seul changement que je peux voir dans cette évolution est dijkstra_get_minqu'il repose techniquement sur l'ordre de Q. Si deux éléments avec les mêmes valeurs minimales sont dans Q, votre algorithme sélectionne la dernière instance. Puisque les ensembles peuvent utiliser un ordre différent, cela peut changer le sommet qui est retourné.
Il semble que MAX_DISTANCEce soit un nombre arbitrairement élevé auquel tout le reste sera inférieur. Vous voudrez peut-être essayer d'utiliser np.infpour cela. En codant en dur la limite supérieure, vous risquez que le problème "grandisse" plus tard et dépasse potentiellement ce maximum; provoquant un comportement erroné.