최단 경로를 찾는 예를 고려하십시오. 도시의 지역을 연결하는 고속도로 네트워크가 제공됩니다. 일부 도로는 일방통행입니다. 도심에서 해당 지역의 각 도시까지의 최단 경로를 찾으십시오.

이 문제를 해결하려면 다음을 사용할 수 있습니다. 다익스트라 알고리즘- 1959년 네덜란드 과학자 E. Dijkstra가 발명한 그래프 알고리즘. 그래프의 정점 중 하나에서 다른 모든 정점까지의 최단 거리를 찾습니다. 음수 가중치의 간선이 없는 그래프에만 작동합니다.

첫 번째 꼭짓점에서 다른 모든 꼭짓점까지의 최단 거리를 구해야 합니다.

원은 꼭짓점을 나타내고, 선은 꼭짓점 사이의 경로(그래프의 가장자리)를 나타냅니다. 정점의 수는 원으로 표시되고 가중치는 경로의 길이인 가장자리 위에 표시됩니다. 각 정점 옆에는 정점 1에서 이 정점까지의 최단 경로 길이인 빨간색 레이블이 표시됩니다.

정점 1 자체의 레이블은 0으로 가정하고 나머지 정점의 레이블은 연결할 수 없습니다. 큰 숫자(이상적으로는 무한대). 이것은 정점 1에서 다른 정점까지의 거리가 아직 알려지지 않았음을 반영합니다. 그래프의 모든 정점은 방문하지 않은 것으로 표시됩니다.

첫 번째 단계

정점 1은 최소 레이블을 가지며 정점 2, 3, 6은 이웃입니다. 우리는 차례로 정점의 이웃을 우회합니다.

정점 1의 첫 번째 이웃은 정점 2로 가는 경로의 길이가 최소이기 때문에 정점 2입니다. 꼭짓점 1을 통과하는 경로의 길이는 꼭짓점 1까지의 최단 거리, 레이블 값 및 1번째에서 2번째로 가는 가장자리의 길이의 합과 같습니다. 즉, 0 + 7 = 7입니다. 이것은 정점 2의 현재 레이블(10000)보다 작으므로 두 번째 정점의 새 레이블은 7입니다.


유사하게, 우리는 다른 모든 이웃(정점 3과 6)에 대한 경로 길이를 찾습니다.

노드 1의 모든 이웃이 확인됩니다. 정상 회담 1까지의 현재 최소 거리는 최종적인 것으로 간주되며 수정 대상이 아닙니다. 정점 1은 방문한 것으로 표시됩니다.

두번째 단계

알고리즘의 1단계가 반복됩니다. 다시 우리는 방문하지 않은 정점의 "가장 가까운"을 찾습니다. 이것은 7로 표시된 정점 2입니다.

다시 우리는 선택된 정점의 이웃 레이블을 줄이려고 시도하고 두 번째 정점을 통과하려고 시도합니다. 정점 2의 이웃은 정점 1, 3, 4입니다.

정점 1은 이미 방문했습니다. 정점 2의 다음 이웃은 정점 3입니다. 방문하지 않은 정점의 최소 레이블이 있기 때문입니다. 2를 통해 이동하면 그러한 경로의 길이는 17(7 + 10 = 17)과 같습니다. 그러나 세 번째 정점의 현재 레이블은 9이고 9< 17, поэтому метка не меняется.


꼭짓점 2의 또 다른 이웃은 꼭짓점 4입니다. 두 번째 꼭짓점을 통해 이동하면 이러한 경로의 길이는 22(7 + 15 = 22)와 같습니다. 22일부터<10000, устанавливаем метку вершины 4 равной 22.

정점 2의 모든 이웃이 조회되었으므로 방문한 것으로 표시합니다.

세 번째 단계

정점 3을 선택하여 알고리즘 단계를 반복합니다. "처리" 후 다음 결과를 얻습니다.

네 번째 단계

다섯 번째 단계

여섯 번째 단계


따라서 정점 1에서 정점 5까지의 최단 경로는 정점을 통과하는 경로가 됩니다. 1 — 3 — 6 — 5 , 이런 식으로 우리는 20의 최소 무게를 얻습니다.

최단 경로를 살펴보자. 우리는 각 꼭짓점에 대한 경로의 길이를 알고 있으며 이제 끝에서 꼭짓점을 고려할 것입니다. 마지막 정점(이 경우 정점 5 ), 연결된 모든 정점에 대해 최종 정점의 경로 길이에서 해당 모서리의 가중치를 빼서 경로 길이를 찾습니다.
네, 탑 5 경로 길이가 있습니다 20 . 그녀는 정상에 연결되어 있습니다 6 그리고 4 .
정상을 위해 6 무게를 얻다 20 - 9 = 11(일치됨).
정상을 위해 4 무게를 얻다 20 - 6 = 14(일치하지 않음).
결과적으로 문제의 정점의 경로 길이와 일치하는 값을 얻는다면(이 경우 정점 6 ) 그런 다음 최종 정점으로의 전환이 이루어졌습니다. 이 정점을 원하는 경로에 표시합니다.
다음으로 정점에 도달한 가장자리를 결정합니다. 6 . 그리고 시작 부분에 도달할 때까지 계속됩니다.
이러한 탐색의 결과로 어떤 단계에서 여러 꼭짓점에 대해 동일한 값이 있으면 그 중 하나를 사용할 수 있습니다. 여러 경로의 길이는 같습니다.

다익스트라 알고리즘의 구현

정사각형 행렬은 그래프 가중치를 저장하는 데 사용됩니다. 그래프의 꼭짓점은 행과 열의 머리글에 있습니다. 그리고 그래프 호의 가중치는 테이블의 내부 셀에 배치됩니다. 그래프에는 루프가 포함되어 있지 않으므로 행렬의 주대각선에는 0 값이 포함됩니다.

1 2 3 4 5 6
1 0 7 9 0 0 14
2 7 0 10 15 0 0
3 9 10 0 11 0 2
4 0 15 11 0 6 0
5 0 0 0 6 0 9
6 14 0 2 0 9 0

C++로 구현

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103

#define _CRT_SECURE_NO_WARNINGS
#포함
#포함
#크기 6 정의
정수 메인()
{
정수 // 연결 행렬
정수 d; // 최소 거리
intv; // 방문한 정점
int temp, miniindex, min;
int 시작 인덱스 = 0;
시스템("chcp 1251" );
시스템("cls" );
// 관계 행렬의 초기화
(int 나는 = 0; 나는 {
a[i][i] = 0;
(int j = i + 1; j printf( "거리 %d - %d 입력: ", 나는 + 1, j + 1);
scanf("%d" , &temp);
a[i][j] = 온도;
a[j][i] = 온도;
}
}
// 관계 행렬 표시
(int 나는 = 0; 나는 {
(int j = 0; j printf("%5d" , a[i][j]);
printf("\n");
}
// 정점과 거리 초기화
(int 나는 = 0; 나는 {
d[i] = 10000;
v[i] = 1;
}
d=0;
// 알고리즘 단계
하다(
최소 지수 = 10000;
최소 = 10000;
(int 나는 = 0; 나는 { // 정점을 아직 방문하지 않았고 가중치가 최소값보다 작은 경우
if ((v[i] == 1) && (d[i] { // 값 재할당
최소 = d[i];
미니 인덱스 = i;
}
}
// 찾은 최소 가중치 추가
// 현재 정점 가중치
// 현재 최소 정점 가중치와 비교
if (최소 인덱스 != 10000)
{
(int 나는 = 0; 나는 {
만약 (a[i] > 0)
{
온도 = 분 + a[i];
만약 (온도< d[i])
{
d[i] = 온도;
}
}
}
v = 0;
}
) 동안 (최소 인덱스< 10000);
// 정점까지의 최단 거리 표시
printf( "\n정점까지의 최단 거리: \n");
(int 나는 = 0; 나는 printf("%5d", d[i]);

// 경로 복원
반전; // 방문한 정점의 배열
정수 끝 = 4; // 끝 정점 인덱스 = 5 - 1
버전 = 끝 + 1; // 시작 요소 - 끝 정점
정수 k = 1; // 이전 피크의 인덱스
정수 가중치 = d; // 끝 정점 가중치

동안 (끝 != begin_index) // 시작 정점에 도달할 때까지
{
(int 나는 = 0; 나는 // 모든 정점을 본다
만약 (a[i] != 0) // 연결이 있는 경우
{
int temp = 무게 - a[i]; // 이전 정점에서 경로의 가중치를 결정합니다.
if (온도 == d[i]) // 무게가 계산된 무게와 일치하는 경우
{ // 이 정점에서 전환이 있었음을 의미합니다.
무게 = 온도; // 새로운 가중치를 저장
끝 = 나; // 이전 정점을 저장
버전[k] = 나는 + 1; // 배열에 쓰기
k++;
}
}
}
// 경로 표시(시작 정점은 k 요소 배열의 끝에 있음)
printf( "\n최단 경로 출력\n");
(int i = k - 1, i >= 0, i--)
printf("%3d" , 버전[i]);
getchar(); getchar();
반환 0;
}


실행 결과


뒤:

Dijkstra의 알고리즘은 1959년 네덜란드 과학자 E. Dijkstra가 발명한 그래프 알고리즘입니다. 그래프의 정점 중 하나에서 다른 정점까지의 최단 거리를 찾습니다. 알고리즘은 음수 가중치의 간선이 없는 그래프에만 작동합니다. 알고리즘은 다음과 같습니다. 프로그래밍 및 OSPF와 같은 기술에서 널리 사용되는 기술은 이를 사용하여 최단 경로 우선이라고도 하는 루프백 경로를 제거합니다.

Dijkstra의 알고리즘은 모든 간선의 가중치가 음이 아닌((u, v) ? 0 for all (u)인 초기 정점 s가 있는 가중치 유향 그래프 G = (V, E)에 대한 단일 정점 최단 경로 문제를 풉니다. , v) 마). 그래프의 가장자리가 같지 않은 경우 이 알고리즘을 사용하는 것이 좋습니다.

작업 공식화.그래프가 있습니다. 정점 중 일부는 정점 1로 지정됩니다. 정점 1에서 그래프의 각 정점까지의 최소 경로를 찾아야 합니다. 최소 경로는 경로를 따라 가격의 최소 합계가 있는 경로입니다. 가격은 가장자리의 가중치인 음수가 아닌 숫자입니다.

알고리즘의 아이디어.이 아이디어는 다음과 같은 명백한 진술을 기반으로 합니다. 정점에서 최소 경로 ㅏ꼭짓점 B로. 그리고 꼭짓점 B가 몇 개의 꼭짓점 i에 연결되도록 합니다. 정점 B에서 정점 i까지의 경로 비용을 C i로 표시합니다. C i에서 최소값을 선택합시다. 그런 다음 점 B에서 경로의 최소 연속은 선택한 값을 통과합니다.

이 진술은 실제로 증거가 필요하지 않습니다. 그리고 매우 심각한 결과가 뒤따릅니다. 최소한의 경로가 이미 통과하는 정점 집합이 있다고 가정합니다. 그러한 집합은 존재하는 것이 보장되며, 이것은 꼭짓점 1입니다. 위에 공식화된 명령문은 이미 존재하는 꼭짓점 집합에 하나 이상의 꼭짓점을 추가하는 것을 가능하게 합니다. 가 유한한 경우 유한한 수의 단계에서 그래프의 모든 정점이 선택되고 이것이 솔루션이 됩니다.

Dijkstra 알고리즘의 핵심은 선택된 정점 집합에 정점을 하나 더 추가하는 절차입니다. 이 절차는 다음 두 단계로 구성됩니다.

1. 선택된 정점에 해당하는 정점들의 집합을 만들고 그 중에서 가장 낮은 가격의 정점을 찾는다. 찾은 정점이 선택한 정점 세트에 추가됩니다.

2. 선택된 정점에 부수적인 정점 세트를 구성하고 새로운 가격을 결정합니다. 정점의 새로운 가격은 선택된 정점 세트에서 주어진 정점까지의 경로의 최소 비용입니다. 새 가격은 다음과 같이 구성됩니다.

ㅏ. 선택된 정점 세트에서 선택되지 않은 정점에 대해 이 정점에 해당하는 정점의 하위 집합이 결정됩니다.

비. 선택된 부분집합의 각 꼭지점에 대해 주어진 경로의 비용이 결정됩니다.

씨. 최저 가격이 결정됩니다. 이 가격이 최고가가 됩니다.

알고리즘은 가장자리 가격과 최고 가격의 두 가지 유형의 가격으로 작동합니다. 엣지 가격은 일정합니다. 피크 가격은 지속적으로 재계산됩니다. 이 가격의 의미는 다릅니다. 모서리 비용은 정점에서 해당 모서리로 연결된 정점으로 이동하는 비용입니다. 그리고 상단의 가격은 최소 경로의 가격입니다. 또 다른 중요한 사항은 예비 가격의 재계산에 관한 것입니다. 사실, 다른 꼭짓점에 대해서는 예비 가격을 변경할 이유가 없기 때문에 마지막 단계에서 선택된 집합에 추가된 꼭짓점과 관련된 꼭짓점에 대해서만 예비 가격을 다시 계산하는 것이 합리적입니다.

모든 가격(예: 경로 또는 통로 설치)은 음수가 아닌 것으로 알려져 있습니다. 모든 i=1에 대해 최소 비용 경로 1->i를 찾습니다. n O(n2) 시간.

알고리즘이 작동하는 동안 일부 도시가 선택됩니다(처음에는 도시 1만, 끝에서는 모두). 여기서:

각 선택된 도시 i에 대해 경로 1->i의 최소 비용이 저장됩니다. 동시에 선택된 도시만 통과하는 경로에서 최소값에 도달하는 것으로 알려져 있습니다.

할당되지 않은 각 도시 i에 대해 경로 1->i의 최소 비용이 저장되며 선택한 도시만 중간 도시로 사용됩니다.

할당된 도시의 집합은 다음과 같은 말을 기반으로 확장됩니다. 할당되지 않은 모든 도시 중에서 저장된 숫자가 최소인 도시를 선택하면 이 숫자가 진정한 최소 비용입니다. 사실, 더 짧은 방법이 있습니다. 이 경로의 첫 번째 선택되지 않은 도시를 고려하십시오. 경로는 이미 더 깁니다! (여기서 가격의 부정성은 필수적입니다.)

선택한 도시를 선택한 도시에 추가하여 선택하지 않은 도시에 대해 저장된 정보를 수정해야 합니다. 이 경우 새 도시가 마지막 환승 지점인 경로만 고려하면 충분하며 새 도시로 가는 경로의 최소 비용을 이미 알고 있기 때문에 수행하기 쉽습니다.

즉, V의 각 꼭짓점은 레이블과 연결되어 있습니다. 이 꼭짓점에서 a까지의 알려진 최소 거리입니다. 알고리즘은 단계별로 작동합니다. 각 단계에서 하나의 정점을 "방문"하고 레이블을 줄이려고 시도합니다. 모든 정점을 방문하면 알고리즘이 종료됩니다.

초기화. 탑 라벨 ㅏ와 같아야 한다 0 , 나머지 정점의 레이블은 무한대입니다. 이는 다음과 같은 거리를 반영합니다. ㅏ다른 봉우리는 아직 알 수 없습니다. 그래프의 모든 정점은 방문하지 않은 것으로 표시됩니다.

알고리즘 단계. 모든 정점을 방문한 경우 알고리즘이 종료됩니다. 그렇지 않으면 아직 방문하지 않은 정점에서 정점이 선택됩니다. 유최소 레이블 포함. 우리는 가능한 모든 경로를 고려합니다. 유끝에서 두 번째 지점입니다. 꼭짓점에 연결된 꼭짓점 유모서리, 우리는 이 정점의 이웃이라고 부를 것입니다. 각 이웃에 대해 현재 레이블의 합과 동일한 새 경로 길이를 고려합니다. 유연결하는 가장자리의 길이 유이 이웃과 함께. 결과 길이가 인접 레이블보다 작으면 레이블을 이 길이로 바꿉니다. 모든 이웃을 고려한 후 정점을 표시합니다. 유방문하고 단계를 반복합니다.

Dijkstra의 알고리즘은 매번 최단 경로의 가장 작은 추정값으로 정점을 처리하도록 선택하기 때문에 탐욕 알고리즘에 속한다고 말할 수 있습니다.

Dijkstra의 알고리즘이 어떻게 작동하는지 더 자세히 설명하겠습니다.

알고리즘은 각각 N(= 네트워크 꼭짓점의 수) 숫자의 세 가지 배열을 사용합니다. 첫 번째 배열 A에는 0(아직 고려되지 않은 꼭짓점)과 1(이미 고려된 꼭짓점)이라는 두 가지 값이 있는 레이블이 포함됩니다. 두 번째 배열 B는 거리를 포함합니다 - 해당 정점에서 현재 최단 거리. 세 번째 배열 c는 정점의 수를 포함합니다. k번째 요소 C[k]는 Vi에서 Vk까지의 현재 최단 경로에 있는 끝에서 두 번째 정점의 수입니다. 거리 행렬 D는 호 D의 길이를 지정합니다. 그러한 호가 없으면 D에 "기계 무한대"와 같은 큰 숫자 B가 할당됩니다.

이제 다음을 설명할 수 있습니다.

1. (초기화). 1에서 N까지의 주기에서 배열 A를 0으로 채웁니다. 배열 C를 숫자 i로 채우십시오. 행렬 D의 i번째 행을 배열 B로 이동, A [i]: =1; C [i]: =0 (i - 시작 정점 번호)

2. (일반 단계). 표시되지 않은 것 중에서 최소값을 찾으십시오(즉, A [k] =0인 k). 인덱스 j에서 최소값에 도달하도록 하십시오. 비[j]<=B [k] Затем выполняются следующие операции: A [j]: =1; если B [k] >B [j] +D , 그러면 (B [k]: =B [j] +D ; C [k]: =j) (조건은 경로 Vi. Vk가 경로 Vi. Vj Vk보다 더 길다는 것을 의미합니다) . (모든 A [k]가 표시되면 Vi에서 Vk까지의 경로 길이는 B [k]와 같습니다. 이제 우리는) ​​최단 경로에 포함된 정점을 열거해야 합니다).

3. (응답 발행). (Vi에서 Vk까지의 경로는 다음 절차에 따라 역순으로 반환됩니다.)

2. 문제 z;

3. z:=C[z]. z = 0이면 종료하고, 그렇지 않으면 3.2로 이동합니다.

알고리즘을 실행하려면 N 요소의 배열 B를 N 번 스캔해야 합니다. Dijkstra의 알고리즘은 2차 복잡도가 O(n2)입니다.

다음은 Dijkstra 알고리즘의 블록 다이어그램입니다(그림 2 참조).

그림 2. 다익스트라 알고리즘의 순서도

알고리즘을 시작할 때 초기 정점에 대한 거리는 0으로 가정하고 다른 모든 거리는 큰 양수로 채워집니다(그래프에서 가능한 최대 경로보다 큼). 플래그 배열은 0으로 채워집니다. 그런 다음 메인 루프가 시작됩니다.

루프의 각 단계에서 최소 거리와 플래그가 0인 정점을 찾습니다. 그런 다음 플래그를 1로 설정하고 인접한 모든 정점을 확인합니다. 그 거리가 현재 정점까지의 거리와 가장자리 길이의 합보다 크면 줄입니다. 모든 정점의 플래그가 1이 되면 루프가 종료됩니다.

지역의 각 도시로(도로를 따라 이동할 수만 있는 경우).

옵션 2.각각의 비용이 알려져 있기 때문에 세계의 도시들 사이에는 많은 항공편이 있습니다. A에서 B까지의 비행 비용은 B에서 A까지의 비행 비용과 같지 않을 수 있습니다. 코펜하겐에서 Barnaul까지의 최소 비용 경로(환승 가능)를 찾으십시오.

형식적 정의

예시

그림에 표시된 그래프의 예에서 알고리즘의 실행을 고려하십시오.

첫 번째 꼭짓점에서 다른 모든 꼭짓점까지의 최단 거리를 구해야 합니다.

프로그래밍 언어로 구현

C(C) 언어로 실행

#define SIZE 6 #define INF 1000000000 int a [ SIZE ][ SIZE ] = (( INF , 5 , INF , INF , INF , INF ),( 1 , 2 , 3 , 4 , 5 , 6 ), // 경로 행렬 ( 1 , 2 , 3 , 4 , 5 , 6 ),( 1 , 2 , 3 , 4 , 5 , 6 ), // 점에서 수평 인덱스 { 1 , 2 , 3 , 4 , 5 , 6 },{ 1 , 2 , 3 , 4 , 5 , 6 }}; // 수직으로 점, 값 - 가중치정수 d[크기]; // 발견된 최단 경로의 배열, 인덱스 - 그래프 정점 void deikstra () ( int v [ SIZE ]; // 레이블 배열 int temp , i ; int miniindex , min ; for (i = 0 ; i< SIZE ; i ++ ) { d [ i ] = INF ; // 무한대로 초기화된 경로 배열 v[i] = 1; ) d [ 0 ] = 0 ; 하다( // 알고리즘 실행최소 인덱스 = INF ; 최소 = INF ; (나는 = 0 ; 나는< SIZE ; i ++ ) { if ((v [ i ] == 1 ) && (d [ i ] < min )) { min = d [ i ]; minindex = i ; } } if (minindex != INF ) { for (i = 0 ; i < SIZE ; i ++ ) { if (a [ minindex ][ i ] >0 ) ( temp = min + a [ miniindex ][ i ]; if (temp< d [ i ]) d [ i ] = temp ; } } v [ minindex ] = 0 ; } } while (minindex < INF ); }

꼭짓점과 간선이 있는 유향 또는 무향 가중치 그래프가 주어집니다. 모든 간선의 가중치는 음수가 아닙니다. 일부 시작 정점이 지정되었습니다. 꼭짓점에서 다른 모든 꼭짓점까지의 최단 경로 길이를 구해야 하며, 최단 경로 자체를 출력하는 방법도 제공해야 합니다.

이 문제를 단일 소스 최단 경로 문제라고 합니다.

연산

이것은 네덜란드 연구원이 제안한 알고리즘을 설명합니다 다익스트라(다익스트라) 1959년

각 정점에 대해 에서 까지의 최단 경로의 현재 길이를 저장할 배열을 구해 보겠습니다. 처음에 , 그리고 다른 모든 정점에 대해 이 길이는 무한대와 같습니다(컴퓨터에서 구현될 때 일반적으로 충분히 큰 숫자가 무한대로 선택되며 경로의 가능한 길이보다 분명히 큽니다).

또한 각 정점에 대해 여전히 레이블이 지정되었는지 여부를 저장합니다. 부울 배열을 구합시다. 처음에는 모든 정점에 레이블이 지정되지 않습니다.

Dijkstra의 알고리즘 자체는 다음으로 구성됩니다. 반복. 다음 반복에서 아직 레이블이 지정되지 않은 정점 중 값이 가장 작은 정점이 선택됩니다.

(첫 번째 반복에서 시작 정점이 선택될 것이 분명합니다.)

이 방법으로 선택한 정점이 표시됩니다. 또한, 현재 반복에서 정점에서, 기분 전환: 정점에서 나가는 모든 가장자리를 살펴보고 각 정점에 대해 알고리즘은 의 값을 개선하려고 시도합니다. 현재 에지의 길이를 , 코드 형태로 완화하면 다음과 같습니다.

여기에서 현재 반복이 종료되고 알고리즘이 다음 반복으로 진행됩니다(다시 말하지만, 가장 작은 값을 가진 정점이 선택되고, 이완이 수행되는 등). 이 경우 결국 반복 후에 그래프의 모든 정점에 레이블이 지정되고 알고리즘이 작업을 완료합니다. 발견된 값은 에서 까지의 최단 경로에 필요한 길이라고 주장합니다.

그래프의 모든 정점이 정점에서 도달할 수 없는 경우 해당 정점의 값은 무한대로 유지됩니다. 알고리즘의 마지막 몇 번의 반복은 이러한 정점을 선택하지만 이러한 반복은 유용한 작업을 생성하지 않는다는 것이 분명합니다(무한한 거리는 다른 무한한 거리를 완화할 수 없기 때문에). 따라서 거리가 무한한 정점을 선택한 정점으로 취하는 즉시 알고리즘을 중지할 수 있다.

경로 복원. 물론 일반적으로 최단 경로의 길이뿐만 아니라 경로 자체도 알아야 합니다. 임의의 정점에서 최단 경로의 후속 재구성에 충분한 정보를 저장하는 방법을 보여 드리겠습니다. 이를 위해 이른바 조상 배열: 각 꼭짓점에 대해 꼭짓점까지의 최단 경로에서 끝에서 두 번째인 꼭짓점의 번호를 보유하는 배열입니다. 이것은 우리가 어떤 정점에 대한 최단 경로를 취한 다음 이 경로에서 마지막 정점을 제거하면 어떤 정점에서 끝나는 경로를 얻고 이 경로는 정점에 대해 가장 짧다는 사실을 사용합니다. 따라서 이 조상 배열이 있는 경우 시작 정점에 도달할 때까지 현재 정점에서 조상을 가져올 때마다 최단 경로를 복원할 수 있습니다. 이렇게 하면 원하는 최단 경로를 얻을 수 있지만 다음과 같이 작성됩니다. 역순으로. 따라서 정상으로 가는 최단 경로는 다음과 같습니다.

이 조상 배열을 구축하는 방법을 이해하는 것이 남아 있습니다. 그러나 이것은 매우 간단하게 수행됩니다. 각 성공적인 이완, 즉 선택한 정점에서 일부 정점까지의 거리가 개선되면 정점의 조상이 정점이라고 씁니다.

증거

주요 성명, Dijkstra 알고리즘의 정확성의 기반이 되는 은 다음과 같습니다. 정점이 표시된 후에는 정점까지의 현재 거리가 이미 가장 짧으므로 더 이상 변경되지 않는다고 명시되어 있습니다.

증거우리는 유도에 의해 생산할 것입니다. 첫 번째 반복의 경우 유효성이 분명합니다. 정점에 대한 최단 경로의 길이인 가 있습니다. 이제 이 주장이 모든 이전 반복에 대해 유지되도록 하십시오. 이미 표시된 모든 정점; 현재 반복을 실행한 후 위반되지 않았음을 증명합시다. 현재 반복에서 선택된 정점이라고 하자. 알고리즘이 레이블을 지정할 정점입니다. 그것이 최단 경로의 길이와 실제로 같다는 것을 증명합시다(이 길이를 로 표시함).

정상까지의 최단 경로를 고려하십시오. 이 경로는 두 개의 경로로 나눌 수 있음이 분명합니다. 표시된 꼭짓점으로만 구성된(최소한 시작 꼭짓점은 이 경로에 있음) 경로의 나머지 부분(표시된 꼭짓점도 포함될 수 있지만 항상 시작 표시되지 않은 것과 함께). 경로의 첫 번째 꼭짓점과 경로의 마지막 꼭짓점으로 표시합니다.

정점에 대한 우리의 주장을 먼저 증명합시다. 즉, 평등을 증명합시다. 그러나 이것은 거의 분명합니다. 결국 이전 반복 중 하나에서 정점을 선택하고 그로부터 이완을 수행했습니다. (꼭짓점의 선택으로 인해) 최단 경로는 에 대한 최단 경로와 에지를 더한 것과 같으므로 이완이 수행될 때 값은 실제로 필요한 값으로 설정됩니다.

모서리 비용의 음수가 아니므로 최단 경로의 길이(방금 증명된 바에 따르면 같음)는 정점까지의 최단 경로의 길이를 초과하지 않습니다. (결국 Dijkstra의 알고리즘은 일반적으로 가능한 것보다 짧은 경로를 찾을 수 없음) 결과적으로 다음 관계를 얻습니다.

반면에 와 및 는 모두 레이블이 지정되지 않은 꼭짓점이므로 현재 반복에서 선택한 꼭짓점이 아니라 꼭짓점이므로 또 다른 부등식을 얻습니다.

이 두 부등식에서 우리는 평등을 결론짓고 이전에 발견된 관계에서 다음을 얻습니다.

Q.E.D.

구현

따라서 Dijkstra의 알고리즘은 반복으로 구성되며 각 반복에서 가장 작은 값을 가진 레이블이 지정되지 않은 정점이 선택되고 이 정점에 레이블이 지정된 다음 이 정점에서 나가는 모든 가장자리를 살펴보고 각 가장자리를 따라 개선을 시도합니다. 가장자리의 다른 쪽 끝에 있는 값.

알고리즘의 실행 시간은 다음의 합계입니다.

이러한 작업을 가장 간단하게 구현하면 정점을 찾는 데 작업이 사용되고 하나의 이완에 대한 작업이 수행되며 최종 점근론알고리즘은 다음과 같습니다.

구현:

const int INF = 1000000000 ; int main() ( int n; ... n 읽기 ... 벡터< vector < pair< int ,int >> > g(n); ... 그래프 읽기... int s = ...; // 시작 정점벡터< int >d(n, INF) , p(n) ; d[s] = 0; 벡터< char >유(n); for (int i= 0 ; i< n; ++ i) { int v = - 1 ; for (int j= 0 ; j< n; ++ j) if (! u[ j] && (v == - 1 || d[ j] < d[ v] ) ) v = j; if (d[ v] == INF) break ; u[ v] = true ; for (size_t j= 0 ; j< g[ v] .size () ; ++ j) { int to = g[ v] [ j] .first , len = g[ v] [ j] .second ; if (d[ v] + len < d[ to] ) { d[ to] = d[ v] + len; p[ to] = v; } } } }

여기서 그래프는 인접 목록 형식으로 저장됩니다. 각 정점에 대해 목록에는 이 정점에서 나오는 가장자리 목록이 포함됩니다. 쌍의 목록 > 여기서 쌍의 첫 번째 요소는 가장자리가 연결되는 정점이고 두 번째 요소는 가장자리의 가중치입니다.

)는 O(m + n \ln n) 시간에 실행되며 이 클래스의 문제에 대해 점근적으로 가장 빠른 순차 알고리즘으로 알려져 있습니다.

1.2 알고리즘의 수학적 설명

그래프 G = (V, E)가 에지 가중치 f(e)와 고유한 소스 정점 u로 주어졌다고 하자. d(v)는 소스 u에서 정점 v까지의 최단 거리로 나타냅니다.

특정 수 r을 초과하지 않는 모든 거리가 이미 계산되었다고 가정합니다. 즉, 집합에서 정점까지의 거리 V_r = \( v \in V \mid d(v) \le r \). 허락하다

(v, w) \in \arg\min \( d(v) + f(e) \mid v \in V, e = (v, w) \in E \).

그 다음에 d(w) = d(v) + f(e), 그리고 v 는 u 에서 w 까지의 최단 경로에 있습니다.

수량 d^+(w) = d(v) + f(e)여기서 v \in V_r , e = (v, w) \in E 라고 합니다. 예상 거리실제 거리의 상한선: d(w) \le d^+(w) .

각 단계에서 Dijkstra의 알고리즘은 가장 작은 추정 거리를 가진 정점을 찾아 방문한 것으로 표시하고 여기에서 나오는 가장자리의 모든 끝점에 대한 추정 거리를 업데이트합니다.

1.3 알고리즘의 계산 핵심

주요 계산은 우선 순위 대기열의 작업과 관련됩니다.

  • 최소 요소 추출(delete_min);
  • 요소의 우선 순위를 낮춥니다(decrease_key).

1.4 알고리즘의 거시구조

알고리즘 의사 코드:

입력 데이터: 정점이 있는 그래프 V, 가장자리 이자형저울로 에프(이자형); 소스 노드 유. 산출: 거리 디(V) 각 정점에 V ∈ V정상에서 유. 큐 := 새로운우선순위 큐 각각 V ∈ V: 만약에 V = 유 그 다음에 디(V) := 0 또 다른 디(V) := ∞ 큐.끼워 넣다( V, 디(V)) 동안 큐 ≠ ∅: V := 큐.delete_min() 각각 이자형 = (V, 승) ∈ 이자형: 만약에 디(승) > 디(V) + 에프(이자형): 디(승) := 디(V) + 에프(이자형) 큐.감소 키( 승, 디(승))

1.5 순차 알고리즘 구현 방식

Dijkstra 알고리즘의 특정 구현은 사용된 우선 순위 대기열 알고리즘의 선택에 따라 결정됩니다. 가장 간단한 경우에 이것은 배열이나 목록이 될 수 있으며 모든 정점을 볼 필요가 있는 최소값을 검색합니다. 힙을 사용하는 것이 더 효율적입니다. 가장 잘 알려진 복잡성 추정치는 피보나치 힙을 사용하는 변형에 대한 것입니다.

구현 옵션은 초기화 단계가 아니라 처음 방문할 때 큐에 정점을 추가하는 경우 가능합니다.

1.6 알고리즘의 순차 복잡도

알고리즘의 순차 복잡도는 O(C_1 m + C_2n) 입니다. 여기서

  • C_1 – 상단까지의 거리를 줄이기 위한 작업의 수.
  • C_2는 최소 계산을 위한 연산 횟수입니다.

Dijkstra의 원래 알고리즘은 C_1 = O(1) , C_2 = O(n) 인 내부 데이터 구조로 목록을 사용하므로 전체 복잡성은 O(n^2) 입니다.

피보나치 힙을 사용할 때 최소 계산 시간이 C_2 = O(\ln n) 로 줄어들므로 전체 복잡도는 O(m + n \ln n) 이며, 이는 이 클래스의 문제에 대해 점근적으로 가장 잘 알려진 결과입니다.

1.7 정보 그래프

목록 또는 배열에 대한 Dijkstra 알고리즘의 기본 구현에 대한 알고리즘 그래프가 제공됩니다.

그림 1. 입력 및 출력 데이터를 표시하지 않는 알고리즘 그래프. n=3. 비교 작업은 노란색으로 표시되고 정점 레이블 변경 작업은 녹색으로 표시되며 정점 레이블링은 파란색으로 표시됩니다.

1.8 알고리즘 병렬 처리 리소스

Dijkstra의 알고리즘은 계산 볼륨 O(n \ln n + m) 에서 효율적인 병렬화, 평균 실행 시간 O(n^(1/3)\ln n) 을 허용합니다.

첫 번째 추정은 초당 수행된 메모리 액세스(읽기 및 쓰기) 수를 측정하는 daps 특성을 기반으로 합니다. 이 특성은 메모리 작업과 관련된 플롭 추정치와 유사하며 지역 추정치보다 메모리와의 상호 작용 성능 추정치에 가깝습니다. 그러나 다음 cvg 기능에 대한 결과와의 비교를 포함하여 정보의 좋은 소스 역할을 합니다.

그림 6은 오름차순으로 정렬된 공통 알고리즘 구현에 대한 daps 값을 보여줍니다(daps가 많을수록 일반적으로 성능이 향상됨). 메모리 성능이 상당히 낮은 것을 볼 수 있습니다. 그래프를 통한 알고리즘 구현은 액세스 프로필을 분석할 때 본 데이터 액세스의 불규칙성으로 인해 거의 항상 효율성이 낮기 때문에 이는 놀라운 일이 아닙니다.

그림 6. daps 점수 값 비교

두 번째 특성인 cvg는 보다 기계 독립적인 지역 추정치를 제공하기 위한 것입니다. 프로그램이 데이터를 캐시로 가져와야 하는 빈도를 결정합니다. 따라서 cvg 값이 작을수록 수행해야 하는 빈도가 적을수록 지역성이 좋습니다.

그림 7은 내림차순으로 정렬된 동일한 구현 세트에 대한 cvg 값을 보여줍니다(cvg가 작을수록 일반적으로 지역성이 높음). 이 경우 cvg 값은 수행점수와 상관관계가 높으며 낮은 지역성을 반영하고 있음을 알 수 있으며 이는 정성적 지역성 평가 결과와 일맥상통한다.

그림 7. cvg 점수 값 비교

2.3 알고리즘의 병렬 구현의 가능한 방법 및 기능

2.4 알고리즘의 확장성 및 구현

2.4.1 알고리즘의 확장성

2.4.2 알고리즘 구현의 확장성

방법론에 따른 알고리즘의 병렬 구현의 확장성을 연구합시다. 연구는 모스크바 대학 슈퍼컴퓨터 컴플렉스의 로모노소프 슈퍼컴퓨터에서 수행됐다. 알고리즘 구현을 시작하기 위한 변수 매개변수 값의 설정 및 범위:

  • 정수 제곱 값을 가진 프로세서의 수;
  • 16000 단계의 그래프 크기.

다음 그림은 변경 가능한 시작 매개변수에 따라 선택한 알고리즘 구현의 성능 그래프를 보여줍니다.

그림 8. 알고리즘의 병렬 구현. 프로세서의 수와 영역의 크기에 따른 성능의 변화.

알고리즘의 병렬 구현의 특성으로 인해 전체 성능은 상당히 낮고 프로세스 수가 증가함에 따라 천천히 증가하며 프로세스 수(128)에 가까워지면 감소하기 시작합니다. 이것은 알고리즘의 각 반복에서 집합적 작업의 사용과 사용되는 프로세스 수가 증가함에 따라 통신 교환 비용이 크게 증가한다는 사실에 의해 설명됩니다. 각 프로세스에 대한 계산은 매우 빠르므로 그래프 분해는 ​​통신 교환 비용의 영향을 약하게 보상합니다.

2.5 동적 성능 및 알고리즘 구현 효율성

실험에는 Dijkstra 알고리즘의 구현이 사용되었습니다. 모든 결과는 Lomonosov 슈퍼컴퓨터에서 얻었습니다. 최고 성능이 94Gflops인 Intel Xeon X5570 프로세서와 Intel 13.1.0 컴파일러를 사용했습니다. 그림은 32개 프로세스에 대한 Dijkstra 알고리즘 구현의 효율성을 보여줍니다.

그림 9. 다익스트라 알고리즘 실행 시 CPU 부하 그래프

프로세서 부하 그래프는 프로그램이 실행되는 거의 전체 시간 동안 부하 수준이 약 50%임을 보여줍니다. 이는 컴퓨팅 노드당 8개의 프로세스를 사용하고 하이퍼 스레딩을 사용하지 않을 때 프로세서의 균일한 부하를 나타냅니다.

그림 10. Dijkstra 알고리즘을 실행할 때 초당 부동 소수점 연산 도표

그림 10은 초당 부동 소수점 연산의 그래프를 보여줍니다. 그래프는 피크에서 약 250Kflops, 모든 노드에서 평균적으로 약 150Kflops로 전반적으로 매우 열악한 성능을 보여줍니다. 이것은 프로그램의 거의 모든 계산이 정수로 수행됨을 나타냅니다.

write-to-memory 그래프는 계산 불균일성의 유사한 패턴을 보여주며, 동시에 활발히 쓰는 프로세스는 소수에 불과합니다. 이는 다른 실행 일정과 관련이 있습니다. 메모리 쓰기 액세스 수가 다소 적다는 점은 주목할 가치가 있습니다. 이것은 계산의 좋은 구성과 메모리에 대한 상당히 효율적인 작업을 나타냅니다.

그림 15. Dijkstra 알고리즘이 실행 중일 때 Infiniband 네트워크를 통한 전송 속도(바이트/초) 그래프

Infiniband 네트워크 데이터 전송 속도 그래프에는 초당 바이트 단위로 상당히 높은 데이터 전송 속도가 있습니다. 이것은 계산 성능이 높기 때문에 프로세스가 서로 집중적으로 그리고 아마도 아주 작은 부분의 데이터를 교환한다는 것을 암시합니다. 전송 속도가 프로세스 간에 다르기 때문에 계산상의 불균형을 나타냅니다.

그림 16. Dijkstra의 알고리즘이 실행 중일 때 Infiniband 네트워크를 통한 전송 속도 그래프(패킷/초)

초당 패킷 단위의 데이터 전송 속도 그래프에서 데이터 전송 강도가 매우 높습니다. 이것은 아마도 프로세스가 매우 많은 양의 데이터를 교환하지 않고 매우 집중적으로 교환한다는 것을 암시합니다. 이 그림을 설명하는 데이터의 작은 부분과 함께 각 단계에서 집합적 작업이 사용됩니다. 또한 메모리 사용량, 컴퓨팅 및 데이터 전송 바이트/초 그래프에서 볼 수 있는 것보다 프로세스 간의 불균형이 적습니다. 이는 알고리즘에 따라 프로세스가 동일한 수의 패킷을 교환하지만 다른 양의 데이터를 수신하고 고르지 않은 계산을 수행함을 나타냅니다.

그림 17. Dijkstra 알고리즘이 실행 중일 때 계수 단계(Loadavg)에 들어가기 위해 대기 중인 프로세스 수 그래프

계수 단계(Loadavg)에 들어가기 위해 대기 중인 프로세스 수의 그래프는 이 매개변수의 값이 전체 프로그램 작동 동안 일정하며 대략 8과 같다는 것을 보여줍니다. 노드. 이것은 프로세스에 의한 하드웨어 자원의 매우 합리적이고 정적인 로딩을 나타냅니다. 그리고 그것은 수행되는 구현의 상당히 좋은 효율성을 보여줍니다. 일반적으로 프로그램의 시스템 모니터링에 따르면 프로그램이 매우 효율적이고 안정적으로 작동했다고 결론지을 수 있습니다. 메모리 사용량은 매우 집중적이며 통신 미디어 사용량은 매우 집중적이지만 데이터 전송 볼륨은 높지 않습니다. 이것은 프로그램의 알고리즘 부분의 통신 환경 대기 시간의 정확한 특성을 나타냅니다. 낮은 효율성은 각 프로세스에서 전송량이 많고 집중적인 메시지 교환과 관련이 있는 것 같습니다.