최단경로

최단 경로(Shortest Path) 알고리즘 이란?

말 그대로 가장 짧은 경로를 찾는 알고리즘이다. 

• 한 지점에서 다른 특정 지점까지의 최단 경로를 구해야하는 경우.
• 한 지점에서 다른 모든 지점까지의 최단 경로를 구해야하는 경우.
• 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야하는 경우 등

다양한 사례에서 사용하며 최단 경로 알고리즘은 보통 그래프로 표현한다.

각 '지점'은 그래프에서 '노드'로 표현되고, 지점 간 연결된 도로는 그래프에서 '간선'으로 표현된다.

 

다익스트라 알고리즘

특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산하는 알고리즘.

음의 간선이 존재하지 않을 때 정상적으로 동작한다.

현실 세계의 도로(간선)은 음의 간선으로 표현되지 않는다.

그리디 알고리즘으로 분류 된다, 매 상황에서 가장 비용이 적은 노드를 선택해 임의의 과정을 반복하기 때문.

알고리즘 동작과정

1. 출발 노드를 설정한다.
2. 최단 거리 테이블을 초기화 한다.
3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다.
4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.
5. 3-4를 반복한다.

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())
    # a번 노드에서 b번 노드로 가는 비용이 c
    graph[a].append((b, c))


# 방문하지 않은 노드 중에서, 가장 최단 거리가 짧은 노드를 반환하는 function
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):
    # start node reset

    distance[start]=0
    visited[start] = True
    for j in graph[start]:
        distance[j[0]]=j[1]
        #처음 시작 위치와 인접한 노드들 거리 값 지정

    #시작 노드를 제외한 전체 n01개의 노드에 대해서 반복
    for i in range(n-1):
        # 현재 최단 거리가 가장 짧은 노드를 꺼내서, 방문 처리
        now = get_smallest_node()
        visited[now] = True
        # 현재 노드와 연결된 다른 노드를 확인
        for k in graph[now]:
            cost  = distance[now]+k[1]
            # 현재 노드를 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우
            if cost < distance[k[0]]:
                distance[k[0]]=cost
dijkstra(start)

#모든 노드로 가기 위한 최단 거리를 출력

for i in range(1,n+1):
    # 도달할 수 없는 경우 INF 출력
    if distance[i] == INF:
        print('infinity')
    else:
        print(distance[i])

시간복잡도 O(V^2) 총 O(V)번에 걸쳐서 최단 거리가 가장 짧은 노드를 매번 선형 탐색하고 현재 노드와 연결된 노드를 매번 일일이 확인 하기 때문.

 

import heapq
import sys

global INF


def dijkstra(start):
    que = list()
    heapq.heappush(que, (0, start))
    distance[start] = 0
    while que:  # 큐가 비어있지 않는동안
        # 가장 최단 거리가 짧은 노드에 대한 정보 꺼내기
        dist, now = heapq.heappop(que)
        # 현재 노드가 이미 처리된 적이 있는 노드라면 무시
        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(que, (cost, i[0]))


if __name__ == '__main__':
    input = sys.stdin.readline
    INF = int(1e9)

    #node, edge
    n,m = map(int,input().split())
    #start node
    start = int(input())
    #empty list by node to node
    graph = [[] for i in range(n+1)]
    #min-value distance list
    distance = [INF]*(n+1)

    for _ in range(m):
        a, b, c = map(int,input().split())
        # a node to b / cost = c
        graph[a].append((b,c))

    dijkstra(start)

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

개선된 다익스트라 알고리즘

O(ElogV) 시간복잡도를 보장하는 알고리즘, E는 간선의 개수, V는 노드의 개수

선형탐색으로 가장 짧은 노드를 찾는 것이 아닌 HEAP 자료구조를 사용하여 찾는 알고리즘.

 

한번 처리된 노드에 대해서 다시 처리 하지 않으므로 더 빠를 수 있다.

큐에서 하나씩 꺼내 검사하는 while은 노드의 개수 V이상의 횟수로 반복되지 않는다.

V번 반복될 때 마다 각각 자신과 연결된 간선들을 모두 확인한다. 

특정 노드까지의 최단 거리에 대한 정보를 힙에 담아서 처리한다 이때 걸리는 시간은 선형시간이 아닌 로그시간.

 

힙(HEAP)?

우선순위 큐(Priority Queue)를 구현하기위한 자료구조 중 하나.

우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제한다.

즉 데이터를 우선순위에 따라 처리하고 싶을 때 사용한다. 데이터를 key와 value로 구성되어 있으면 key값이 우선순위 값이 되는 것이다. 내부적으로 최소 힙 (min heap)이나 최대 힙 (max heap)을 이용한다. 최소 힙을 이용하는 경우 '값이 낮은 데이터 부터 삭제된다' 최대 힙은 반대의 경우이다.

최소 힙을 최대 힙처럼 사용하기 위해 일부러 우선순위에 해당하는 값에 음수 부호를 붙여 넣었다가 나중에 꺼낸 다음 다시 부호를 붙여 원래의 값으로 돌리는 방식을 사용할 수 있다.

 

시작노드로부터 가장 거리가 짧은 노드 순서대로 큐에서 나올 수 있도록 하면된다.

 

플로이드 워셜 알고리즘

모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우 사용하는 알고리즘.

 

다익스트라는 단계마다 최단 거리를 가지는 노드를 하나씩 반복적으로 선택하고 해낭 노드를 거쳐 가는 경로를 확인하며, 최단 거리 테이블을 갱신하는 방식으로 동작한다.

 

플로이드 워셜 또한 단계마다 거쳐 가는 노드를 기준으로 알고리즘을 수행한다. 하지만 매번 방문 하지 않은 노드 중에서 최단 거리를 갖는 노드를 찾을 필요가 없다는 점이 다르다.

 

노드의 개수가 N개 일때, 알고리즘 상으로 N번의 단계를 수행하며, 단계마다 O(N^2)의 연산을 통해 현재노드를 거쳐가는 모든 경로를 고려한다. 총 시간 복잡도는 O(N^3)이다.

 

다익스트라 알고리즘은 출발 노드가 1개 이므로 다른 모든 노드 까지의 최단 거리를 저장하기 위해서 1차원 리스트를 이용함.

 

반면 플로이드 워셜은 2차원 리스트에 최단 거리 정보를 저장한다는 특징이 있다. 모든 노드에 대하여 다른 모든 노드로 가는 최단 거리 정보를 담아야 하기 때문이다. 2차원 리스트를 처리해야 하므로 N번의 반복단계에서 N^2의 처리를 하게 된다.

 

또 다익스트라의 경우 그리디 알고리즘인 반면 플로이드 워셜의 경우 다이나믹 프로그래밍 이다.

노드의 개수가 N이라 할 때, N번 만큼의 단꼐를 반복하며 점화식에 맞게 2차원 리스트를 갱신하기 때문이다.

 

Dab = min(Dab, Dak+Dkb)

전체적으로 3중 반복문을 이용하여 최단 거리 테이블을 갱신한다.

 

import sys

global INF

if __name__ == '__main__':
    INF = int(1e9)
    input = sys.stdin.readline

    n,m = map(int,input().split())

    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())
        graph[a][b]=c
    #점화식에 따른 플로이드 워셜 알고리즘 수행
    for i in range(1, n+1): # 거쳐갈 node
        for j in range(1, n+1): # j > k         j > i > k
            for k in range( 1, n+1):
                graph[j][k]=min(graph[j][k],(graph[j][i]+graph[i][k]))

    for k in range(1, n+1):
        for j in range(1, n+1):
            if graph[k][j]==INF:
                print("INFINITY")
            else:
                print(graph[k][j])