Dijsktra의 알고리즘: C++, Python 코드 예

최단 경로 또는 최단 거리란 무엇입니까?

소스 정점에서 최소 비용이 드는 대상 정점까지의 경로가 최단 경로 또는 최단 거리입니다. 그래프 이론에서는 소스에서 대상까지 여러 경로를 가질 수 있습니다. 이들 경로 사이에 최소한의 비용이 드는 경로가 있다면 이를 최단 경로 알고리즘이라 부를 수 있다.

여기서 "비용"은 경로의 노드 수 또는 각 경로의 비용 합계를 의미합니다. 경로에는 하나 이상의 가장자리가 있을 수 있습니다. 두 정점 사이의 연결을 "모서리"라고 합니다. Dijkstra 알고리즘, Bellman-Ford 알고리즘 등 다양한 유형의 최단 경로 알고리즘이 있습니다.

오늘은 다익스트라 알고리즘(Dijkstra Algorithm)에 대해 알아보겠습니다.

폴로를 살펴보자wing 가중 그래프:

무방향 가중치 그래프
무방향 가중치 그래프
  • "가중치"라는 용어는 한 노드에서 다른 노드로 비용을 이동하는 것을 의미합니다. 예를 들어 노드 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 그리드 데모

2D 그리드 데모

알고스케치, 쇼wing BFS 시연

이 데모는 BFS가 경로만 찾는다는 것을 나타냅니다. 그러나 경로의 가중치는 고려하지 않습니다. BFS(폭 우선 검색)는 한 노드에서 다른 노드로 이동하는 데 드는 비용은 1이라고 가정합니다.

하지만 예시 그래프를 살펴보겠습니다.

2D 그리드 데모

여기서는 레벨 2에서 경로를 찾습니다. BFS는 레벨 순서대로 그래프를 탐색합니다. 따라서 다음과 같이 이동합니다.

단계 1) 노드 “1”에서 시작하여 인접한 모든 노드 2,3,4를 방문합니다.

단계 2) 노드 2,3,4를 레벨 1로 표시하고 인접한 노드를 방문합니다. 대상 노드에 도달할 때까지 모든 인접 노드를 계속 탐색합니다.

DFS 측면에서는 다음과 같이 1에서 7까지의 경로를 통과합니다.wing:

  • 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는 다음 작업을 수행합니다.wing:

  • DFS는 소스(시작 정점)에서 대상까지의 경로를 찾을 수 있습니다.
  • 원본 노드에서 대상까지 검색된 경로가 최단 경로인지 여부는 보장할 수 없습니다.

그러나 Dijkstra 알고리즘에서는 비용을 기준으로 가장자리를 선택합니다. 그리디 알고리즘으로서 최적 또는 최소 비용 경로를 선택합니다.

Dijkstra 알고리즘의 예

Dijkstra 알고리즘은 비용 또는 가중치를 사용하여 경로의 총 비용을 계산합니다.

Dijkstra 알고리즘의 예

Dijkstra 알고리즘의 목표는 이러한 총 비용 또는 무게를 최소화하는 것입니다. 위에 표시된 예에서는 노드 1에서 노드 7까지의 최상의 경로를 찾은 다음 모든 비용을 계산합니다.

Dijkstra 알고리즘에서는 가중치를 계산하여 최단 경로를 찾습니다. 가능한 모든 경로를 검색하지는 않습니다. 예제를 통해 Dijkstra 알고리즘을 살펴보겠습니다. 예를 들어 노드 1에서 7까지의 최단 경로를 찾으라는 요청을 받았습니다.

이 프로세스의 단계는 다음과 같습니다.

단계 1) 시작 노드 비용을 0으로 초기화합니다.

나머지 노드 할당 “인프”. 이는 시작 정점(소스)과 노드 사이에 경로가 존재하지 않거나 경로를 아직 방문하지 않았음을 의미합니다.

Dijkstra 알고리즘의 예

단계 2) 노드 1을 선택하면 방문한 것으로 표시됩니다. 그런 다음 노드 1의 모든 인접한 이웃을 업데이트합니다. 2,3,4는 노드 1의 이웃 노드입니다.

비용을 업데이트하는 동안 아래 절차를 따라야 합니다.

Dijkstra 알고리즘의 예

위 공식을 사용하여 각 노드의 비용을 업데이트할 수 있습니다. 예를 들어 우리는 노드 1에 있었고 인접한 노드 2,3,4의 비용을 업데이트해야 했습니다.

업데이트 후 비용 또는 무게는 다음과 같습니다.

Dijkstra 알고리즘의 예

3단계) ​​노드 “2”의 경우, 이웃은 6과 3입니다. 무한대(현재 값)를 비교하여 "6"의 비용을 업데이트하고 있습니다. 노드 2의 비용 + 2에서 6까지의 경로 비용입니다. 간단히 말하면 노드 "6"의 비용은 1+3 또는 4입니다.

Dijkstra 알고리즘의 예

노드 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단계 이후에는 다음과 같습니다.

Dijkstra 알고리즘의 예

이제 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이었습니다.

따라서 최종 그래프는 다음과 같습니다.

Dijkstra 알고리즘의 예

검은색 선으로 표시된 가장자리는 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: 기본적으로 이 알고리즘은 최단 경로를 찾기 위한 백본입니다. 위의 코드 조각 출력에서 ​​볼 수 있듯이.

Dijkstra 알고리즘의 응용

Google은 간단한 Dijkstra 알고리즘을 사용하지 않습니다. 대신 수정된 버전을 사용합니다. 목적지를 선택하면 구글 지도에 여러 경로가 표시됩니다. 이러한 경로 중 일부 경로는 사용자를 위해 정렬됩니다. 선택된 경로는 "시간"을 기준으로 합니다. 따라서 "시간"은 최단 경로의 가장자리 비용입니다.

IP 라우팅의 Dijkstra: IP 라우팅 네트워킹 용어입니다. 이는 데이터 패킷이 다른 경로를 통해 수신기로 전송되는 방식을 의미합니다. 이러한 경로는 라우터, 서버 등으로 구성됩니다. IP 라우팅에는 다양한 유형의 프로토콜이 있습니다.

이러한 프로토콜은 라우터가 데이터를 전송할 최단 경로를 찾는 데 도움이 됩니다. 프로토콜 이름 중 하나는 “OSPF(Open Shortest Path First)”입니다. OSPF는 dijkstra 알고리즘을 사용합니다. 라우터는 경로 테이블을 유지 관리합니다. 각 라우터 shares 이웃 라우터가 있는 테이블입니다. 업데이트된 테이블을 받은 후 모든 경로를 다시 계산해야 합니다. 이때 라우터는 Dijkstra 알고리즘을 사용합니다.

Dijkstra 알고리즘의 한계

Dijkstra 알고리즘은 음의 에지 그래프에서 최단 경로를 보장할 수 없습니다. Dijkstra 알고리즘은 다음 방법론을 따릅니다.

  • 한 노드에서 다른 노드로 하나의 최단 경로가 선택됩니다.
  • 두 노드 사이의 최단 경로가 선택되면 다시 계산되지 않습니다.

여기에서 음수 모서리가 있는 두 가지 예를 확인하세요.

Dijkstra 알고리즘의 한계

왼쪽 그래프에서, 세 개의 꼭지점이 있습니다. Dijkstra는 다음과 같이 그래프에서 실행됩니다.wing:

단계 1) 시작 정점 "1"은 XNUMX으로 초기화됩니다. 다른 노드는 무한대를 갖습니다.

Dijkstra 알고리즘의 한계

단계 2) 노드 “1”을 방문한 것으로 표시하고 최단 경로에 포함시킵니다.

단계 3) 최단 경로가 아직 계산되지 않았으므로 소스 노드 1에서 노드 "2"와 "3"까지의 거리는 무한대로 설정됩니다. 따라서 무한대보다 비용이 적게 드는 경로는 최단 경로에 추가됩니다(탐욕적 접근 방식).

단계 4) 소스 정점 또는 소스 노드 "1"에서 "2"로의 거리 업데이트. 현재 가중치는 5(5

Dijkstra 알고리즘의 한계

단계 5) 이제 노드 "1"에서 최단 거리를 확인하면 5가 가장자리 1-> 2의 최단 거리임을 알 수 있습니다. 따라서 노드 "2"는 방문한 것으로 표시됩니다.

마찬가지로 노드 "3"도 최단 거리가 3이므로 방문한 것으로 표시됩니다.

그러나 관찰해 보면 비용이 1에 불과한 경로 3-2-2가 있습니다. 그러나 Dijkstra는 노드 “1”에서 노드 “2”까지의 최단 거리가 5임을 보여줍니다. 따라서 Dijkstra는 최단 거리를 계산하지 못했습니다. 거리를 정확하게 두세요. 이런 일이 발생한 이유는 Dijkstra가 탐욕스러운 알고리즘이기 때문입니다. 따라서 노드가 방문한 것으로 표시되면 더 짧은 경로를 사용할 수 있더라도 다시 고려되지 않습니다. 이 문제는 가장자리에 음수 비용이 있거나 음수 가중치 가장자리가 있는 경우에만 발생합니다.

이 시나리오에서는 Dijkstra가 두 노드 사이의 최단 경로를 계산하지 못합니다. 결과적으로 이 알고리즘에는 몇 가지 단점이 있습니다. 이 음의 에지 문제를 해결하기 위해 "Bellman-Ford Algorithm"이라는 또 다른 알고리즘이 사용됩니다. 해당 알고리즘은 음의 가장자리에서 작동할 수 있습니다.

Dijkstra의 알고리즘 Complexity

위의 구현에서는 두 개의 "for" 루프를 사용했습니다. 이러한 루프는 정점 수만큼 실행됩니다. 그래서 타임컴은plexity는 오(V2). 여기서 "0"이라는 용어는 Dijkstra 알고리즘에 대한 가정을 제공하는 표기법을 의미합니다.

"우선순위 큐"를 사용하여 그래프를 저장할 수 있습니다. 우선순위 큐는 이진 힙 데이터 구조입니다. 2D 매트릭스보다 더 효율적입니다. 최소 비용을 갖는 에지가 높은 우선순위를 갖습니다.

그럼 타임컴plex이 될 것입니다 O (E log (V)). 여기서 E는 변의 개수이고, V는 꼭지점의 개수이다.

스페이스컴plexity는 오(V2), 인접 행렬(2D 배열). 스페이스컴plex인접 목록이나 대기열 데이터 구조를 사용하여 최적화할 수 있습니다.