[알고리즘 with 파이썬] - 최단거리(다익스트라, 플로이드 워셜)

참고서적: 이것이 코딩테스트다 with 파이썬

 

graph를 이용해 최단거리를 이용하는 방법이다. 

다익스트라는 특정 노드에서 다른 노드로 가는 최단거리를 구하는 방법이고, 시간복잡도는 짜는 방법에 따라 O(V^2), O(ElongV)다. (V는 간선의 개수, E는 간선의 개수) 간선은 모두 양수여야 한다.

 

플로이드 워셜은 모든 노드에서 모든 노드로 가는 최단거리를 구하는 방법이고, DP를 이용해 구한다. 시간복잡도는 O(V^3)이다. 음수 가중치 간선이 있어도 수행할 수 있다.

 

 

다익스트라 알고리즘

먼저 거리를 무한으로 초기화하고, 출발노드부터 시작해 방문하지 않은 노드를 선택해 인접한 다른 노드로 가는 비용을 체크한다. 이때 해당 노드를 거쳐 다른 노드로 가는 거리가 다른 노드의 기존 거리보다 작다면 갱신한다.

######## 입력부 #########
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 = map(int,input().split())
    graph[a].append((b,c))              # a번 노드에서 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         # 시작노드 초기화(거리는 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 수정 
                distance[j[0]] = cost

# 다익스트라 알고리즘수행
dijkstra(start)

######## 출력부 #########
    # 최단거리 출력하기(각 노드로 가기 위한 최단거리 출력) 
for i in range(1, n+1):
    if distance[i] == INF:
        print("INFINITY")
    else:
        print(distance[i])

 

우선순위 큐를 이용한 개선된 다익스트라 알고리즘

(거리, 노드) 튜플을 우선순위 큐에 넣는다. 이렇게 되면 큐에서 원소를 꺼낼 때 거리가 가장 작은 튜플을 꺼내게 된다.

이때 해당 노드를 이미 처리한 적이 있다면 무시하고, 아직 처리하지 않은 노드가 있다면 처리한다(해당 노드에서 다른 노드까지 거리를 체크하고, 해당 노드를 거쳐 다른 노드로 가는 거리가 다른 노드의 기존 거리보다 작다면 갱신한다)

######## 입력부 #########
import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)  # 무한 의미, 10억으로 설정

n, m = map(int, input().split())    # 노드 개수, 간선 개수 입력받기
start = int(input())                # 시작노드 번호 입력받기
graph = [[] for i in range(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 dijkstra(start):
    q = []
    heapq.heappush(q, (0, start))   # 시작 노드로 가기 위한 최단 경로는 0으로 설정해 큐에 삽입
    distance[start] = 0
    while q:                            # 큐가 비어있지 않다면
        dist, now = heapq.heappop(q)    # 가장 최단거리가 짧은 노드에 대한 정보 꺼내기
        if distance[now] < dist:        # 현재 노드가 이미 처리된 적이 있는 노드라면 무시
            continue
        for i in graph[now]:            # 현재 노드와 연결된 다른 인접한 노드들 확인
            cost = dist + i[1]          
            if cost < distance[i[0]]:   # 현재 노드를 거쳐 다른 노드로 이동하는 거리가 더 짧은 경우
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))  

######## 출력부 #########
dijkstra(start)

for i in range(1, n+1):
    if distance[i] == INF:
        print("INFINITY")
    else:
        print(distance[i])

 

플로이드 워셜 알고리즘

각 노드 k마다, a에서 b로 가는 거리와  a -> k -> b 로 가는 거리 중 작은 값을 dp로 갱신한다.  

############# 입력부 ##############
INF = int(1e9)

# 노드와 간선의 개수 입력받기
n = int(input())
m = int(input())

# 2차원 리스트를 만들고, 모든 값을 무한으로 초기화
graph = [[INF]*(n+1) for _ in range(n+1)]   

# 자기 자신에서 자신으로 가는 비용은 0으로 초기화
for a in range(1, n+1):
    for b in range(1, n+1):
        if a == b:
            graph[a][b] = 0

# 각 간선에 대한 정보를 입력받아 그 값으로 초기화
for _ in range(m):
    a, b, c = map(int, input().split()) # a에서 b로 가는 비용이 c
	if graph[a][b] > c:
            graph[a][b] = c

############# 수행부 ##############
# 점화식에 따라 플로이드 워셜 알고리즘 수행
for k in range(1, n+1):
    for a in range(1, n+1):
        for b in range(1, n+1):
            graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])
    

############# 출력부 ##############
# 수행된 결과 출력
for a in range(1, n+1):
    for b in range(1, n+1):
        if graph[a][b] == INF:               
            print("INFINITY", end = " ")    # 도달할 수 없는 경우
        else:                           
            print(graph[a][b], end = " ")   # 도달할 수 있는 경우