[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. image.png (Source: De la page Youtube ci-dessus)

Recommended Posts

[Python3] Méthode Dikstra avec 14 lignes
Implémentation de la méthode Dyxtra par python
Algorithme en Python (Dijkstra)
Trouvez l'itinéraire le plus court avec l'algorithme de Python Dijkstra
Implémenter l'algorithme de Dijkstra en python
Algorithme Python
FizzBuzz en Python3
Grattage avec Python
Statistiques avec python
Mémorandum Python (algorithme)
Grattage avec Python
Livre Ali en python: méthode Dyxtra Sec.2-5
Python avec Go
Twilio avec Python
Rechercher le labyrinthe avec l'algorithme python A *
Jouez avec 2016-Python
Testé avec Python
avec syntaxe (Python)
Bingo avec python
Zundokokiyoshi avec python
Développons un algorithme d'investissement avec Python 1
Excel avec Python
Micro-ordinateur avec Python
Cast avec python
Calculer l'itinéraire le plus court d'un graphe avec la méthode Dyxtra et Python
Résolvez le problème du sac à dos Python avec l'algorithme glouton
Communication série avec Python
Zip, décompressez avec python
Django 1.11 a démarré avec Python3.6
Jugement des nombres premiers avec Python
Python avec eclipse + PyDev.
Communication de socket avec Python
Analyse de données avec python 2
Grattage en Python (préparation)
Algorithme A * (édition Python)
Essayez de gratter avec Python.
Apprendre Python avec ChemTHEATER 03
Recherche séquentielle avec Python
"Orienté objet" appris avec python
Exécutez Python avec VBA
Manipuler yaml avec python
Résolvez AtCoder 167 avec python
Communication série avec python
[Python] Utiliser JSON avec Python