Розбір завдання A2 (демо ЄДІ 2012)

Між населеними пунктами A, B, C, D, E, F побудовано дороги, довжина яких наведена у таблиці. (Відсутність числа у таблиці означає, що прямої дороги між пунктами немає.)

Визначте довжину найкоротшого шляху між пунктами A і F (за умови, що пересуватися можна лише збудованими дорогами).

Зобразимо з допомогою графа дані таблиці. Крапками позначимо населені пункти. Там, де пункти з'єднані дорогою, з'єднуємо точки.

Намалюємо шлях з пункту А до F. Почнемо з кінця, з пункту F. До нього йде дорога з Е:

До пункту Е ведуть дороги з D, C і B:

У пункт D веде дорога із С, у пункт С веде дорога із В, у пункт В веде дорога із А:

До пункту С веде дорога з В, до пункту В веде дорога з А:

До пункту В веде дорога з А:

Бачимо, що з А в F веде 3 шляхи. Треба знайти найкоротший шлях із трьох. Додамо до графа значення відстаней між пунктами:

1-й шлях: A-B-C-D-E-F=2+1+3+3+2=11

2-й шлях: A-B-C-E-F=2+1+4+2=9

3-й шлях: A-B-E-F=2+7+2=11

Отримали найкоротший шлях: A-B-C-E-F. Його довжина дорівнює 9 .