최단 경로 문제란, 가중치 그래프에서 간선(edge)의 가중치의 합이 최소가 되는 경로를 찾는 문제이다.
단일 출발 최단 경로, Single-source(one-to-all): 하나의 출발 노드 s로부터 다른 모든 노드까지의 최단 경로를 찾는 문제
단일 도착 최단 경로, Single-destination: 다른 모든 노드로부터 하나의 목적지 노드까지의 최단 경로를 찾는 문제
단일 쌍 최단 경로, Single-pair(one-to-one):
전체 쌍 최단 경로, All-pairs: 모든 노드 쌍에 대해서 최단 경로를 찾는 문제
다익스트라 알고리즘에서는 음수 가중치가 없다는 가정하에 진행함
음수 사이클: 사이클인데 사이클을 구성하는 간선(edge)의 총합이 음수인 사이클
음수 사이클이 있으면 최단 경로가 정의되지 않는다. 사이클을 돌 수록 가중치의 합이 작아지기 때문이다.
알고리즘에 따라 음수 가중치가 있어도 작동하는 경우도 있고 그렇지 않은 경우도 있다.
u - x - y - v 이 경로가 u에서 v까지 최단 경로라면
x - y 경로도 x에서 y까지의 최단 경로이다.
입력값: 음수 사이클이 없는 가중치 방향그래프 G=(V,E)와 출발 노드 sㅌV (그래프에 V개의 정점과 E개의 간선이 있고 출발 노드는 s이다.)
목적: 각 노드 vㅌV에 대해서 다음을 계산한다.
d[v] (d = distance = dist 를 의미)
파이[v]
그림에서 (a)를 예로 들어 설명하면,
u의 동그라미 안에 있는 숫자는 s부터 u까지의 최단 거리가 5라는 말이다. v도 마찬가지. s부터 v까지의 최단 거리가 9라는 말이다.
이 상태에서 u와 v를 연결하는 edge의 가중치가 2인 걸 알았다.
그렇다면... s -> u -> v로 가게되면 현재 s부터 v까지의 최단 거리인 9보다 짧을 것이다. 더 나은 경로를 알게된 것이다.
그래서 d[v] = 7로 업데이트하고 파이[v] = u가 된다.
대부분의 single-source 최단 경로 알고리즘의 기본 구조
어떤 간선(edge)에 대해서 어떤 순서로 relaxation 연산을 하느냐에 따라 알고리즘 종류가 달라짐
Generic-Single-Source
앞서 봤던 초기화 과정(초기화: d[s]=0, 노드 v=/=s에 대해서 d[v]=무한대, 파이[v]=null)
repeat
for each edge (u,v) ㅌ E (모든 edge에 대해서 반복한다.)
relax(u,v,w)
until there is no change(어떤 변화도 없을 때까지 반복)
질문 1) 이렇게 하면 최단 경로가 찾아지는가?
질문 2) 몇번 반복되는가?
최단경로에서 거쳐갈 수 있는 edge의 최대 개수는 n-1개이다.
즉 n-1번의 반복으로 충분하다.
V개의 정점과 E개의 간선을 가진 가중치 그래프 G에서 특정 출발 정점(s)에서 부터 다른 모든 정점까지의 최단경로를 구하는 알고리즘이다.
V개의 정점과 E개의 간선을 가진 가중치 그래프에서 어떤 정점 A에서 어떤 정점 B까지의 최단거리는 최대 V-1개의 간선을 사용한다. (시작 정점 A를 포함하여 최대 V개의 정점을 지난다.)
for문 (V-1번 실행)
for문 (음수 사이클이 있는지 확인하는 작업)
음의 가중치를 가지는 간선도 포함될 수 있다.
음의 사이클이 존재하는지 확인하고 이 경우를 제외시킨다. 음의 사이클이 존재하는지 확인할 때 E개의 모든 간선을 한번 더 확인한다.
시간복잡도: O(VE)
다익스트라 알고리즘과의 차이점: 벨만-포드 알고리즘은 매 반복마다 모든 간선을 확인한다. 반면 다익스트라 알고리즘은 방문하지 않는 노드들 중에서 최단 거리가 가장 가까운 노드만을 방문한다.
V개의 정점과 음수가 아닌 E개의 간선을 가진 그래프 G에서 특정 출발 정점(s)에서 부터 다른 모든 정점까지의 최단경로를 구하는 알고리즘
dist값을 갱신할 때 모든 간선에 대해서 relaxation연산을 하는 것이 아니라 조건을 만족해야 갱신하도록 하는 점이 벨만-포드 알고리즘과의 차이점이다.
출발점 s의 dist에 0을 저장한다. d[s] = 0
방문하지 않은 정점중에서 d[u]가 최소인 정점 u를 선택한다. (처음엔 출발노드인 s가 선택된다.)
정점 u에서 뻗어나가는 방문하지 않는 노드들이 새로운 최단 경로가 존재할 경우 dist 값을 갱신한다. d[w] = min { d[w], d[u] + E(u, w) } 이 작업이 완료되면 u는 방문했다고 체크한다.
모든 노드들을 방문하면 코드가 종료된다.
한번 방문한 노드는 방문하지 않는다. (그 노드에 대한 최단 거리는 이미 계산되어 다시 갱신할 필요가 없기 때문이다.)
음수 가중치가 없는 경우에 쓴다.
s로부터 최단 경로를 이미 알아낸 노드들을 집합 S에 넣는다. S는 처음엔 공집합이다가 노드가 추가된다. S의 크기가 V(정점의 개수)와 같아지면 종료한다.
집합 S에 없는 노드 u에 대해서 d[u]는 이미 S에 속한 노드들만 거쳐서 s로부터 u까지 가는 최단 경로의 길이이다.