[GO] Méthode Dyxtra: j'ai posé le problème d'AOJ avec Python en me basant sur le contenu de l'article de M. Kencho dans le numéro d'octobre de Software Design

Problème résolu

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_2_A

La source

• Notez que le problème AOJ a un point de départ spécifié
• Dans Arimoto, un drapeau a été utilisé pour vérifier les mises à jour, mais la méthode de Kenchon est de confirmer s'il n'est pas mis à jour (ne le mettez pas dans la file d'attente prioritaire).
• Recherche à partir des sommets (les sommets avec la distance la plus courte depuis le début) obtenus en faisant sauter la file de priorité

import heapq
INF = 10**10

class Edge:
    to = -1
    w = -1
    def __init__(self, to, w):
        self.to = to
        self.w = w

def Dijkstra(Graph, s):
    dist = [INF] * len(Graph)
    dist[s] = 0

    prev = [-1] * len(Graph)

    #Mettre en file d'attente le sommet de départ
    #[Distance la plus courte au pic correspondant (heure actuelle),Index du sommet correspondant]
    que = [[0,s]]

    #Convertir en file d'attente prioritaire
    heapq.heapify(que)

    while len(que) > 0:
        #Récupérer le premier élément d'une file d'attente prioritaire
        #v est le numéro du sommet,d est la distance la plus courte actuelle par rapport au sommet correspondant
        p = heapq.heappop(que)
        v = p[1]
        d = p[0]

        #Dans la conception de logiciels, il y a le traitement suivant, mais est-ce inutile?
        #Je ne comprends pas vraiment le besoin
        #if d > dist[v]:
        #   continue

        #Calculer la distance pour chaque sommet qui peut être atteint à partir du sommet correspondant v
        for e in Graph[v]:
            #Si la distance la plus courte ne peut pas être mise à jour, ne faites rien
            if dist[v] + e.w >= dist[e.to] :
                continue

            #Voici quand la distance la plus courte peut être mise à jour

            #Transférer les informations de sommet de destination vers une file d'attente prioritaire
            heapq.heappush(que,[dist[v] + e.w, e.to])

            #Mettre à jour la distance de destination la plus courte
            dist[e.to] = dist[v] + e.w

            #Souvenez-vous du nœud avant la destination
            #Non utilisé pour les problèmes AOJ
            prev[e.to] = v

    for d in dist:
        if d == INF:
            print("INF")
        else:
            print(d)

    return

def main():
    n, m, s = map(int, input().split())
    Graph =  [[] for j in range(n)]
    for i in range(m):
        a, b, w = map(int, input().split())
        Graph[a].append(Edge(b, w))
        #Le problème AOJ est un graphe valide (http)://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_2_A）
        #Graph[b].append(Edge(a, w))

    Dijkstra(Graph, s)

main()