Кратчайший маршрут. Алгоритмизация и программирование. Язык С++, 11 класс

1. Кратчайший маршрут

Алгоритмизация и программирование. Язык C++, 11 класс
1
Кратчайший маршрут
Алгоритм Дейкстры (1960):
B
2
4
R
P
C
B
2
A
C
4
A
D
8
9
A
A
0
×
7
1
D
A
E
A
1
3
E
F
2
Э.В. Дейкстра
F
кратчайшее расстояние
A откуда ехать
ближайшая от A
невыбранная вершина
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

2. Кратчайший маршрут

Алгоритмизация и программирование. Язык C++, 11 класс
2
Кратчайший маршрут
Алгоритм Дейкстры (1960):
B
2
4
A
0
×
B
2
A
W[x,z]
X
C
C
4
A
Z
W[x,y]
К.Ю. Поляков, Е.А. Ерёмин, 2014
D
8
9
A
R
P
7
1
D
9
A
B
E
A
W[z,y]
Y
1
3
E
F
2
Э.В. Дейкстра
F
кратчайшее расстояние
A откуда ехать
может быть так, что
W[x,z] + W[z,y] < W[x,y]
http://kpolyakov.spb.ru

3. Кратчайший маршрут

Алгоритмизация и программирование. Язык C++, 11 класс
3
Кратчайший маршрут
Алгоритм Дейкстры (1960):
B
2
4
A
0
×
B
2
A
W[x,z]
X
C
C
4
A
Z
W[x,y]
К.Ю. Поляков, Е.А. Ерёмин, 2014
D
8
9
A
R
P
7
1
D
9
B
E
5
A
C
W[z,y]
Y
1
3
E
F
2
Э.В. Дейкстра
F
кратчайшее расстояние
A откуда ехать
может быть так, что
W[x,z] + W[z,y] < W[x,y]
http://kpolyakov.spb.ru

4. Кратчайший маршрут

Алгоритмизация и программирование. Язык C++, 11 класс
4
Кратчайший маршрут
Алгоритм Дейкстры (1960):
B
2
4
R
P
B
2
A
C
C
4
A
D
8
9
A
A
0
×
7
1
D
9
8
B
E
E
5
C
1
3
E
F
2
Э.В. Дейкстра
F
7 кратчайшее расстояние
E откуда ехать
! При рассмотрении вершин F и D
таблица не меняется!
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

5. Кратчайший маршрут

Алгоритмизация и программирование. Язык C++, 11 класс
5
Кратчайший маршрут
R
P
A
0
×
B
2
A
C
4
A
D
8
E
E
5
C
F
7
E
длины кратчайших
маршрутов из A в
другие вершины
? Как найти сам маршрут?
R
P
A
0
×
B
2
A
C
4
A
D
8
E
E
5
C
F
7
E
A C E F
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

6. Алгоритм Дейкстры

Алгоритмизация и программирование. Язык C++, 11 класс
6
Алгоритм Дейкстры
Данные:
const int N = 6;
int W[N][N];
// весовая матрица
bool active[N]; // вершина не выбрана?
int R[N], P[N];
int i, j, min, kMin;
Начальные значения (выбор начальной вершины):
for ( i = 0; i < N; i ++ ) {
active[i] = true; // все вершины не выбраны
R[i] = W[0][i];
// рёбра из вершины 0
P[i] = 0;
}
active[0] = false; // вершина уже выбрана
P[0] = -1;
// это начальная вершина
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

7. Алгоритм Дейкстры

Алгоритмизация и программирование. Язык C++, 11 класс
7
Алгоритм Дейкстры
Основной цикл:
выбор следующей
for ( i = 0; i < N-1; i++ ) {
вершины,
ближайшей к A
minDist = 99999;
for ( j = 0; j < N; j ++ )
if ( active[j] && R[j] < minDist) {
minDist = R[j];
kMin = j;
проверка
маршрутов через
}
вершину kMin
active[kMin] = false;
for ( j = 0; j < N; j ++ )
if ( R[kMin]+W[kMin][j] < R[j] ) {
R[j] = R[kMin] + W[kMin][j];
P[j] = kMin;
}
}
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

8. Алгоритм Дейкстры

Алгоритмизация и программирование. Язык C++, 11 класс
8
Алгоритм Дейкстры
Вывод результата (маршрут 0 N-1):
i = N-1;
для начальной
while ( i != -1 )
вершины P[i]=-1
{
cout << i << " ";
i = P[i]; // к следующей вершине
}
R
P
A
0
×
B
2
A
C
4
A
D
8
E
E
5
C
F
7
E
A C E F
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

9. Алгоритм Флойда

Алгоритмизация и программирование. Язык C++, 11 класс
9
Алгоритм Флойда
Все кратчайшие пути (из любой вершины в любую):
for ( k = 0; k < N; k++ )
for ( i = 0; i < N; i++ )
for ( j = 0; j < N; j++ )
if ( W[i][k]+W[k][j] < W[i][j] )
W[i][j] = W[i][k] + W[k][j];
K
W[i,k]
I
W[k,j]
W[i,j]
J
? Как найти сам маршрут?
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

10. Алгоритм Флойда + маршруты

Алгоритмизация и программирование. Язык C++, 11 класс
10
Алгоритм Флойда + маршруты
Дополнительная матрица:
for ( i = 0; i < N; i++ ) {
for ( j = 0; j < N; j++ )
P[i][j] = i;
P[i][i] = -1;
}
Кратчайшие длины путей и маршруты:
for ( k = 0; k < N; k++ )
for ( i = 0; i < N; i++ )
for ( j = 0; j < N; j++ )
if ( W[i][k] + W[k][j] < W[i][j] ) {
W[i][j] = W[i][k] + W[k][j];
P[i][j] = P[k][j];
}
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

11. Конец фильма

Алгоритмизация и программирование. Язык C++, 11 класс
11
Конец фильма
ПОЛЯКОВ Константин Юрьевич
д.т.н., учитель информатики
ГБОУ СОШ № 163, г. Санкт-Петербург
[email protected]
ЕРЕМИН Евгений Александрович
к.ф.-м.н., доцент кафедры мультимедийной
дидактики и ИТО ПГГПУ, г. Пермь
[email protected]
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru