Question

Между населенными пунктами a, b, c, d, e, f построены дороги, протяжённость которых
(в километрах) в таблице.
определите длину кратчайшего пути между пунктами а и f, проходящего через пункт с.
передвигаться можно только по дорогам, протяжённость которых указана в таблице.
с !

Answer 1

В общую длину пути будет входить длина дороги AC = 10

Длина пути напрямую из C в F (CF) = 8.

Нам нужно проверить, если ли смысл ехать в другой нас. пункт из C, чтоб сократить общий путь.

Варианты, где расстояние из C в другой нас. пункт больше или равно CF отбрасываем. У нас остаются:

CB = 6CD = 2CE = 5

Теперь проверим, из какого из этих пунктов расстояние в F не превышает расстояние CF - 8.

BF = 1DF = 4EF = 0

Подсчитаем общий размер пути, который нужно преодолеть с самого начала и найдем наименьший

ACF   = 10 + 8 =       18ACBF = 10 + 6 + 1 = 17ACDF = 10 + 2 + 4 = 16ACEF = 10 + 5 + 0 = 15

Длина кратчайшего пути между пунктами А и F, проходящая через пункт С = 15 (ACEF).