Algorithm design - 최단경로

---

Dijkstra

가중치가 있는 그래프에서 한 시작 정점에서 다른 모든 정점까지의 최단 거리를 계산하는 데 사용되는 알고리즘이다. 아래와 같이 정의된다고 했을 때 알고리즘의 작동 과정을 살펴보자.

S: 최단경로가 발견된 정점들의 집합
weight[i, j] : 아크 <i, j>의 가중치
Dist[i]: S에 속하지 않은 i에 대해서, v에서 시작하여 S에 있는 정점만을 거쳐 정점 i에 이르는 최단 경로의 길이

 

1. 처음 S에는 시작점 v만 포함, Dist[v]=0
2. 가장 최근에 S에 첨가한 정점을 u로 설정
3. u의 모든 인접 정점 중에서 S에 포함 되지 않은 w에 대해 Dist[w]를 다시 계산
Dist[w]=min{Dist[w],Dist[u]+weight[u,w]}
4. S에 포함되지 않은 모든 정점 w중에서 dist[w]가 가장 작은 정점 w를 S에 첨가 5. 모든 정점에 대한 최단 경로가 결정될 때까지 단계 2~4 를 반복

 

- G의 n개의 정점을 0에서 n-1까지 번호를 붙임

- S[] : 정점 i 가 S에 포함되어 있으면 S[i] = true, 아니면 S[i]=false로 표현 하는 불리언 배열
- weight[n, n] : 가중치 인접행렬

Pseudo code로 살펴보면 아래와 같이 설계될 수 있음을 알 수 있다.

다른 알고리즘들과 비슷하게 강조해둔 가중치를 갱신하는 부분이 핵심이다.

위와 같이 최단 거리로 Dist list를 채워가며 방문여부를 S list에서 계속 체크해주는 것이 핵심이다.

체크여부를 확인해가며 하나씩 점점 갱신해나가는 모습이다. 그러나 점선으로 표시된 부분들은 간과하고 판단한다는 단점이 존재한다.

---

Bellman-Ford

음의 가중치를 가진 방향 그래프에 대해서는 Dijkstra 알고리즘으로 최단 경로를 구할 수 없으므로 Bellman-Ford 알고리즘을 이용한다. 음의 길이값을 갖는 사이클은 허용하지 않는다. 사이클이 없는 최단경로가 가질 수 있는 최대 간선수(n-1)를 이용하여 알고리즘을 작성한다.

알고리즘 수행 과정을 살펴보면 아래와 같다.

- Dist(k)[u]:시작점v에서정점u까지최대k개의아크를갖는 최단경로의길이
- Dist(1)[u] = weight[v, u]
- Dist(n-1)[u] : 시작점 v에서 정점 u까지의 최단 경로의 길이

- Dist(k)[u] ← min{ Dist(k-1)[u], min{Dist(k-1)[i] + weight[i, u]} } (k = 2, 3,..., n-1)

다익스트라 알고리즘은 2중 for문 내에 if문을 통해 최단 경로 갱신을 진행했는데 그와 달리 Bellman-Ford에서는 3중 for문 내에 if문을 통해 최단 경로를 갱신하는 것을 확인할 수 있다. 이 때문에 최단거리 기록 list 생성도 훨씬 복잡한 것을 볼 수 있다.

---

DAG

Directed Acyclic Graph, 즉 싸이클이 없는 유향 그래프를 뜻하는 DAG의 최단경로는 위상정렬후에 계산을 하여 선형시간에 간단히 구할 수 있다.

위와 같은 그래프를 아래와 같이 위상정렬하여 최단경로를 간단하게 구할 수 있는 것이다.

---

SCC

그래프의 모든 정점쌍에 대해서 양방향으로 경로가 존재하면 강하게 연결되었다고 한다. 강하게 연결된 부분 그래프를 강연결요소(SCC, Strongly connected component)라 한다.

stronglyConnectedComponent(G)
{
	1. 그래프 에 대해 DFS를 수행하여 각 정점 v의 완료시간 fv를 계산한다; 
	2. GR을 만든다;
	3. DFS를 수행하되 시작점은 1에서 구한 fv가 가장 큰 정점으로 잡는다;
	4. 3에서 만들어진 분리된 트리들 각각을 강연결요소로 리턴한다;
}

---