Между населёнными пунктами A, B, C, D, E, F построены дороги, протяженность которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)
Определит длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам).
Попасть в п.F можно:
С -> F - 4 км
D -> F - 3 км
E -> F - 2 км
Отрабатываем кратчайший путь (Е -> F):
Как попасть в п.E: D -> E - 1 км; B -> E - 8 км
Как попасть в п.D: C -> D - 3 км
Дорога C -> D -> E отпадает, так как на 1 километр короче попасть в пункт F по дороге: D -> F - 3 км.
Вариант с дорогой D отпадает, так как чтобы попасть в С, нужно проехать 8 км.
Отрабатываем вариант C -> F:
A -> C - 8 км; С -> F - 4 км. Получается: A -> C -> F - 12 км.
использовать Чертежник
алг буквы
нач
е
п
б
ч
ц
ш
кон
алг е
нач
опустить перо
сместиться на вектор (2,0)
сместиться на вектор (-2,0)
сместиться на вектор (0,2)
сместиться на вектор (2,0)
сместиться на вектор (-2,0)
сместиться на вектор (0,2)
сместиться на вектор (2,0)
поднять перо
сместиться на вектор (1,-4)
кон
алг п
нач
опустить перо
сместиться на вектор (0,4)
сместиться на вектор (2,0)
сместиться на вектор (0,-4)
поднять перо
сместиться на вектор (1,0)
кон
алг б
нач
опустить перо
сместиться на вектор (2,0)
сместиться на вектор (0,2)
сместиться на вектор (-2,0)
сместиться на вектор (0,-2)
сместиться на вектор (0,4)
сместиться на вектор (2,0)
поднять перо
сместиться на вектор (1,0)
кон
алг ч
нач
опустить перо
сместиться на вектор (0,-2)
сместиться на вектор (2,0)
сместиться на вектор (0,2)
сместиться на вектор (0,-4)
поднять перо
сместиться на вектор (1,4)
кон
алг ц
нач
опустить перо
сместиться на вектор (0,-4)
сместиться на вектор (2,0)
сместиться на вектор (0,4)
сместиться на вектор (0,-4)
сместиться на вектор (1,0)
сместиться на вектор (0,-1)
поднять перо
сместиться на вектор (1,5)
кон
алг ш
нач
опустить перо
сместиться на вектор (0,-4)
сместиться на вектор (1,0)
сместиться на вектор (0,4)
сместиться на вектор (0,-4)
сместиться на вектор (1,0)
сместиться на вектор (0,4)
кон
3) 12
Объяснение:
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяженность которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)
Определит длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам).
Попасть в п.F можно:
С -> F - 4 км
D -> F - 3 км
E -> F - 2 км
Отрабатываем кратчайший путь (Е -> F):
Как попасть в п.E: D -> E - 1 км; B -> E - 8 км
Как попасть в п.D: C -> D - 3 км
Дорога C -> D -> E отпадает, так как на 1 километр короче попасть в пункт F по дороге: D -> F - 3 км.
Вариант с дорогой D отпадает, так как чтобы попасть в С, нужно проехать 8 км.
Отрабатываем вариант C -> F:
A -> C - 8 км; С -> F - 4 км. Получается: A -> C -> F - 12 км.
Это кратчайший путь.