다익스트라 알고리즘(Dijkstra's Algorithm) 구현 (python)

참고:
[이것이 코딩 테스트다 with Python] 30강 다익스트라 최단 경로 알고리즘

최단 거리 알고리즘 대표 3가지

• 다익스트라 알고리즘(Dijkstra's Algorithm):
  한 노드로부터 다른 모든 노드까지의 최단 경로를 찾을 때 사용되며, 가중치가 양수인 경우에 효과적이다.

• 벨만-포드 알고리즘(Bellman-Ford Algorithm):
  다익스트라 알고리즘과 유사하지만, 가중치가 음수인 간선이 있을 경우에도 사용할 수 있다.

• 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm):
  모든 노드 쌍 사이의 최단 경로를 찾는 데 사용된다.
  
  

다익스트라 알고리즘(Dijkstra's Algorithm) 기본 과정

1. 출발 노드 설정
2. 최단 거리 테이블을 초기화(자기자신은 0, 그 외는 무한대)
3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택
4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 계산
5. 위 과정에서 3번, 4번을 반복

(방문한 노드는 이미 최단 거리가 구해진 것으로 보면 된다.)

python

import sys
input = sys.stdin.readline
INF = int(1e9)  # 무한을 의미하는 값으로 10억 설정

"""
기본 세팅
"""
# n:노드개수, m:간선개수
n, m = map(int, input().split())

# 시작 노드 번호
start = int(input())

# 각 노드별 연결되어 있는 노드에 대한 정보
graph = [[] for _ in range(n + 1)]

# 해당 노드를 방문한 적이 있는지 확인하는 목적의 리스트 (False로 세팅)
visited = [False] * (n + 1)

# 최단 거리 리스트 (무한으로 세팅)
distance = [INF] * (n + 1)

"""
모든 간선 정보 받기
"""
for _ in range(m):
    a, b, c = map(int, input().split())
    # a -> b 비용이 c 라는 의미
    graph[a].append((b, c))


"""
방문하지 않은 노드 중, 가장 최소 비용인 노드 구하기
"""
def get_smallest_node():
    min_value = INF

    index = 0
    for node in range(1, n + 1):
        if not visited[node] and distance[node] < min_value:
            min_value = distance[node]
            index = node

    return index


"""
다익스트라 알고리즘 
- 최단 경로 구하기. 매 순간 가장 최적의 값을 구하기 때문에 그리디 분류에 속함.
- 간선 비용이 음의 값이면 안됨. 간선은 양방향, 단방향 상관 없음
- 정해진 하나의 노드로부터, 다른 노드(=정해진 특정 노드가 아니어도 됨)까지의 최단 경로 구할 때 용이
"""
def dijkstra(start):
    # 시작 노드 설정
    visited[start] = True
    distance[start] = 0

    for i in graph[start]:
        distance[i[0]] = i[1]

    # 시작 노드 제외한 전체 n - 1개의 노드에 대해서 반복
    for _ in range(n - 1):
        # 현재 최단 거리가 가장 짧은 노드를 꺼냄
        node = get_smallest_node()

        # 방문 처리
        visited[node] = True

        # 현재 노드와 연결된 다른 노드 확인
        for connect_node, cost in graph[node]:
            # 현재 노드를 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우 갱신
            if distance[connect_node] > distance[node] + cost:
                distance[connect_node] = distance[node] + cost


dijkstra(start)


for i in range(1, n + 1):
    print(f"{start} -> {i} : {distance[i]}")

입력값

6 10
1
1 2 2
1 3 5
1 4 1
2 4 2
2 3 3
3 2 3
4 3 3
4 5 1
5 3 1
5 6 2

출력값 (노드 1로부터 다른 노드로까지의 최단 거리)

1 -> 1 : 0
1 -> 2 : 2
1 -> 3 : 3
1 -> 4 : 1
1 -> 5 : 2
1 -> 6 : 4