На рисунке представлена схема дорог, связывающих города A, I, B, C, D, F, G, E, H, J, K, L. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Какова длина самого длинного пути из города A в город L? Длиной пути считать количество дорог, составляющих этот путь.
При решении будем каждый раз брать конкретную дорогу AB и смотреть, нет ли более длинного пути из A в B (Буквы приведены для примера).
1. Зачеркнём KL т.к. из K в L выгоднее пройти через KJ-JL.
2. Зачеркнём HJ, HL т.к. из H в L выгоднее пройти через HK-KJ-JL.
3. Зачеркнём EH т.к. из E в H выгоднее пройти через EG-GH.
4. Зачеркнём FH т.к. из F в H выгоднее пройти через FG-GH.
5. Зачеркнём DG т.к. из D в G выгоднее пройти через DE-EG или через DF-FG.
6. Зачеркнём CE т.к. из C в E выгоднее пройти через CD-DE.
7. Зачеркнём BF т.к. из B в F выгоднее пройти через BD-DF.
8. Зачеркнём AD, AC, CD, AB т.к. из A в D выгоднее пройти через AI-IB-BD.
9. Зачеркнём EF, FI т.к. из E в I выгоднее пройти через ED-DG-GH-HI.
Получаем путь AI-IB-BD-DE-EG-GH-HK-KJ-JL длиной 9.