На рисунке представлена схема дорог, связывающих города A, B, C, D, E, F, G, H, K, J, I. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Какова длина самого длинного пути из города А в город I? Длиной пути считать количество дорог, составляющих этот путь.
При решении будем каждый раз брать конкретную дорогу AB и смотреть, нет ли более длинного пути из A в B (Буквы приведены для примера).
1. Зачеркнём FI т.к. из F в I выгоднее пройти через FH-HI или FG-GI.
2. Зачеркнём DF т.к. из D в F выгоднее пройти через DE-EF.
3. Зачеркнём JE, JF т.к. из J в F выгоднее пройти через JC-CD-DE-EF.
4. Зачеркнём JC т.к. из J в C выгоднее пройти через JB-BC.
5. Зачеркнём AB т.к. из A в B выгоднее пройти через AJ-JB.
6. Зачеркнём очевидно невыгодные дороги AK, KE.
Получаем путь AJ-JB-BC-CD-DE-EF-FG-GI длиной 8.