85a8740c29d2479d98851e671efcba93

1.

ТАБЛИЦЫ И ГРАФЫ
Таблица «Схема дорог»
Взвешенный граф
90
80
C
D
70
60
B
E
50
A
90
A
B
A
50
B
50
90
90
80
60
80
70
60
70
C
D
E
90
C
D
E
90
Если между парой населённых пунктов существует дорога, то в ячейку на
пересечении соответствующих строки и столбца записывается число, равное
её длине. Пустые клетки в таблице означают, что дорог между
соответствующими населёнными пунктами нет.

2.

ПОИСК КРАТЧАЙШЕГО ПУТИ
Между населёнными пунктами A, B, C, D, E построены дороги,
протяжённость которых (в километрах) приведена в таблице.
Определите длину кратчайшего пути между пунктами A и Е.
Передвигаться можно только по дорогам, протяжённость которых
указана в таблице. Каждый пункт можно посетить только один раз.

3.

ПОИСК КРАТЧАЙШЕГО ПУТИ
Между населёнными пунктами A, B, C, D, E построены дороги,
протяжённость которых (в километрах) приведена в таблице.
Определите длину кратчайшего пути между пунктами A и Е.
Передвигаться можно только по дорогам, протяжённость которых
указана в таблице. Каждый пункт можно посетить только один раз.
А
B
C
C
D
B
D
D
E
D
E
E
E
D
B
E
E
C
C
B

4.

ПОИСК КРАТЧАЙШЕГО ПУТИ
1
2
B
2
5
4
B
D
3
2
5
2
D
E
D
E
8
2
9
8
E
D
7
2
E
C
E
3
D
E
3
C
C
2
А
B
C
B
13
Ответ: длина кратчайшего пути между пунктами A и Е равна 5.
7
5

5.

ПОИСК КРАТЧАЙШЕГО ПУТИ
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в
километрах) приведена в таблице. Определите длину кратчайшего пути между
пунктами A и Е, проходящего через пункт С. Передвигаться можно только по дорогам,
протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
1
B
2
C
D
3
D
Ответ: длина кратчайшего
пути между пунктами A и Е,
проходящего через С, равна 8.
2
E
2
4
C
D
5
2
D
E
2
9
E
8
13
D
E
3
B
E
А
B
E
C
C
B

6.

ПОИСК КРАТЧАЙШЕГО ПУТИ
Между населёнными пунктами A, B, C, D, E построены дороги,
протяжённость которых (в километрах) приведена в таблице.
Определите длину кратчайшего пути между пунктами A и Е,
не проходящего через пункт С. Передвигаться можно только
по дорогам, протяжённость которых указана в таблице. Каждый
пункт можно посетить только один раз.

7.

ПОИСК КРАТЧАЙШЕГО ПУТИ
Чему равна длина кратчайшего пути между пунктами
A и Е?
1
5
D
Ответ: длина кратчайшего
пути между пунктами A и Е,
не проходящего через С,
равна 5.
2
E
8
А
7
3
B
D
B
2
E
E
7
5

8.

ВОПРОСЫ И ЗАДАНИЯ
Таблица стоимости перевозок устроена следующим образом: числа,
стоящие на пересечениях строк и столбцов таблиц, означают стоимость
проезда между соответствующими соседними станциями.
Если пересечение строки и столбца пусто, то станции не являются
соседними. Стоимость проезда по маршруту складывается из стоимостей
проезда между соседними станциями. Перевозки между населёнными
пунктами A, B, C, D, F осуществляют три компании, представившие
стоимость своих услуг в табличной форме. Какая компания обеспечивает
минимальную стоимость проезда из А в B?
A
A
1)
B
C
3
D
1
E
B
C
D
3
1
E
A
4
2
4
2
2
3
A
2)
B
B
C
3
D
1
E
1
C
D
E
3
1
1
4
4
2
2
A
A
3)
B
B
C
3
D
1
E
4
C
D
E
3
1
4
4
2
4
2
2
2