최단 경로 알고리즘

최단 경로 문제란, 가중치 그래프에서 간선(edge)의 가중치의 합이 최소가 되는 경로를 찾는 문제이다.

• 가중치 (방향) 그래프 G=(V,E)가 있다고 할 때. 모든 간선(edge)에 가중치가 있음
• 경로의 '길이'는 경로상 모든 간선의 가중치의 합이며 -> 이 길이가 최소가 되도록 하는게 최단 경로 문제이다.
• 노드 u에서 v까지의 최단경로 길이를 델타(u,v)라고 표시한다.

최단 경로 문제의 종류

• 단일 출발 최단 경로, Single-source(one-to-all): 하나의 출발 노드 s로부터 다른 모든 노드까지의 최단 경로를 찾는 문제

  • ex) Dijkstra(다익스트라) 알고리즘

• 단일 도착 최단 경로, Single-destination: 다른 모든 노드로부터 하나의 목적지 노드까지의 최단 경로를 찾는 문제

  • 따로 배우진 않을것. 엣지의 방향을 거꾸로 한다고 했을 때 Single-source 문제와 동일하기 때문

• 단일 쌍 최단 경로, Single-pair(one-to-one):

  • 이것도 Single-source 문제의 알고리즘을 쓴다.

• 전체 쌍 최단 경로, All-pairs: 모든 노드 쌍에 대해서 최단 경로를 찾는 문제

  • ex) Floyd(플로이드)

주요 알고리즘

• BFS(완전 탐색 알고리즘에 속함)
  • 가중치가 없거나 모든 가중치가 동일한 그래프에서 최단 경로를 구하는 경우 가장 빠르다. (그래프의 가중치가 다 다를경우 BFS로는 최단 경로 문제를 해결할 수 없다.)
• 다익스트라 알고리즘(Dijkstra)
  • 음의 가중치가 없는 가중 그래프에서 단일 출발, 단일 도착, 단일 쌍 최단 경로 문제
• 벨만-포드 알고리즘(Bellman-Ford-Moore)
  • 가중 그래프에서 단일 출발, 단일 도착, 단일 쌍 최단 경로 문제
• 플로이드-워셜 알고리즘(Floyd-Warshall)
  • 전체 쌍 최단 경로 문제

음수 가중치

다익스트라 알고리즘에서는 음수 가중치가 없다는 가정하에 진행함

음수 사이클: 사이클인데 사이클을 구성하는 간선(edge)의 총합이 음수인 사이클

음수 사이클이 있으면 최단 경로가 정의되지 않는다. 사이클을 돌 수록 가중치의 합이 작아지기 때문이다.

알고리즘에 따라 음수 가중치가 있어도 작동하는 경우도 있고 그렇지 않은 경우도 있다.

최단 경로의 기본 특성

• 최단 경로의 어떤 부분 경로도 역시 최단 경로이다.

u - x - y - v 이 경로가 u에서 v까지 최단 경로라면
x - y 경로도 x에서 y까지의 최단 경로이다.

• 최단 경로는 사이클을 포함하지 않는다.(음수사이클이 없다는 가정하에서)

Single-source 최단 경로 문제

입력값: 음수 사이클이 없는 가중치 방향그래프 G=(V,E)와 출발 노드 sㅌV (그래프에 V개의 정점과 E개의 간선이 있고 출발 노드는 s이다.)

목적: 각 노드 vㅌV에 대해서 다음을 계산한다.

• d[v] (d = distance = dist 를 의미)

  • 처음에는 d[s] = 0, d[v] = 무한대 (나머지 정점들) 로 시작한다.
  • d[v] 값은 알고리즘이 진행되면서 감소해간다. 하지만 항상 d[v] >= 델타(s,v)를 유지한다. (델타(s,v)는 s에서 v로 갈 때 최단 경로 길이를 의미한다.)
  • 최종적으로는 d[v] = 델타(s,v) = 최단 경로 가 된다.

• 파이[v]

  • s에서 v까지 최단경로 상에서 v의 직전 노드
  • 그런 노드가 없는 경우 파이[v] = null

기본연산: relaxation

그림에서 (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 최단 경로 알고리즘의 기본 구조

  • 1. 초기화: d[s]=0, 노드 v=/=s에 대해서 d[v]=무한대, 파이[v]=null
  • 2. 간선(edge)들에 대한 반복적인 relaxation 연산

• 어떤 간선(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번의 반복으로 충분하다.

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

V개의 정점과 E개의 간선을 가진 가중치 그래프 G에서 특정 출발 정점(s)에서 부터 다른 모든 정점까지의 최단경로를 구하는 알고리즘이다.

V개의 정점과 E개의 간선을 가진 가중치 그래프에서 어떤 정점 A에서 어떤 정점 B까지의 최단거리는 최대 V-1개의 간선을 사용한다. (시작 정점 A를 포함하여 최대 V개의 정점을 지난다.)

for문 (V-1번 실행)
for문 (음수 사이클이 있는지 확인하는 작업)

• 음의 가중치를 가지는 간선도 포함될 수 있다.

• 음의 사이클이 존재하는지 확인하고 이 경우를 제외시킨다. 음의 사이클이 존재하는지 확인할 때 E개의 모든 간선을 한번 더 확인한다.

• 시간복잡도: O(VE)

  • (V-1) x E(간선의 개수, for문 내에서 간선 개수만큼 반복하니까)

• 다익스트라 알고리즘과의 차이점: 벨만-포드 알고리즘은 매 반복마다 모든 간선을 확인한다. 반면 다익스트라 알고리즘은 방문하지 않는 노드들 중에서 최단 거리가 가장 가까운 노드만을 방문한다.

다익스트라 알고리즘(Dijkstra)

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까지 가는 최단 경로의 길이이다.

Ref

• 영리한 프로그래밍을 위한 알고리즘 강좌 - 인프런 강의
• 알고리즘 - 최단 경로 알고리즘 (다익스트라 알고리즘, 벨만-포드 알고리즘, 플로이드-워셜 알고리즘)
• https://shnoh.tistory.com/15
• https://taesung1993.tistory.com/48
• https://m.blog.naver.com/kks227/220796963742