Кратчайший путь в графе

1.

Задание №4
Кратчайший путь в графе
Никифоров Николай Сергеевич
МБОУ СОШ №26 г. Сургут
http://online.fizinfo.ru
[email protected]

2.

№1 (Демоверсия ФИПИ – 2020)
Между населёнными пунктами A, B, C, D, E
построены дороги, протяжённость которых
(в километрах) приведена в таблице.
Определите длину кратчайшего пути между
пунктами A и E, проходящего через пункт C.
Передвигаться можно только по дорогам,
протяжённость которых указана в таблице.
Решение:
Решение:
1 способ:
Строим дерево.
2 способ:
Строим граф.
Ответ: 8

3.

№2 (СтатГрад – октябрь 2019)
Между населёнными пунктами A, B, C, D, E
построены дороги, протяжённость которых
приведена в таблице.
Определите длину кратчайшего пути между
пунктами A и B, проходящего через пункт D.
Передвигаться можно только по дорогам,
указанным в таблице.
Решение:
Решение:
1 способ:
Строим дерево.
2 способ:
Строим граф.
Ответ: 3

4.

№3 (СтатГрад – октябрь 2019)
Между населёнными пунктами A, B, C, D, E
построены дороги, протяжённость которых
приведена в таблице.
Определите длину кратчайшего пути между
пунктами A и E, проходящего через пункт D.
Передвигаться можно только по дорогам,
указанным в таблице.
Решение:
Решение:
1 способ:
Строим дерево.
2 способ:
Строим граф.
Ответ: 10

5.

№4 (СтатГрад – ноябрь 2019)
Между населёнными пунктами A, B, C, D, E, F
построены дороги, протяжённость которых (в
километрах) приведена в таблице.
Определите длину кратчайшего пути между
пунктами A и F. Передвигаться можно только
по дорогам, указанным в таблице.
Решение:
Решение:
1 способ:
Строим дерево.
2 способ:
Строим граф.
Ответ: 13

6.

№5 (СтатГрад – ноябрь 2019)
Между населёнными пунктами A, B, C, D, E, F
построены дороги, протяжённость которых (в
километрах) приведена в таблице.
Определите длину кратчайшего пути между
пунктами A и F. Передвигаться можно только
по дорогам, указанным в таблице.
Решение:
Решение:
1 способ:
Строим дерево.
2 способ:
Строим граф.
Ответ: 11