На рисунке представлена схема дорог, связывающих города A, B, C, D, E, F, G, H, I. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Какова длина самого длинного пути из города A в город I? Длиной пути считать количество дорог, составляющих этот путь.
При решении будем каждый раз брать конкретную дорогу AB и смотреть, нет ли более длинного пути из A в B (Буквы приведены для примера).
1. Зачеркнём DI т.к. из D в I выгоднее пройти через DH-HI.
2. Зачеркнём DH т.к. из D в H выгоднее пройти через DG-GH.
3. Зачеркнём BG т.к. из B в G выгоднее пройти через GE-ED-DG.
4. Зачеркнём CG т.к. из C в G выгоднее пройти через CE-ED-DG.
5. Зачеркнём CD т.к. из C в D выгоднее пройти через CE-ED.
6. Зачеркнём BE т.к. из B в E выгоднее пройти через BC-CE.
7. Зачеркнём AC т.к. из A в C выгоднее пройти через AB-BC.
8. Зачеркнём AD т.к. из A в D выгоднее пройти через AB-BC-CE-ED.
9. Зачеркнём EF, FI т.к. из E в I выгоднее пройти через ED-DG-GH-HI.
Получаем путь AB-BC-CE-ED-DG-GH-HI длиной 7.