Задание 4. Формальные описания реальных объектов и процессов

Задание 4. Формальные описания реальных объектов и процессов (открытый банк заданий ФИПИ)

Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.

http://ege.fipi.ru/os11/docs/B9ACA5BBB2E19E434CD6BEC25284C67F/questions/03752BADA252AFCB4996F3609E93B627/img335965n0.gif

Определите длину кратчайшего пути между пунктами A и F при условии, что передвигаться можно только по указанным в таблице дорогам.

Решение:

Попробуем начертить схему (граф) городов, и соединим их дорогами согласно таблице.

Вот такой граф:

После того как мы нарисовали граф, пытаемся эмпирическим (экспериментальным ) путем найти самое короткое расстояние между городами А и F.

После долгих экспериментов (перебирая, все возможные пути) находим самый короткий

A–C–D–E–F =12 км