[개념] 최단 경로

 

최단 경로 알고리즘은 말 그대로 가장 짧은 경로를 찾는 알고리즘으로, '길 찾기' 문제라고도 불린다. 

 

최단 경로 문제는 보통 그래프를 이용하여 표현하는데 각 지점은 그래프에서 '노드'로 표현되고, 지점 간 연결된 도로는 그래프에서 '간선'으로 표현된다. 

 

최단 거리 알고리즘은 다익스트라 최단 경로 알고리즘, 플로이드 워셜, 벨만 포드 알고리즘 이렇게 3가지 이다.

이 중, 다익스트라 최단 경로와 플로이드 워셜 알고리즘이 가장 많이 등장한다.

 

최단 경로 알고리즘에는 그리디 알고리즘과 다이나믹 프로그래밍 알고리즘이 적용된다.

 

 

 

---

1. 다익스트라 최단 경로 알고리즘

 

: 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다.

다익스트라 최단 경로 알고리즘은 '음의 간선'이 없을 때 정상적으로 동작한다.

 

다익스트라 알고리즘은 최단 경로를 구하는 과정에서 '각 노드에 대한 현재까지의 최단 거리' 정보를 항상 1차원 리스트에 저장하며 리스트를 계속 갱신한다는 특징이 있다. 

 

 

 

 

<예시>

1번 노드에서 각 노드에 도달할 수 있는 최단 경로를 구해보자 (방문한 노드는 회색으로 칠할 것이다.) 

 

🔨 Step 1.

 

1번을 제외한 나머지 노드는 처음에 무한대로 초기화된다. 

노드 번호	1	2	3	4	5
거리	0	INF	INF	INF	INF

 

 

🔨 Step 2.   

 

방문하지 않은 노드 중 가장 작은 거리인, 노드 1부터 시작

노드 1에서는 노드 3과 노드 4 방문, 각각 6과 3으로 기존의 거리보다 작으므로 바꿔준다.

노드 번호	1	2	3	4	5
거리	0	INF	6	3	INF

 

 

 

🔨 Step 3.

 

방문하지 않은 노드 중 가장 작은 거리인, 노드 4에 방문

노드 4에서는 노드 2와 노드 3을 방문할 수 있고, 거리는 각각 (3+1), (3+1)로 노드 2,3 모두 기존 값보다 작으므로 바꿔준다.

노드 번호	1	2	3	4	5
거리	0	4	4	3	INF

 

 

 

🔨 Step 4.

방문하지 않은 노드 중 가장 작은 거리인, 노드 2와 노드 3 중 노드 2 방문 (최단 거리가 같은 경우 주로 번호가 작은 것 먼저 방문)

노드 2에서는 노드 1을 방문하고 거리는 (4+3)으로, 기존의 거리보다 크므로 변하지 않는다.

노드 번호	1	2	3	4	5
거리	0	4	4	3	INF

 

 

 

🔨 Step 5.

방문하지 않은 노드 중 가장 작은 거리인 노드 3을 방문

노드 3에서는 노드 4를 방문하고 거리는 (4+2)이므로, 기존의 거리보다 커서 변하지 않는다.

노드 번호	1	2	3	4	5
거리	0	4	4	3	INF

 

 

 

🔨 Step 6. 

마지막 남은 노드 5를 방문하지만, 값이 INF라서, 거리는 변하지 않는다.

 

노드 번호	1	2	3	4	5
거리	0	4	4	3	INF

따라서, 노드 1에서는 노드 5를 방문하지 못함을 알 수 있다.