Dijsktra의 알고리즘: C++, Python 코드 예제
사라 첸
최단 경로 또는 최단 거리란 무엇입니까?
소스 정점에서 최소 비용이 드는 대상 정점까지의 경로가 최단 경로 또는 최단 거리입니다. 그래프 이론에서는 소스에서 대상까지 여러 경로를 가질 수 있습니다. 이들 경로 사이에 최소한의 비용이 드는 경로가 있다면 이를 최단 경로 알고리즘이라 부를 수 있다.
여기서 "비용"은 경로의 노드 수 또는 각 경로의 비용 합계를 의미합니다. 경로에는 하나 또는 여러 개의 에지가 있을 수 있습니다. 두 정점 사이의 연결을 "에지"라고 합니다. Dijkstra 알고리즘, Bellman-Ford 알고리즘 등과 같은 다양한 유형의 최단 경로 알고리즘이 있습니다.
오늘은 다익스트라 알고리즘(Dijkstra Algorithm)에 대해 알아보겠습니다.
다음의 가중 그래프를 살펴보겠습니다.
- "가중치"라는 용어는 한 노드에서 다른 노드로 비용을 이동하는 것을 의미합니다. 예를 들어 노드 1에서 노드 2로 이동하면 비용 또는 가중치는 1입니다.
- 노드 1에서 노드 2까지의 경로를 가장자리라고 합니다.
- "무지정"은 한 노드를 다른 노드로 이동했다가 다시 이전 노드로 돌아갈 수 있음을 의미합니다. 따라서 노드 1에서 노드 7까지의 모든 경로를 찾으려고 하면 다음과 같습니다.
| 경로 또는 경로 | 비용 |
|---|---|
| 1-2-6 | (1+3+3) = 7 |
| 1-2-3 | (1+9+1) = 11 |
| 1-3-7 | (7+1) = 8 |
| 1-4-5 | (6+2+5) = 13 |
이 7개의 경로 중 첫 번째 경로의 비용은 XNUMX이라는 것을 알 수 있습니다. 따라서 비용 측면에서 가장 짧은 경로입니다.
Dijkstra 알고리즘의 작동 방식
Dijkstra 알고리즘은 방향성 및 무방향 가중치 그래프 모두에서 최단 거리를 찾을 수 있습니다. 이 알고리즘은 항상 원점에서 가장 짧거나 가장 가까운 노드를 선택하기 때문에 탐욕적입니다. "탐욕적"이라는 용어는 일련의 결과 또는 결과 중에서 알고리즘이 가장 좋은 것을 선택한다는 것을 의미합니다.
여기서는 다른 모든 경로 중에서 가장 짧은 경로를 찾으려고 합니다. 따라서 Dijkstra 알고리즘은 단일 대상 노드에서 모든 최단 경로를 찾습니다. 결과적으로 다음과 같이 동작합니다. 탐욕스러운 알고리즘.
아래의 "예제" 섹션에서는 단계별 접근 방식을 볼 수 있습니다. 다음과 같이 작동합니다:
단계 1) 비용이 0인 시작 노드를 초기화하고 나머지 노드는 무한 비용으로 초기화합니다.
단계 2) 방문한 노드를 추적하기 위해 배열 또는 목록을 유지합니다.
단계 3) 최소 비용으로 노드 비용을 업데이트합니다. 이는 현재 비용과 경로 비용을 비교하여 수행할 수 있습니다. (데모는 예제 섹션에 나와 있습니다.)
단계 4) 모든 노드를 방문할 때까지 3단계를 계속합니다.
이 모든 단계를 완료하면 소스에서 대상까지 최소 비용이 드는 경로를 찾을 수 있습니다.
Dijkstra와 BFS, DFS의 차이점
Dijkstra와 BFS-DFS의 주요 차이점은 Dijkstra가 최단 경로 찾기 알고리즘이고 BFS, DFS가 경로 찾기 알고리즘이라는 것입니다. 일반적으로 BFS와 DFS는 경로를 찾을 때 비용을 고려하지 않습니다. 따라서 이러한 알고리즘은 최단 경로를 보장할 수 없습니다.
BFS 작동 방식을 보여주는 2D 그리드 데모
이 데모는 BFS가 경로만 찾는다는 것을 나타냅니다. 그러나 경로의 가중치는 고려하지 않습니다. BFS(폭 우선 검색)는 한 노드에서 다른 노드로 이동하는 데 드는 비용은 1이라고 가정합니다.
하지만 예시 그래프를 살펴보겠습니다.
여기서는 레벨 2에서 경로를 찾습니다. BFS는 레벨 순서대로 그래프를 탐색합니다. 따라서 다음과 같이 이동합니다.
단계 1) 노드 “1”에서 시작하여 인접한 모든 노드 2,3,4를 방문합니다.
단계 2) 노드 2,3,4를 레벨 1로 표시하고 인접한 노드를 방문합니다. 대상 노드에 도달할 때까지 모든 인접 노드를 계속 탐색합니다.
DFS 관점에서 보면 1부터 7까지의 경로는 다음과 같습니다.
- 1→2→3→7 (원가 10, DFS 비용 3)
- 1→2→6→7 (원가 7, DFS 비용 3)
- 1→3→7 (원가 8, DFS 비용 2)
- 1→4→5→7 (원가 13, DFS 비용 3)
보시다시피 DFS는 깊이 수 또는 가장자리 수를 사용하여 경로 비용을 계산합니다.
DFS는 다음을 수행합니다.
- DFS는 소스(시작 정점)에서 대상까지의 경로를 찾을 수 있습니다.
- 원본 노드에서 대상까지 검색된 경로가 최단 경로인지 여부는 보장할 수 없습니다.
그러나 Dijkstra 알고리즘에서는 비용을 기준으로 가장자리를 선택합니다. 그리디 알고리즘으로서 최적 또는 최소 비용 경로를 선택합니다.
Dijkstra 알고리즘의 예
Dijkstra 알고리즘은 비용 또는 가중치를 사용하여 경로의 총 비용을 계산합니다.
Dijkstra 알고리즘의 목표는 이러한 총 비용 또는 무게를 최소화하는 것입니다. 위에 표시된 예에서는 노드 1에서 노드 7까지의 최상의 경로를 찾은 다음 모든 비용을 계산합니다.
Dijkstra 알고리즘에서는 가중치를 계산하여 최단 경로를 찾습니다. 가능한 모든 경로를 검색하지는 않습니다. 예제를 통해 Dijkstra 알고리즘을 살펴보겠습니다. 예를 들어 노드 1에서 7까지의 최단 경로를 찾으라는 요청을 받았습니다.
이 프로세스의 단계는 다음과 같습니다.
단계 1) 시작 노드 비용을 0으로 초기화합니다.
나머지 노드 할당 “인프”. 이는 시작 정점(소스)과 노드 사이에 경로가 존재하지 않거나 경로를 아직 방문하지 않았음을 의미합니다.
단계 2) 노드 1을 선택하면 방문한 것으로 표시됩니다. 그런 다음 노드 1의 모든 인접한 이웃을 업데이트합니다. 2,3,4는 노드 1의 이웃 노드입니다.
비용을 업데이트하는 동안 아래 절차를 따라야 합니다.
위 공식을 사용하여 각 노드의 비용을 업데이트할 수 있습니다. 예를 들어 우리는 노드 1에 있었고 인접한 노드 2,3,4의 비용을 업데이트해야 했습니다.
업데이트 후 비용 또는 무게는 다음과 같습니다.
3단계) 노드 “2”의 경우, 이웃은 6과 3입니다. 무한대(현재 값)를 비교하여 "6"의 비용을 업데이트하고 있습니다. 노드 2의 비용 + 2에서 6까지의 경로 비용입니다. 간단히 말하면 노드 "6"의 비용은 1+3 또는 4입니다.
노드 3은 노드 2의 이웃입니다. 그러나 이전 단계에서 비용을 계산했는데 7이었습니다. 이제 경로가 1-2-3이면 노드 3의 비용은 10이 됩니다. 경로 1-2- 3개는 10, 1~3개는 7개입니다.
4단계) 노드 3의 경우, 이웃 노드는 7입니다. 따라서 노드 7의 현재 값을 경로 비용(7+1) 또는 8과 비교하여 노드 7의 비용을 업데이트합니다. 즉 8입니다.
따라서 노드 1에서 노드 7까지의 경로를 찾게 되며, 1→3→7이 됩니다. 비용은 8입니다.
5단계) 노드 4의 경우, 이에 따라 인접 노드 비용을 업데이트할 것입니다. 따라서 노드 "5"의 비용은 8로 업데이트됩니다. 4,5단계 이후에는 다음과 같습니다.
이제 1-3-7 경로의 비용은 (이전) 8입니다. 노드 "7"은 노드 "7"에서 노드 "6"에 도달할 수 있으므로 방문한 것으로 표시되지 않았습니다. "1-2-6" 경로의 비용은 4입니다. 따라서 경로 1-2-6-7의 비용은 7입니다.
7 < 8이므로 소스 정점 “1”에서 대상 정점 “7”까지의 최단 경로는 1-2-6-7이 되고 비용은 7이 됩니다. 이전에는 1-3-7이었고 비용은 8입니다. XNUMX이었습니다.
따라서 최종 그래프는 다음과 같습니다.
검은색 선으로 표시된 가장자리는 1에서 7까지의 최단 경로이며 비용은 7입니다.
의사 코드 Dijkstra의 알고리즘
다음은 Dijkstra 알고리즘의 의사 코드입니다.
Dijkstra(G, S):
for each vertex V in G
distance[V] & lt; - Infinity
previous[V] & lt; - NULL
if V does not equal S, then,
(priority queue) Q.push(V)
distance[S] = 0
While Q is not empty
U & lt; - Extract the MIN from Q
For each unvisited adjacent V of U
TotalDistance & lt; - distance[U] + edge_cost(U, V)
if TotalDistance is less than distance[V], then
distance[V] & lt; - TotalDistance
previous[V] & lt; - u
return distance, previous
C++ 구현 Dijkstra의 알고리즘
다음을 사용하여 Dijkstra의 알고리즘을 구현하려면 C++, 코드는 다음과 같습니다.
#include <bits/stdc++.h>
using namespace std;
#define size 7
int minimumDistance(int distance[], bool visited[]) {
int min = INT_MAX;
int min_index = INT_MAX;
for (int i = 0; i < size; i++) {
if (!visited[i] & amp; & distance[i] <= min) {
min = distance[i];
min_index = i;
}
}
return min_index;
}
void printParentPath(int parent[], int i) {
if (parent[i] == -1) {
return;
}
printParentPath(parent, parent[i]);
cout << i + 1 << " ";
}
void dijkstra(int graph[size][size], int source) {
int distance[size];
bool visited[size];
int parent[size];
for (int i = 0; i < size; i++) {
parent[0] = -1;
distance[i] = INT_MAX;
visited[i] = false;
}
distance[source] = 0;
for (int i = 0; i < size - 1; i++) {
int U = minimumDistance(distance, visited);
visited[U] = true;
for (int j = 0; j < size; j++) {
int curr_distance = distance[U] + graph[U][j];
if (!visited[j] & amp; & graph[U][j] & amp; &
curr_distance < distance[j]) {
parent[j] = U;
distance[j] = curr_distance;
}
}
}
cout << "Vertex\t\tDistance\tPath" << endl;
for (int i = 1; i < size; i++) {
cout << source + 1 << "->" << i + 1 << "\t\t" << distance[i] << "\t\t"
<< source + 1 << " ";
printParentPath(parent, i);
cout << endl;
}
}
int main() {
int graph[size][size] = {{0, 1, 7, 6, 0, 0, 0}, {1, 0, 9, 0, 0, 3, 0},
{7, 9, 0, 0, 0, 0, 1}, {6, 0, 0, 0, 2, 0, 0},
{0, 0, 0, 2, 0, 0, 0}, {0, 3, 0, 0, 0, 0, 3},
{0, 0, 0, 0, 5, 3, 0}};
dijkstra(graph, 0);
}
출력:
Vertex Distance Path 1->2 1 1 2 1->3 7 1 3 1->4 6 1 4 1->5 8 1 4 5 1->6 4 1 2 6 1->7 7 1 2 6 7
Python 구현 Dijkstra의 알고리즘
다음을 사용하여 Dijkstra의 알고리즘을 구현하려면 파이썬, 코드는 다음과 같습니다.
num_of_vertex = 7
def minimumDistance(distance, visited):
_min = 1e11
min_index = 1e11
for i in range(num_of_vertex):
if not visited[i] and distance[i] & lt; = _min:
_min = distance[i]
min_index = i
return min_index
def printParentNode(parent, i):
if parent[i] == -1:
return
printParentNode(parent, parent[i])
print("{} ".format(i + 1), end = "")
def dijkstra(graph, src):
distance = list()
visited = list()
parent = list()
for i in range(num_of_vertex):
parent.append(-1)
distance.append(1e11)
visited.append(False)
distance[src] = 0
for i in range(num_of_vertex - 1):
U = minimumDistance(distance, visited)
visited[U] = True
for j in range(num_of_vertex):
curr_distance = distance[U] + graph[U][j]
if not visited[j] and graph[U][j] and curr_distance & lt;
distance[j]: parent[j] = U
distance[j] = curr_distance
print("Vertex\t\tDistance\tPath")
for i in range(num_of_vertex):
print("{}->{}\t\t{}\t\t{}
".format(src + 1, i + 1, distance[i], src + 1), end = "")
printParentNode(parent, i)
print("")
graph = [
[0, 1, 7, 6, 0, 0, 0],
[1, 0, 9, 0, 0, 3, 0],
[7, 9, 0, 0, 0, 0, 1],
[6, 0, 0, 0, 2, 0, 0],
[0, 0, 0, 2, 0, 0, 0],
[0, 3, 0, 0, 0, 0, 3],
[0, 0, 0, 0, 5, 3, 0]
]
dijkstra(graph, 0)
출력:
Vertex Distance Path 1->1 0 1 1->2 1 1 2 1->3 7 1 3 1->4 6 1 4 1->5 8 1 4 5 1->6 4 1 2 6 1->7 7 1 2 6 7
알고리즘이 소스 노드로부터의 최단 거리를 계산하는 것을 볼 수 있습니다.
Dijkstra 알고리즘의 응용
Dijkstra Algo에는 다양한 용도가 있습니다. 그 중에서도 네트워킹 분야에서 널리 사용됩니다. Dijkstra 알고리즘의 실제 사용법은 다음과 같습니다.
Google 지도의 Dijkstra: 기본적으로 이 알고리즘은 최단 경로를 찾기 위한 백본입니다. 위의 코드 조각 출력에서 볼 수 있듯이.
Google은 간단한 Dijkstra 알고리즘을 사용하지 않습니다. 대신 수정된 버전을 사용합니다. 목적지를 선택하면 구글 지도에 여러 경로가 표시됩니다. 이러한 경로 중 일부 경로는 사용자를 위해 정렬됩니다. 선택된 경로는 "시간"을 기준으로 합니다. 따라서 "시간"은 최단 경로의 가장자리 비용입니다.
IP 라우팅의 Dijkstra: IP 라우팅 네트워킹 용어입니다. 이는 데이터 패킷이 다른 경로를 통해 수신기로 전송되는 방식을 의미합니다. 이러한 경로는 라우터, 서버 등으로 구성됩니다. IP 라우팅에는 다양한 유형의 프로토콜이 있습니다.
이러한 프로토콜은 라우터가 데이터를 보낼 최단 경로를 찾는 데 도움이 됩니다. 프로토콜 이름 중 하나는 "OSPF(Open Shortest Path First)"입니다. OSPF는 다이크스트라 알고리즘을 사용합니다. 라우터는 경로 테이블을 유지 관리합니다. 각 라우터는 이웃 라우터와 테이블을 공유합니다. 업데이트된 테이블을 수신한 후 모든 경로를 다시 계산해야 합니다. 이때 라우터는 다이크스트라 알고리즘을 사용합니다.
Dijkstra 알고리즘의 한계
Dijkstra 알고리즘은 음의 에지 그래프에서 최단 경로를 보장할 수 없습니다. Dijkstra 알고리즘은 다음 방법론을 따릅니다.
- 한 노드에서 다른 노드로 하나의 최단 경로가 선택됩니다.
- 두 노드 사이의 최단 경로가 선택되면 다시 계산되지 않습니다.
여기에서 음수 모서리가 있는 두 가지 예를 확인하세요.
왼쪽 그래프에서, 세 개의 정점이 있습니다. Dijkstra는 다음과 같이 Graph에서 실행됩니다.
단계 1) 시작 정점 "1"은 XNUMX으로 초기화됩니다. 다른 노드는 무한대를 갖습니다.
단계 2) 노드 “1”을 방문한 것으로 표시하고 최단 경로에 포함시킵니다.
단계 3) 최단 경로가 아직 계산되지 않았으므로 소스 노드 1에서 노드 "2"와 "3"까지의 거리는 무한대로 설정됩니다. 따라서 무한대보다 비용이 적게 드는 경로는 최단 경로에 추가됩니다(탐욕적 접근 방식).
단계 4) 소스 정점 또는 소스 노드 "1"에서 "2"로의 거리 업데이트. 현재 가중치는 5(5
단계 5) 이제 노드 "1"에서 최단 거리를 확인하면 5가 가장자리 1-> 2의 최단 거리임을 알 수 있습니다. 따라서 노드 "2"는 방문한 것으로 표시됩니다.
마찬가지로 노드 "3"도 최단 거리가 3이므로 방문한 것으로 표시됩니다.
그러나 관찰해 보면 비용이 1에 불과한 경로 3-2-2가 있습니다. 그러나 Dijkstra는 노드 “1”에서 노드 “2”까지의 최단 거리가 5임을 보여줍니다. 따라서 Dijkstra는 최단 거리를 계산하지 못했습니다. 거리를 정확하게 두세요. 이런 일이 발생한 이유는 Dijkstra가 탐욕스러운 알고리즘이기 때문입니다. 따라서 노드가 방문한 것으로 표시되면 더 짧은 경로를 사용할 수 있더라도 다시 고려되지 않습니다. 이 문제는 가장자리에 음수 비용이 있거나 음수 가중치 가장자리가 있는 경우에만 발생합니다.
이 시나리오에서는 Dijkstra가 두 노드 사이의 최단 경로를 계산하지 못합니다. 결과적으로 이 알고리즘에는 몇 가지 단점이 있습니다. 이 음의 에지 문제를 해결하기 위해 "Bellman-Ford Algorithm"이라는 또 다른 알고리즘이 사용됩니다. 해당 알고리즘은 음의 가장자리에서 작동할 수 있습니다.
Dijkstra의 알고리즘 복잡도
위의 구현은 두 개의 "for" 루프를 사용했습니다. 이 루프는 정점 수만큼 실행됩니다. 따라서 시간 복잡도는 다음과 같습니다. 오(V2). 여기서 "0"이라는 용어는 Dijkstra 알고리즘에 대한 가정을 제공하는 표기법을 의미합니다.
"우선순위 큐"를 사용하여 그래프를 저장할 수 있습니다. 우선순위 큐는 이진 힙 데이터 구조입니다. 2D 매트릭스보다 더 효율적입니다. 최소 비용을 갖는 에지가 높은 우선순위를 갖습니다.
그러면 시간 복잡도는 다음과 같습니다. O (E log (V)). 여기서 E는 변의 개수이고, V는 꼭지점의 개수이다.
공간 복잡도는 오(V2), 인접 행렬(2D 배열). 공간 복잡도는 인접 리스트나 큐 데이터 구조를 사용하여 최적화할 수 있습니다.
