Dijkstra's algorithm: I asked the problem of AOJ in Python based on the content of Kencho-san's article in the October issue of Software Design.

Solved problem

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

Source

• Note that the AOJ problem has a starting point specified
• In the ant book, the flag was used to check for updates, but Kenchon's method is to confirm if it is not updated (do not put it in the priority queue).
• Search from the vertex (the vertex with the shortest distance from the start) obtained by popping the priority queue.

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)

    #Queue the start vertex
    #[Shortest distance to the corresponding vertex (current time),Index of the corresponding vertex]
    que = [[0,s]]

    #Convert to priority queue
    heapq.heapify(que)

    while len(que) > 0:
        #Fetch the first element of the priority queue
        #v is the vertex number,d is the current shortest distance to the corresponding vertex
        p = heapq.heappop(que)
        v = p[1]
        d = p[0]

        #In software design, the following processing is required, but is it unnecessary?
        #I don't really understand the need
        #if d > dist[v]:
        #   continue

        #Calculate the distance for each vertex that can be reached from the corresponding vertex v
        for e in Graph[v]:
            #If the shortest distance cannot be updated, do nothing
            if dist[v] + e.w >= dist[e.to] :
                continue

            #The following is when the shortest distance can be updated

            #Push destination vertex information to the priority queue
            heapq.heappush(que,[dist[v] + e.w, e.to])

            #Update the shortest destination distance
            dist[e.to] = dist[v] + e.w

            #Remember the node before the destination
            #Not used for AOJ issues
            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))
        #AOJ problem is valid graph (http)://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_2_A）
        #Graph[b].append(Edge(a, w))

    Dijkstra(Graph, s)

main()