다익스트라 최단 경로 알고리즘
최소 비용으로 모든 정점을 방문한다.
0 방문
예약 👉 1 (15), 3 (35)
0 을 지나 1 으로 온다면 1의 가중치는 15
0 을 지나 3 으로 온다면 3의 가중치는 35
15 < 35 1이 예약되어 있는 정점들 중 비용이 가장 낮으므로 1 선택
1 방문
예약 👉 2 (20 = 15 + 5), 3(25 = 15 + 10)
0 1 을 지나 2 으로 온다면 2의 가중치는 15 + 5 = 20
0 1 을 지나 3 으로 온다면 3의 가중치는 15 + 10 = 25
20 < 24 2이 예약되어 있는 정점들 중 비용이 가장 낮으므로 2 선택
2 방문
새로 예약 할게 없음 (0 1 2) 을 지나올 수 있는 정점이 없어서.
현재 예약 목록 3 선택
3 방문
예약 👉 4 (30 = 15 + 10 + 5)
0 1 3 을 지나 4 으로 온다면 4의 가중치는 15 + 10 + 5 = 30
현재 예약 목록 4 선택
4 방문
예약 👉 5 (35 = 15 + 10 + 5 + 5)
0 1 3 4 을 지나 5 으로 온다면 5의 가중치는 15 + 10 + 5 + 5 = 35
현재 예약 목록 5 선택
5 방문
새로 예약 할게 없음
현재 예약 목록 X 👉 종료
BFS와 유사하면서도 다르다는 것을 알 수 있다. 예약하고 예약한 정점들 중에서 다음 방문 정점을 선택한다는 점에서는 같지만 예약 목록에서 방문할 정점을 선택할 땐, 무조건 예약 된지 가장 오래된 정점을 선택하는 BFS와 달리 다익스트라 알고리즘은 예약된 정점들의 가중치를 다르게 받아들이며 비용이 가장 낮은 정점을 다음 방문 정점으로 선택하게 된다.
예약된 정점들의 가중치는 현재까지 어떤 정점들을 방문해왔느냐에 따른 가중치의 합이다. 그러나 예약된 정점들의 가중치는 언제든지 새롭게 업데이트 될 수 있다. 어떤 경로가 되느냐에 따라, 현재 어떤 정점을 방문 중이냐에 따라 예약된 정점들의 가중치가 달라질 수 있다. 바로 이게 그 당시 상황에서의 최단 거리가 된다. 그 때 그때의 상황의 최단 거리를 가진 정점을 선택하는 것이다.
[BFS와 다익스트라의 비교]
[BFS]
BFS는 가중치 그래프에선 사용할 수 없다.
예약된 정점들 중 들어간지 가장 오래된 애가 가장 좋은 정점이다.
모두 가중치 없이 동일 했었으니까 줄을 가장 오래선 애를 선택했을 뿐.
👉 따라서 방문 대기열의 자료구조를 큐(Queue)로 쓰는게 적합하다. 왜냐하면 가중치는 모두가 다 동일하니까(즉 비교 가
능한 가중치가 없고) 예약된지 오래된 순서로 방문하면 되기 때문에
[다익스트라]
다익스트라는 가중치 그래프에서 사용할 수 있다.
BFS와 달리 예약된 순서는 아무런 상관이 없다.
가중치가 방문한 곳에 따라 모두 다르기 때문에 예약된 정점은 언제든지, 그때 그때 상황에 따라 중요도 순서가 뒤집힐 수
있다. 따라서 큐(Queue)는 다익스트라 자료구조로는 적합하지 않다.
각 상황에 맞는 베스트 솔루션(= 최단 거리, 최소 가중치)을 예약 목록에서 선택한다.
예약된 정점들 중 여태 방문해온 정점들에서 이 정점을 선택했을 때 최단 경로가 된다! 싶은 정점을 선택한다. 그게 가장 좋
은 정점이기 때문이다. 따라서 방문 대기열의 자료구조를 우선순위 큐로 쓰는게 적합하다.
쉽게 이해하면 가중치 있는 그래프에서 사용하는 BFS 라고 생각하면 될 것 같다.
[큐를 이용한 다익스트라 구현]
class Graph
{
// -1 은 연결 안된 상태를 표시
int[,] adj = new int[6, 6]
{
{ -1, 15, -1, 35, -1, -1 },
{ 15, -1, 5, 10, -1, -1 },
{ -1, 5, -1, -1, -1, -1 },
{ 35, 10, -1, -1, 5, -1 },
{ -1, -1, -1, 5, -1, 5 },
{ -1, -1, -1, -1, 5, -1 },
};
public void Dijikstra(int start)
{
bool[] visited = new bool[6];
int[] distance = new int[6];
Array.Fill(distance, Int32.MaxValue);
int[] parent = new int[6];
distance[start] = 0;
parent[start] = start;
while(true)
{
// 제일 좋은 후보를 찾는다.
// 가장 유력한 정점의 거리와 번호를 저장한다.
int closet = Int32.MaxValue;
int now = -1;
for (int i = 0; i < 6; i++)
{
// 이미 방문한 정점은 스킵
if (visited[i])
continue;
// 아직 발견(예약)된 적이 없거나, 기존 후보보다 멀리 있으면 스킵
if (distance[i] == Int32.MaxValue || distance[i] >= closet)
continue;
// 지금 시점까지 발견한 가장 좋은 후보
closet = distance[i];
now = i;
}
if (now == -1) // 다음 후보가 하나도 없으므로 종료
break;
// 제일 좋은 후보를 찾았으니까 방문한다.
visited[now] = true;
// 방문한 정점과 연결되어 있는 정점들을 조사해서
// 상황에 따라 발견한 최단 거리를 갱신한다.
for (int next = 0; next < 6; next++)
{
// 연결되지 않은 정점은 스킵
if (adj[now, next] == -1)
continue;
// 이미 방문한 정점은 스킵
if (visited[next])
continue;
// 새로 조사된 정점의 최단 거리를 계산한다.
int nextDist = distance[now] + adj[now, next];
// 만약에 기존에 발견한 최단 거리가 새로 조사된 최단거리보다 크면 정보를 갱신
if (nextDist < distance[next])
{
distance[next] = nextDist;
parent[next] = now;
}
}
}
}
}
[함수 설명]
visited 방문 체크
distance 해당 점점까지의 거리 (최종적으로 최단 거리들이 저장되게 됨)
parent 해당 정점의 부모 (지나온 바로 이전 정점)
1. 출발 정점 초기화
출발 정점에서 출발 정점까지의 거리는 0 👉 distance[start] = 0
출발 정점의 부모는 자기 자신. 출발 정점 👉 parent[start] = start;
2. 다음 방문 정점 찾기 👉 예약된 후보 정점들 중 가장 최단거리를 가지는 정점 뽑기
[과정]
과정 1️⃣ : 예약된 것들 중에서 방문할 정점 고르기
예약 된 것들 중에서 방문할 정점 선택하기
👉 예약 된 것들 중에서 가장 최소 비용인 정점을 선택해야 한다.
// 제일 좋은 후보를 찾는다.
// 가장 유력한 정점의 거리와 번호를 저장한다.
int closet = Int32.MaxValue;
int now = -1;
for (int i = 0; i < 6; i++)
{
// 이미 방문한 정점은 스킵
if (visited[i])
continue;
// 아직 발견(예약)된 적이 없거나, 기존 후보보다 멀리 있으면 스킵
if (distance[i] == Int32.MaxValue || distance[i] >= closet)
continue;
// 지금 시점까지 발견한 가장 좋은 후보
closet = distance[i];
now = i;
}
distance가 Int32.MaxValue 이 아니면 3️⃣ 과정에서 현재 예약 되어 있거나, 혹은 예약이 예전에 됐던적이 있는 정점이다.
최소값 찾기 알고리즘처럼 closet에 해당 시점까지의 최소값을 저장해 나가고 더 작은 distance를 가진 정점을 찾으면 해당 값으로 업데이트 한다. now에도 그때 그때 시점에서의 최단 거리를 가진 정점을 저장해두고 더 작은 거리를 가진 정점을 찾으면 업데이트한다.
현재 예약된 정점은 visited[i] 은 False 상태지만 (방문하기로 선택된 것은 아니다!), distance는 Int32.MaxValue 가 아님. 과정3️⃣ 에 의하여.
모든 정점을 검사하되 현재 예약 된 정점을 찾기 위하여 아래의 세 과정을 뚫은 정점만이 방문 후보가 된다.
1. visited[i] 이 True 면 방문하기로 선택 되어 예약 목록에서 빠진 정점이다. 따라서 스킵.
2. distance가 Int32.MaxValue 면 예약 된적이 없는 정점이므로 예약 목록에 당연히 없다. 스킵.
3. distance[i]가 closet 보다 크면 방문 하지 않고 스킵한다. 더 작은 거리를 가진 정점을 방문하려고 하는거니까
위 세 과정을 뚫고 왔다면 바로 현재 예약 목록에 있는 정점인 것이다!
지금 시점까지 발견한 최단 거리를 가진, 가장 좋은 정점이 되므로 closet에 그 거리를, now에 그 정점을 업데이트 한다.
다음 for문 반복에서 더 좋은 정점을 발견하면 업뎃될 수 있다. (예약 목록에서 더 좋은 정점을 찾아내는 것이 목적이므로)
과정 2️⃣ : 방문한다.
if (now == -1) // 다음 후보가 하나도 없으므로 종료
break;
// 제일 좋은 후보를 찾았으니까 방문한다.
visited[now] = true;예약 된 후보가 하나도 없었다면 과정 1️⃣ 이 끝날 때까지 now는 -1 로 남아있을 것이다. 즉 모든 정점을 방문했다는 뜻이므로 다익스트라를 종료한다.
과정 1️⃣ 이 끝나면 now에 예약 목록에서 가장 좋은, 최단 거리 정점이 저장되어 있다. 해당 정점을 방문한다. visited[now] = true
과정 3️⃣ : 새로운 방문 노드를 중심으로 한 다음 예약 목록 선정
// 방문한 정점과 연결되어 있는 정점들을 조사해서
// 상황에 따라 발견한 최단 거리를 갱신한다.
for (int next = 0; next < 6; next++)
{
// 연결되지 않은 정점은 스킵
if (adj[now, next] == -1)
continue;
// 이미 방문한 정점은 스킵
if (visited[next])
continue;
// 새로 조사된 정점의 최단 거리를 계산한다.
int nextDist = distance[now] + adj[now, next];
// 만약에 기존에 발견한 최단 거리가 새로 조사된 최단거리보다 크면 정보를 갱신
if (nextDist < distance[next])
{
distance[next] = nextDist;
parent[next] = now;
}
}
새롭게 방문된 now를 기준으로 한 예약 목록을 업데이트한다. 해당 now를 기준으로 한 distance를 업데이트 한다. distance와 parent가 업데이트가 된다면 현재 예약 목록에 속한 정점이 되는 것이다.
예약 될 수 있는 조건
1. now와 연결 되어 있어야 함
2. 방문 한 적이 없는 정점이어야 함
위 두 조건을 뚫었으면 예약 후보 임명
예약 후보가 되었으니 distance를 임명해야 하는데 새로운 방문지 now를 기준으로 새로 업데이트한 distance[now] + adj[now, next]; 거리가 기존에 발견된 최단 거리 distance[next] 보다 작다면 새롭게 업데이트 한다.
'공부 > 인프런 - Rookiss' 카테고리의 다른 글
| Part 2-5-2. 트리 : 힙 트리, 우선순위 큐 (0) | 2023.08.10 |
|---|---|
| Part 2-5-1. 트리 : 트리 이론과 구현 (0) | 2023.08.10 |
| Part 2-4-4. 그래프 : BFS(너비 우선 탐색) (0) | 2023.08.09 |
| Part 2-4-3. 그래프 : DFS(깊이 우선 탐색) (0) | 2023.08.09 |
| Part 2-4-2. 그래프 : 그래프 이론, 생성 (0) | 2023.08.09 |