알고리즘 기초 - 최단 경로(플로이드-워셜, 벨만-포드)

반응형

이번 포스팅에서는 플로이드-워셜, 벨만-포드 알고리즘에 대해 설명하겠습니다.

 

- 플로이드 워셜 알고리즘(Floyd-Warshall)

모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 구하고 싶을 떄 사용하는 알고리즘입니다. 각 단계마다 해당 노드를 거쳐가는 경우를 고려해야 합니다. 예를 들어, 1번 노드에 있을때는 1번 노드를 거쳐가는 모든 경우를 고려하면 됩니다. A->1->B인 경우의 비용을 확인 후 최단 거리를 갱신해주어야 합니다. 이를 점화식으로 나타내면, 아래와 같습니다!

min 함수를 사용해 바로 이동하는 거리와 특정한 노드를 거쳐서 이동하는 거리를  이용해 짧은 것으로 갱신될 수 있도록 해줍니다.

다익스트라 알고리즘은 매번 최단 거리를 검색하지만 이 알고리즘은 그럴 필요가 없다는 점이 장점입니다.

​

step 0)

step 1) 1번 노드를 거쳐가는 경우

D23, D24, D32, D34, D42, D43에 대해서만 갱신합니다.

​

step 2)2번 노드를 거쳐가는 경우

이후 step) 이와 같은 과정을 3번 노드, 4번 노드에 대해서도 실행합니다.

최종 리스트의 값은 아래와 같이 저장됩니다.

- 코드(링크)

GitHub - jgyy4775/python-for-coding-test: [한빛미디어] "이것이 취업을 위한 코딩 테스트다 with 파이썬" 전

구현은 삼중 for문을 이용합니다.

INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정합니다.

# 노드의 개수 및 간선의 개수를 입력받습니다.
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라고 설정해줍니다.
    a, b, c = map(int, input().split())
    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):
        # 도달할 수 없는 경우, 무한(INFINITY)이라고 출력합니다.
        if graph[a][b] == 1e9:
            print("INFINITY", end=" ")
        # 도달할 수 있는 경우 거리를 출력합니다.
        else:
            print(graph[a][b], end=" ")
    print()

 

 

- 벨만-포드 알고리즘(Bellman-Ford)

이전의 다익스트라 알고리즘은 간선의 가중치가 모두 양수여야만 최단거리 판별시 사용할 수 있는 알고리즘입니다. 벨만 포드 알고리즘은 음의 간선(음의 가중치)이 포함되어 있을 때도 최단거리를 찾을 수 있도록 한 알고리즘입니다. 만약 음의 간선이 포함되어 있는 그래프에 다익스트라 알고리즘을 적용하면 어떻게 될까요? 무한루프에 빠질 수도 있고 최단거리를 찾을 수 없게 됩니다.(해당 내용에 대한 자세한 설명을 이곳을 참고해주세요!)

알고리즘의 동작과정은 아래 순서로 이루어집니다.

1) 시작 정점을 결정합니다.

2) 시작 정점에서 다른 정점까지의 거리 값을 무한대로 초기화합니다.

3) 정점들을 차례로 탐색하며 기존에 저장된 인접 정점까지의 거리보다 작은 값이 나오면 갱신해줍니다.

4) 위 과정을 n-1번 반복합니다.(자기 자신 노드를 제외하고 나머지를 다 탐색해야하기 때문입니다.)

5) 이 과정을 마치고 난 후 한번 더 반복합니다.

=> 5번 과정 후 갱신되는 값이 생긴기는 경우가 있습니다. 이는 무엇을 의미하는 것일까요?
음수 사이클이 존재하는 그래프이므로 최단 거리를 구할 수 없을 뿐만 아니라, 무한 루프에 빠지게 되는 경우를 말합니다.

 

아래와 같은 그래프가 있고 1번부터 탐색을 시작합니다.

step 1) 1번 노드 탐색 후 이웃 노드까지의 거리 값을 갱신합니다.

step 2) 2번 노드를 탐색하고, 이때 1->4로 바로 가는 것 보다 1->2->4를 거쳐가는 것이 -5로 값이 더 작으므로 갱신됩니다.

step 3) 3번 노드를 탐색하고, 이떄는 원래 저장되어 있던 -5보다 1->3->4를 거쳐 가는게 더 큰 비용이 들기 때문에 갱신되지 않습니다.

step 4) 4번 노드를 탐색하고, 5번 노드까지 가는 최단 경로가 갱신됩니다.

step 5) 5번 노드를 탐색합니다.

모든 노드를 한번 씩 탐색한 후 1번 노드에서 다른 노드까지의 최단 거리 값은 [0, -4, 5, -5, 1]입니다. 이 과정을 한번 더 반복해도 값이 갱신되지 않습니다. 그러므로 위 그래프는 사이클이 없는 그래프입니다.

​

-코드

import sys
import collections
input = sys.stdin.readline
INF = int(1e9)

n, m = map(int, input().split()) # 노드 수, 간선 수를 입력받습니다.
edges = [] # 모든 간선에 대한 정보를 담는 리스트를 생성합니다.
dist = [INF] * (n+1) # 최단 거리 테이블을 모두 무한으로 초기화합니다.

# 그래프를 생성합니다.
for _ in range(m):
    u, v, w = map(int, input().split()) # 노드, 인접 노드, 가중치를 입력받습니다.
    edges.append((u, v, w))

# 벨만 포드 알고리즘
def bf(start):
    dist[start] = 0 # 시작 노드에 대해서 거리를 0으로 초기화합니다.
    for i in range(n): # 정점 수만큼 반복해줍니다.
        for j in range(m): # 매 반복 마다 모든 간선을 확인합니다.
            node = edges[j][0] # 현재 노드를 받아옵니다.
            next_node = edges[j][1] # 다음 노드를 받아옵니다.
            cost = edges[j][2] # 가중치를 받아옵니다.
            
            # 현재 간선을 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우에는 아래 과정을 거칩니다.
            if dist[node] != INF and dist[next_node] > dist[node] + cost:
                dist[next_node] = dist[node] + cost
                
                # n번째 라운드에서도 값이 갱신된다면 음수 사이클이 존재한다는 의미입니다.
                if i == n-1:
                    return True
    return False

# 벨만 포드 알고리즘 수행합니다.
negative_cycle = bf(1)

if negative_cycle:
    print('-1')
else:
    # 1번 노드를 제외한 다른 모든 노드로 가기 위한 최단 거리를 출력합니ㅏㄷ.
    for i in range(2, n+1):
        if dist[i] == INF: # 도달할 수 없는 경우 -1을 출력합니다.
            print('-1')
        else: # 도달할 수 있는 경우 거리를 출력합니다.
            print(dist[i])