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

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()

Recommended Posts

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
[Examen d'ingénieur d'information de base] J'ai écrit l'algorithme de la méthode de division mutuelle euclidienne en Python.
Je souhaite utiliser Python dans l'environnement de pyenv + pipenv sous Windows 10
J'ai installé Pygame avec Python 3.5.1 dans l'environnement de pyenv sur OS X
[Exemple d'amélioration de Python] Apprentissage des bases de Python sur un site gratuit en 2 semaines
J'ai posé le problème de la séquence tribonatch en C ++ et le nombre d'appels de fonction lors de l'écriture avec une fonction de récurrence (python est également disponible)
Informations de base Écrire le problème d'algorithme de l'automne 2018 en Python
Implémentation de l'algorithme "Algorithm Picture Book" en Python3 (Heap Sort Edition)
Algorithme en Python (Dijkstra)
Implémentation de l'algorithme de "Algorithm Picture Book" en Python3 (Bubble Sort)
Problème de placement d'ambulance - Tiré du numéro d'octobre du magazine OR
Implémentation de l'algorithme «Algorithm Picture Book» en Python3 (tri sélectif)
Partie 1 J'ai écrit la réponse au problème de référence de l'écriture hors ligne en temps réel en Python
J'ai essayé "Implémentation d'un algorithme génétique (GA) en python pour résoudre le problème du voyageur de commerce (TSP)"