직관적인 이해: 단일 소스에서 최단 경로 얻기 -Dijkstra 알고리즘

SSSP 디제스트라 알고리즘: 네덜란드 컴퓨터 과학자 에즈거 디코스처가 1959 년 제안한 단일 소스 최단 경로 알고리즘 (SSSP) 입니다. 가중치 그래프 (음수 가중치가 없는 가장자리) 에서 한 정점에서 다른 정점까지의 최단 경로 문제를 해결하는 알고리즘입니다. Dijkstra 알고리즘은 탐욕 알고리즘, 폭 넓은 우선 검색 (BFS) 및 동적 계획을 결합한 최단 경로 알고리즘입니다. Dijkstra 알고리즘의 주요 특징은 원점에서 시작하여 욕심 많은 알고리즘을 사용하는 전략으로, 매번 원점과 가장 가깝고 액세스되지 않은 정점의 인접한 정점으로 이동하여 종점까지 확장한다는 것이다.

Dijkstra 알고리즘은 두 개의 집합 (최단 경로의 정점이 발견됨) 과 (최단 경로의 정점을 찾을 수 없음) 을 유지 관리하고, 컬렉션에서 경로 거리가 가장 작은 점을 반복적으로 제거하고, 컬렉션이 비어 있을 때까지 각 정점에서 소스 점까지의 최단 경로를 새로 이동한 점으로 업데이트합니다. 예를 들어 Dijkstra 알고리즘의 과정을 간단히 설명하겠습니다.

정점 a 가 알고리즘의 시작점이 아닌 다음 그림을 가지고 있다고 가정합니다.

먼저 두 세트의 합과 각 정점에서 소스 점까지의 거리를 초기화해야 합니다. A 에 직접 인접하지 않은 경우 결과는 양의 무한대로 설정됩니다.

단계 1: 컬렉션에서 가장 작은 점을 선택합니다. 여기서 정점 F 를 선택하면 컬렉션의 합이 다음과 같이 변경됩니다. 가장 최근의 중간 정점에서 소스 점 A 까지의 가장 짧은 거리를 다시 계산합니다.

Step 2:: 컬렉션에서 가장 작은 점을 선택합니다. 여기서 정점 e 를 선택하면 컬렉션의 합이 다음과 같이 변경됩니다. 가장 최근 재계산을 기준으로 정점에서 소스 점 a 까지의 가장 짧은 거리를 계산합니다.

세 번째 단계: 컬렉션에서 가장 작은 점을 선택합니다. 여기서 정점 C 를 선택하면 컬렉션의 합이 변경됩니다. 즉, 가장 최근 재계산된 정점에서 소스 점 A 까지의 가장 짧은 거리를 기준으로 합니다.

네 번째 단계: 컬렉션에서 가장 작은 점을 선택합니다. 여기서 정점 D 를 선택하면 컬렉션의 합이 다음과 같이 변경됩니다. 그리고 가장 최근 재계산된 정점에서 소스 점 A 까지의 가장 짧은 거리를 기준으로 합니다. (존 F. 케네디, Northern Exposure (미국 TV 드라마), 예술명언)

5 단계: 컬렉션에서 가장 작은 점을 골라서 정점 B 를 고르고, 컬렉션의 합은 다음과 같이 변경됩니다. 가장 최근의 재계산을 기준으로 정점에서 소스 점 A 까지의 가장 짧은 거리를 계산합니다.

6 단계: 컬렉션에서 가장 작은 점을 선택합니다. 여기서 정점 G 를 선택하면 컬렉션의 합계가 다음과 같이 변경됩니다. 컬렉션이 비어 있기 때문에 알고리즘이 반복을 중지하고 결과를 출력합니다.

다음은 Dijkstra 알고리즘 계산 프로세스에 대한 간단한 설명입니다.