[Python3] Méthode Dikstra avec 14 lignes
Hier, j'ai implémenté la Prime factorisation en 14 lignes, mais aujourd'hui j'ai implémenté la méthode Dyxtra en 14 lignes en utilisant le tas. En 14 lignes à partir du haut.
dijkstra.py
from heapq import heappush, heappop
def dijkstra(vertices_num, edges, src):
dist = [float('inf')] * vertices_num
heap = [(0, src)]
while len(heap):
d, from_ = heappop(heap)
if d < dist[from_]:
dist[from_] = d
for _, to, cost in filter(lambda e: e[0]==from_, edges):
heappush(heap, (min(dist[to], dist[from_] + cost), to))
return dist
if __name__ == '__main__':
answer = dijkstra(
8,
[
(0, 1, 5), (0, 2, 4), (0, 3, 1), (1, 4, 2), (1, 0, 5), (2, 0, 4), (2, 3, 2), (2, 4, 5),
(2, 5, 6), (3, 0, 1), (3, 2, 2), (4, 1, 2), (4, 2, 5), (4, 6, 1), (4, 7, 3), (5, 2, 6),
(5, 7, 2), (6, 4, 1), (6, 7, 4), (7, 4, 3), (7, 5, 2), (7, 6, 4)
], 0
)
print(answer) # [0, 5, 3, 1, 7, 9, 8, 10]
Le premier argument est le nombre de sommets, le deuxième argument est une liste de (from_, to, cost) et le troisième argument est l'index du point de départ. La valeur de retour renvoie la distance la plus courte entre le point de départ et chaque sommet.
référence
https://www.youtube.com/watch?v=X1AsMlJdiok
En ce qui concerne la méthode Dyxtra, l'explication de cette vidéo était très simple à comprendre, j'ai donc fait un cas de test en référence aux problèmes traités. Les lettres rouges sont les index de chaque sommet.
(Source: De la page Youtube ci-dessus)
Recommended Posts