Chapter 4-5. 다익스트라 최단 경로 알고리즘
카테고리: Algorithm Lesson 2
인프런에 있는 Rookiss님의 [C#과 유니티로 만드는 MMORPG 게임 개발 시리즈] Part2: 자료구조와 알고리즘 강의를 듣고 정리한 필기입니다. 😀
🌜 강의 들으러 가기 Click
Chapter 4. 그래프
🚖 다익스트라 최단 경로 알고리즘
모든 정점을 방문하되, 최단 경로로.
0방문- 예약 👉
1(15),3(35)- 0 을 지나 1 으로 온다면
1의 가중치는 15 - 0 을 지나 3 으로 온다면
3의 가중치는 35
- 0 을 지나 1 으로 온다면
- 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
- 0 1 을 지나 2 으로 온다면
- 20 < 24
2이 예약되어 있는 정점들 중 비용이 가장 낮으므로2선택
- 예약 👉
2방문- 새로 예약 할게 없음 (0 1 2) 을 지나올 수 있는 정점이 없어서.
- 현재 예약 목록
3선택
3방문- 예약 👉
4(30 = 15 + 10 + 5)- 0 1 3 을 지나 4 으로 온다면
4의 가중치는 15 + 10 + 5 = 30
- 0 1 3 을 지나 4 으로 온다면
- 현재 예약 목록
4선택
- 예약 👉
4방문- 예약 👉
5(35 = 15 + 10 + 5 + 5)- 0 1 3 4 을 지나 5 으로 온다면
5의 가중치는 15 + 10 + 5 + 5 = 35
- 0 1 3 4 을 지나 5 으로 온다면
- 현재 예약 목록
5선택
- 예약 👉
5방문- 새로 예약 할게 없음
- 현재 예약 목록 X 👉 종료
BFS 랑 비슷하면서도 다르다는 것을 알 수 있다. 예약하고 예약한 정점들 중에서 다음 방문 정점을 선택한다는 점에서는 같지만 예약 목록에서 방문할 정점을 선택할 땐, 무조건 예약 된지 가장 오래된 정점을 선택하는 BFS 와 달리 다익스트라 알고리즘은 예약된 정점들의 가중치를 다르게 받아들이며 비용이 가장 낮은 정점을 다음 방문 정점으로 선택하게 된다. 예약된 정점들의 가중치는 현재까지 어떤 정점들을 방문해왔느냐에 따른 가중치의 합이다. 그러나 예약된 정점들의 가중치는 언제든지 새롭게 업데이트 될 수 있다. 어떤 경로가 되느냐에 따라, 현재 어떤 정점을 방문 중이냐에 따라 예약된 정점들의 가중치가 달라질 수 있다. 바로 이게 그 당시 상황에서의 최단 거리가 됨. 그 때 그때의 상황의 최단 거리를 가진 정점을 선택하는 것이다.
- BFS 와의 비교 (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해당 정점의 부모 (지나온 바로 이전 정점) - 출발 정점 초기화
- 출발 정점에서 출발 정점까지의 거리는 0
- distance[start] = 0
- 출발 정점의 부모는 자기 자신. 출발 정점
- parent[start] = start;
- 출발 정점에서 출발 정점까지의 거리는 0
- 다음 방문 정점 찾기 👉 예약된 후보 정점들 중 가장 최단거리를 가지는 정점 뽑기
아래 과정 무한 반복
과정 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️⃣ 에 의하여.
- 모든 정점을 검사하되 현재 예약 된 정점을 찾기 위하여
- 아래의 세 과정을 뚫은 정점만이 방문 후보가 된다.
visited[i]이 True 면 방문하기로 선택 되어 예약 목록에서 빠진 정점이다. 따라서 스킵.distance가 Int32.MaxValue 면 예약 된적이 없는 정점이므로 예약 목록에 당연히 없다. 스킵.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가 업데이트가 된다면 현재 예약 목록에 속한 정점이 되는 것.
- 이
- 예약 될 수 있는 조건
now와 연결 되어 있어야 함- 방문 한 적이 없는 정점이어야 함
- 위 두 조건을 뚫었으면 예약 후보 임명
- 예약 후보가 되었으니
distance를 임명해야 하는데 새로운 방문지now를 기준으로 새로 업데이트한 distance[now] + adj[now, next]; 거리가 기존에 발견된 최단 거리distance[next]보다 작다면 새롭게 업데이트 한다.
- 예약 후보가 되었으니
이중 반복문이라 비효율적인 것을 볼 수 있다. while 문 안에 for문.. 😂 for문을 또 쓰지 않고 예약 후보 정점들을 우선순위 큐로 관리면 자동으로 최소 값을 가지는(Min Heap) 정점을 방문 노드로 뽑아낼 수 있다. 우선 순위 큐로 개선할 수 있음.
🚖 다익스트라 의사 코드
Graph- 그래프 정보. 모든 노드와 노드 간의 거리, 이웃노드에 관한 정보를 포함한다.
Source- 출발할 노드를 의미한다.
prev[(node)]- 출발지까지 가장 빠르게 갈 수 있다고 계산된 이웃 노드를 가리킨다. 즉, 출발지부터 목적지까지의 경로가 아니라, 목적지부터 출발지까지의 경로를 기록한다.
dist[(node)]- 출발지부터 현재 node까지의 cost 값을 의미한다.
function Dijkstra(Graph, Source):
dist[source] ← 0 // 소스와 소스 사이의 거리 초기화 --출발지와 출발지의 거리는 당연히 0--
prev[source] ← undefined // 출발지 이전의 최적 경로 추적은 없으므로 Undefined
create vertex set Q //노드들의 집합 Q(방문되지 않은 노드들의 집합) 생성 시작
for each vertex v in Graph: // Graph안에 있는 모든 노드들의 초기화
if v ≠ source: // V 노드가 출발지가 아닐 경우(출발지를 제외한 모든 노드!)
dist[v] ← INFINITY // 소스와 V노드 사이에 알려지지 않은 거리 --얼마나 먼지 모르니까-- = 무한값 ( 모든 노드들을 초기화하는 값)
prev[v] ← UNDEFINED // V노드의 최적경로 추적 초기화
add v to Q // Graph에 존재하고 방금 전 초기화된 V 노드를 Q(방문되지 않은 노드들의 집합)에 추가
//요약하자면, Graph에 존재하는 모든 노드들을 초기화한 뒤, Q에 추가함.
while Q is not empty: // Q 집합이 공집합 아닐 경우, 루프 안으로!
u ← vertex in Q with min dist[u] // 첫번째 반복에서는 dist[source]=0이 선택됨. 즉, u=source에서 시작
remove u from Q // U 노드를 방문한 것이므로 Q집합에서 제거
for each neighbor v of u: // U의 이웃노드들과의 거리 측정
alt ← dist[u] + length(u, v) // 출발지 노드 부터 계산된 U노드까지의 거리 + V에서 U의 이웃노드까지의 거리
//= source to U + V to U = source to U
if alt < dist[v]: // 방금 V노드까지 계산한 거리(alt)가 이전에 V노드까지 계산된 거리(dist[v])보다 빠른 또는 가까운 경우
dist[v] ← alt // V에 기록된 소스부터 V까지의 최단거리를 방금 V노드까지 계산한 거리로 바꿈
prev[v] ← u // 제일 가까운 노드는 지금 방문하고 있는 노드(U)로 바꿈
return dist[], prev[] //계산된 거리값과 목적지를 리턴
🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄
댓글남기기