다익스트라 알고리즘 Python & C++ (예)

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

출발점에서 도착점까지 이동하는 데 드는 비용이 가장 적은 경로를 최단 경로 또는 최단 거리라고 합니다. 그래프 이론에서는 출발점에서 도착점까지 여러 경로가 존재할 수 있습니다. 이러한 경로들 중에서 비용이 가장 적은 경로가 있다면, 그 경로를 최단 경로라고 부릅니다.

여기서 "비용"이란 경로상의 노드 수 또는 각 간선의 비용 합계를 의미합니다. 경로는 하나 또는 여러 개의 간선을 가질 수 있습니다. 두 정점 사이의 연결을 "간선"이라고 합니다. 최단 경로 알고리즘에는 다익스트라 알고리즘, 벨만-포드 알고리즘 등 다양한 유형이 있습니다.

여기서는 다익스트라 알고리즘에 대해 논의하겠습니다. 다음 가중 그래프를 살펴보겠습니다.

무방향 가중치 그래프

• "가중치"라는 용어는 한 노드에서 다른 노드로 이동하는 데 드는 비용을 의미합니다. 예를 들어, 노드 1에서 노드 2로 이동하는 데 드는 비용 또는 가중치는 1입니다.
• 노드 1과 노드 2 사이의 경로를 간선이라고 합니다.
• "방향 없음"이란 한 노드에서 다른 노드로 이동했다가 다시 이전 노드로 돌아갈 수 있다는 의미입니다. 따라서 노드 1에서 노드 7까지의 모든 경로를 찾으려면 다음과 같은 경로가 있습니다.

이 네 가지 경로 중에서 첫 번째 경로의 비용이 7임을 알 수 있습니다. 따라서 비용 측면에서 가장 짧은 경로입니다.

최단 경로

Dijkstra 알고리즘의 작동 방식

다익스트라 알고리즘은 방향 그래프와 무방향 가중 그래프 모두에서 최단 거리를 찾을 수 있습니다. 이 알고리즘은 시작점에서 가장 가깝거나 가장 짧은 노드를 항상 선택하기 때문에 탐욕적 알고리즘입니다. "탐욕적"이라는 용어는 알고리즘이 여러 결과 중에서 가장 좋은 것을 선택한다는 것을 의미합니다.

여기서는 모든 경로 중에서 가장 짧은 경로를 찾으려고 합니다. 따라서 다익스트라 알고리즘은 단일 출발점에서 출발하여 모든 최단 경로를 찾습니다. 결과적으로, 이 알고리즘은 마치... 탐욕스러운 알고리즘.

아래 "예시" 섹션에서 단계별 접근 방식을 확인할 수 있습니다. 작동 방식은 다음과 같습니다.

단계 1) 시작 노드의 비용을 0으로 초기화하고 나머지 노드의 비용은 무한대로 설정합니다.
단계 2) 배열이나 리스트를 유지하여 관리하세요. trac방문한 노드의 k개.
단계 3) 노드 비용을 최소 비용으로 업데이트합니다. 이는 현재 비용과 경로 비용을 비교하여 수행할 수 있습니다(예제 섹션 참조).
단계 4) 모든 노드를 방문할 때까지 3단계를 계속하십시오.

이 모든 단계를 완료하면 소스에서 대상까지 최소 비용이 드는 경로를 찾을 수 있습니다.

Dijkstra와 BFS, DFS의 차이점

다익스트라 알고리즘과 BFS-DFS의 주요 차이점은 다익스트라는 최단 경로 탐색 알고리즘인 반면, BFS와 DFS는 일반적인 경로 탐색 알고리즘이라는 점입니다. 일반적으로 BFS와 DFS는 경로를 찾을 때 간선 비용을 고려하지 않습니다. 따라서 이러한 알고리즘은 최단 경로를 보장할 수 없습니다.

BFS 작동 방식을 보여주는 2D 그리드 데모

알고스케치, BFS 데모를 보여줍니다

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

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

여기서 BFS는 레벨 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 알고리즘의 목표는 이러한 총 비용 또는 무게를 최소화하는 것입니다. 위에 표시된 예에서는 노드 1에서 노드 7까지의 최상의 경로를 찾은 다음 모든 비용을 계산합니다.

다익스트라 알고리즘은 가중치를 계산하여 최단 경로를 찾습니다. 모든 가능한 경로를 탐색하지는 않습니다. 예를 들어 다익스트라 알고리즘을 설명해 보겠습니다. 예를 들어, 노드 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"은 노드 "6"에서 노드 "7"로 이동할 수 있으므로 방문한 것으로 표시되지 않았습니다. 경로 "1-2-6"의 비용은 4였습니다. 따라서 경로 1-2-6-7의 비용은 7이 됩니다.

7 < 8이므로 출발점 "1"에서 도착점 "7"까지의 최단 경로는 1-2-6-7이며 비용은 7입니다. 이전에는 1-3-7이었고 비용은 8이었습니다. 따라서 최종 그래프는 다음과 같습니다.

검은색 선으로 표시된 가장자리는 1에서 7까지의 최단 경로이며 비용은 7입니다.

별명 Code 다익스트라 알고리즘

다음은 다익스트라 알고리즘의 의사 코드입니다.

Dijkstra(G, S):
  for each vertex V in G
    distance[V] <- Infinity
    previous[V] <- NULL
    if V does not equal S, then,
      (priority queue) Q.push(V)
  distance[S] = 0
  While Q is not empty
    U <- Extract the MIN from Q
    For each unvisited adjacent V of U
      TotalDistance <- distance[U] + edge_cost(U, V)
      if TotalDistance is less than distance[V], then
        distance[V] <- TotalDistance
        previous[V] <- U
  return distance, previous

C++ 다익스트라 알고리즘 구현

다음을 사용하여 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] && 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] && graph[U][j] &&
          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의 알고리즘을 구현하려면 Python다음은 코드입니다:

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] <= _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 < 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 알고리즘의 응용

다익스트라 알고리즘은 다양한 분야에서 활용됩니다. 그중에서도 특히 네트워킹 분야에서 널리 사용됩니다. 다음은 다익스트라 알고리즘의 실제 활용 사례 몇 가지입니다.

다익스트라 인 Google 지도 : 위 코드 조각 출력에서 ​​볼 수 있듯이, 이 알고리즘은 최단 경로를 찾는 데 핵심적인 역할을 합니다.

Google 단순 다익스트라 알고리즘을 사용하지 않고, 수정된 버전을 사용합니다. 목적지를 선택하면 여러 경로를 보여줍니다. Google 지도. 이러한 경로들 중에서 일부는 사용자에게 보기 좋게 정렬되어 있습니다. 이러한 경로는 "시간"을 기준으로 선택됩니다. 따라서 "시간"은 최단 경로에 대한 간선 비용입니다.

IP 라우팅에서의 다익스트라 정리: IP 라우팅 라우팅은 네트워킹 용어입니다. 데이터 패킷이 여러 경로를 거쳐 수신자에게 전송되는 방식을 설명합니다. 이러한 경로는 라우터, 서버 및 기타 장비로 구성됩니다. IP 라우팅에는 다양한 유형의 프로토콜이 있습니다.

이러한 프로토콜은 라우터가 데이터를 전송하는 최단 경로를 찾는 데 도움을 줍니다. 프로토콜 중 하나가 "OSPF(Open Shortest Path First)"입니다. OSPF는 다익스트라 알고리즘을 사용합니다. 라우터는 경로 테이블을 유지 관리하며, 각 라우터는 이 테이블을 이웃 라우터와 공유합니다. 업데이트된 테이블을 받은 라우터는 모든 경로를 다시 계산해야 합니다. 이때 라우터는 다익스트라 알고리즘을 사용합니다.

Dijkstra 알고리즘의 한계

다익스트라 알고리즘은 음수 간선이 있는 그래프에서 최단 경로를 보장할 수 없습니다. 다익스트라 알고리즘은 다음과 같은 원칙을 따릅니다.

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

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

왼쪽 그래프에서, 그래프에는 세 개의 정점이 있습니다. 다익스트라 알고리즘은 다음과 같이 실행됩니다.

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

단계 2) 노드 "1"을 방문한 것으로 표시하고 최단 경로에 포함시키세요.

단계 3) 출발 노드 1에서 노드 "2"와 "3"까지의 거리는 최단 경로가 아직 계산되지 않았으므로 무한대로 설정됩니다. 따라서 무한대보다 짧은 모든 경로는 최단 경로에 추가됩니다(탐욕 알고리즘).

단계 4) 출발점 정점 "1"에서 "2"까지의 거리를 업데이트합니다. 현재 가중치는 5입니다(5 < 무한대). 마찬가지로 노드 "1"에서 "3"까지의 거리도 가중치 3으로 업데이트합니다.

단계 5) 이제 노드 "1"에서 최단 거리를 확인해 보면, 간선 1→2의 최단 거리가 5임을 알 수 있습니다. 따라서 노드 "2"는 방문한 것으로 표시됩니다. 마찬가지로 노드 "3"도 최단 거리가 3이므로 방문한 것으로 표시됩니다.

하지만 살펴보면 1-3-2 경로가 있는데, 이 경로의 비용은 2에 불과합니다. 그런데 다익스트라 알고리즘은 노드 "1"에서 노드 "2"까지의 최단 거리가 5라고 계산합니다. 즉, 다익스트라 알고리즘은 최단 거리를 정확하게 계산하지 못한 것입니다. 그 이유는 다익스트라 알고리즘이 탐욕 알고리즘이기 때문입니다. 따라서 한 번 방문한 노드는 더 짧은 경로가 존재하더라도 다시 고려되지 않습니다. 이러한 문제는 간선의 비용이나 가중치가 음수일 때만 발생합니다.

다익스트라 알고리즘은 이러한 상황에서 두 노드 사이의 최단 경로를 계산하는 데 실패합니다. 결과적으로 이 알고리즘에는 몇 가지 단점이 있습니다. 이러한 음의 간선 문제를 해결하기 위해 "벨만-포드 알고리즘"이라는 다른 알고리즘이 사용됩니다. 이 알고리즘은 음의 간선을 처리할 수 있습니다.

Dijkstra의 알고리즘 복잡도

위의 구현은 두 개의 "for" 루프를 사용했습니다. 이 루프는 정점 수만큼 실행됩니다. 따라서 시간 복잡도는 다음과 같습니다. O(V²)여기서 "O"라는 용어는 다익스트라 알고리즘에 대한 가정을 나타내는 표기법입니다.

그래프를 "우선순위 큐"를 사용하여 저장할 수 있습니다. 우선순위 큐는 이진 힙 데이터 구조입니다. 2차원 행렬보다 효율적입니다. 최소 비용을 가진 간선은 높은 우선순위를 갖게 됩니다. 따라서 시간 복잡도는 다음과 같습니다. O(E 로그 V). 여기서 E는 변의 개수이고, V는 꼭지점의 개수이다.

공간 복잡도는 O(V²), 인접 행렬(2D 배열). 공간 복잡도는 인접 리스트나 큐 데이터 구조를 사용하여 최적화할 수 있습니다.

자주 묻는 질문