Algorithme en Python (Dijkstra)

introduction

J'aimerais étudier le contenu de la bibliothèque, que je n'avais collé que jusqu'à présent, petit à petit. La raison pour laquelle j'ai écrit cet article est que je voudrais confirmer mes pensées et donner des conseils, alors veuillez commenter! (Surtout l'accélération, le montant du calcul)

Objectif

Trouvez la distance la plus courte d'un point de départ à un autre pour un graphique sans arêtes de coût négatives. (Itinéraire le plus court au point de départ unique)

principe

Prenons le cas où le nombre de sommets dans le graphique est $ V $ et le nombre de côtés est $ E $. Tout d'abord, préparez deux listes. L'un consiste à enregistrer la distance la plus courte depuis le point de départ et l'autre à enregistrer si l'itinéraire le plus court a été déterminé. (Il semble qu'il puisse être combiné en un seul, mais c'est la même chose que pour le comprendre.) Ici, la distance à votre propre point est fixée à 0, et la distance aux autres points est INF. Préparez une file d'attente prioritaire pour récupérer la valeur minimale du coût de la périphérie. Ensuite, le côté s'étendant à partir de son propre point est placé dans la file d'attente prioritaire. À ce moment, ** la destination du côté avec le coût minimum ne sera pas moins coûteuse via d'autres côtés **. Parce que le coût est non négatif, ce sera un détour. Par conséquent, le côté avec le coût minimum est retiré et la distance la plus courte jusqu'au sommet de cette destination est déterminée. De plus, le côté partant de ce sommet est également mis dans la file de priorité de la même manière. La distance est ** la distance à ce sommet + le coût du côté **. Ici, puisque le côté ayant la destination pour laquelle la distance la plus courte est fixée n'est pas lié à la distance la plus courte, la quantité de calcul devient plus légère si elle n'est pas incluse. Répétez le processus ci-dessus jusqu'à ce que toutes les distances les plus courtes soient déterminées. (Dans l'implémentation, la file d'attente prioritaire est vide)

la mise en oeuvre

import heapq
def dijkstra(s):
    #La distance la plus courte entre le point de départ et chaque sommet
    d = [float('inf')]*n
    d[s] = 0
    #Si chaque sommet a été visité
    used = [False]*n
    used[s] = True
    #Tas pour enregistrer la distance temporaire
    que = []
    for e in g[s]:
        heapq.heappush(que, e)
    while que:
        u, v = heapq.heappop(que)
        if used[v]:
            continue
        d[v] = u
        used[v] = True
        for e in g[v]:
            if not used[e[1]]:
                heapq.heappush(que, [e[0] + d[v], e[1]])
    return d

contribution

n = 4
g = [[[1, 1], [4, 2]], [[1, 0], [2, 2], [5, 3]], [[4, 0], [2, 1], [1, 3]], [[1, 2], [5, 1]]] #Liste adjacente
print(dijkstra(0))

production

[0, 1, 3, 4]

Analyse de calcul

L'ajout à la file d'attente prioritaire est de $ O (E) $ selon le nombre de côtés. La taille de la file d'attente prioritaire est proportionnelle à $ V $ en n'incluant pas les côtés sauf s'ils sont la distance la plus courte, donc chaque opération est $ O (logV) $. Par conséquent, le montant du calcul est de O $ (ElogV) $.

Question

Je me suis demandé si la taille de la file d'attente prioritaire était proportionnelle au nombre de côtés $ E $, mais j'étais un peu réticent à l'élaguer proportionnellement à $ V $. Si vous l'écrivez concrètement, vous pouvez voir qu'il n'atteindra jamais $ E $, mais j'aimerais savoir s'il peut être facilement exprimé par une formule mathématique. En premier lieu, lorsque le côté est étiré entre tous les sommets, il devient $ E∝V ^ 2 $, ce qui est pire que les autres algorithmes $ O (V ^ 2) $, donc je ne pense pas qu'il soit nécessaire d'y penser!

Exemple concret

L'exemple ci-dessus. Nous sélectionnerons et mettrons à jour celui avec le coût le plus bas parmi les sommets accessibles.

en conclusion

Je voudrais continuer à le mettre à jour sous forme de mémorandum. Je suis plus motivé car les articles sont parfois utilisés comme références.

Les références

[Livre du défi du concours de programmation](https://www.amazon.co.jp/%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F% E3% 83% B3% E3% 82% B0% E3% 82% B3% E3% 83% B3% E3% 83% 86% E3% 82% B9% E3% 83% 88% E3% 83% 81% E3% 83% A3% E3% 83% AC% E3% 83% B3% E3% 82% B8% E3% 83% 96% E3% 83% 83% E3% 82% AF-% E7% AC% AC2% E7% 89 % 88-% EF% BD% 9E% E5% 95% 8F% E9% A1% 8C% E8% A7% A3% E6% B1% BA% E3% 81% AE% E3% 82% A2% E3% 83% AB% E3% 82% B4% E3% 83% AA% E3% 82% BA% E3% 83% A0% E6% B4% BB% E7% 94% A8% E5% 8A% 9B% E3% 81% A8% E3% 82% B3% E3% 83% BC% E3% 83% 87% E3% 82% A3% E3% 83% B3% E3% 82% B0% E3% 83% 86% E3% 82% AF% E3% 83% 8B% E3% 83% 83% E3% 82% AF% E3% 82% 92% E9% 8D% 9B% E3% 81% 88% E3% 82% 8B% EF% BD% 9E-% E7% A7 % 8B% E8% 91% 89-% E6% 8B% 93% E5% 93% 89-ebook / dp / B00CY9256C) [Blog de Juppy](https://juppy.hatenablog.com/entry/2019/02/18/%E8%9F%BB%E6%9C%AC_python_%E3%83%97%E3%83%A9%E3 % 82% A4% E3% 82% AA% E3% 83% AA% E3% 83% 86% E3% 82% A3% E3% 82% AD% E3% 83% A5% E3% 83% BC% 28heapq% 29 % E3% 82% 92% E7% 94% A8% E3% 81% 84% E3% 81% 9F% E3% 83% 97% E3% 83% AA% E3% 83% A0% E6% B3% 95)