다익스트라 알고리즘

1. 시작 노드 설정

2. 최단 거리 테이블 초기화 int(1e9)

3. 방문하지 않은 노드 중 거리가 가장 짧은 노드 선택

4. 이 노드를 통해 다른 노드로 이동하는 비용을 계산하여 최단 거리 테이블을 업데이트합니다.

5. 위 프로세스의 3단계와 4단계를 반복합니다.

각 단계에서 ‘미방문 노드 중 거리가 가장 짧은 노드를 선택’하기 위해 각 단계에서 1차원 리스트의 모든 요소를 ​​확인한다(순차적 탐색).

방법 1> Dijkstra 알고리즘의 단순 소스 코드 / 시간 복잡도: O(V Squared)

import sys
input=sys.stdin.readline
INF=int(1e9)
#노드 개수, 간선의 개수 입력받음
n,m=map(int, input().split())
#시작 노드 번호
start=int(input())
#각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트를 만들기
graph=(() for i in range(n+1))
#방문한 적이 있는지 체크하는 리스트
visited=(False)*(n+1)
#최단거리 테이블을 모두 무한으로 초기화
distance=(INF)*(n+1)
#모든 간선 정보 입력받기
for _ in range(m):
    #a번 노드에서 b번 노드로 가는 비용이 c
    a,b,c=map(int, input().split())
    graph(a).append((b,c))

#방문하지 않은 노드 중에서 가장 최단 거리가 짧은 노드의 반환
def get_smallest_node():
    min_value=INF
    index=0
    for i in range(1, n+1):
        if distance(i) < min_value and not visited(i):
            min_value=distance(i)
            index=i
    return index
def dijkstra(start):
    #시작 노드에 대해서 초기화
    distance(start)=0
    visited(start)=True

    for j in graph(start):
        distance(j(0))=j(1)
    # 시작 노드를 제외한 전체 n-1개의 노드에 대해 반복
    for i in range(n-1):
        now=get_smallest_node()
        visited(now)=True
        for j in graph(now):
            cost=distance(now)+j(1)
            #현재 노드를 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우
            if cost<distance(j(0)):
                
                distance(j(0))=cost
dijkstra(start)
#모든 노드로 가기 위한 최단거리 출력
for i in range(1, n+1):
    if distance(i)==INF:
        print("INFINITY")
    else:
        print(distance(i))

방법 2> 향상된 다익스트라 알고리즘 / 시간 복잡도 O(ElogV)