dijkstra 방법의 기본 아이디어를 간략하게 설명합니다.

dijkstra 방법의 기본 아이디어를 간략하게 설명하면 다음과 같다.

먼저 시작점 O부터 시작하여 각 노드에 라벨을 부여하고, 이는 두 가지 카테고리로 구분된다. : T 라벨과 P 라벨 T 라벨은 시작점 O부터 지점까지의 최단 통행권 상한을 나타내며, 이는 최단 통행권을 나타냅니다. - 출발지점 O에서 지점까지 가는 길.

라벨링 과정에서 T 구두점은 계속 변경되며 P 라벨링은 변경되지 않습니다. P 라벨이 붙지 않은 모든 포인트에는 T 라벨이 붙습니다. 알고리즘의 각 단계에서 모든 T 라벨이 P 라벨로 변경될 때까지 특정 지점의 T 라벨을 P 라벨로 변경해야 합니다. 즉, 시작점 O부터 다른 지점까지의 최단 경로를 구하고 라벨링 과정을 종료한다.

1. Dijkstra

Dijkstra는 한 노드에서 다른 노드까지의 최단 경로를 계산하는 데 사용되는 일반적인 최단 경로 알고리즘입니다. 이 알고리즘은 그리디(greedy) 전략을 사용합니다. 즉, 매번 나머지 정점 중에서 소스 지점에 가장 가까운 정점을 찾습니다. 가중치 그래프가 주어지면 그래프의 각 가장자리의 가중치는 음수가 아니며 두 정점 사이의 거리를 나타냅니다. 그래프의 정점을 소스 포인트로 지정하고 소스 포인트에서 다른 정점까지의 최단 경로와 그 길이를 찾는 문제는 단일 소스 최단 경로 문제입니다.

Dijkstra 알고리즘의 입력에는 가중 방향 그래프 G와 G의 소스 정점 S가 포함되어 있습니다. V가 G의 모든 정점 집합을 나타낸다고 가정합니다. 그래프의 모든 모서리는 두 개의 꼭지점으로 구성된 순서화된 요소 쌍입니다. (u,v)는 정점 u와 v를 연결하는 경로가 있음을 의미합니다. 우리는 E의 모든 간선 집합을 취하고 간선의 가중치는 가중치 함수 w:E→[0,]에 의해 정의됩니다.

2. Dijkstra의 원리

초기화 중에 S에는 소스 노드만 포함됩니다. U에서 가장 작은 거리 v를 갖는 정점 k를 선택하고 이를 S에 추가합니다(선택한 거리는 v에서 k까지의 최단 경로 길이입니다). k를 새로 고려된 중간점으로 취하고, 소스 노드 v에서 정점 u까지의 거리(정점 k를 통과함)가 원래 거리(정점 k를 통과하지 않음)보다 짧은 경우 U의 각 정점의 거리를 수정합니다. 정점 u의 거리 값, 수정된 거리 값은 정점 k로부터의 거리에 k에서 u까지의 거리를 더한 값입니다.