На рисунке представлена схема дорог, связывающих города A, B, C, D, E, F, G, I, H. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Какова длина самого длинного пути из города А в город J? Длиной пути считать количество дорог, составляющих этот путь.
При решении будем каждый раз брать конкретную дорогу AB и смотреть, нет ли более длинного пути из A в B (Буквы приведены для примера).
1. Вместо FJ можем пройти по FH-HJ. Зачёркиваем FJ.
2. Вместо FH-HJ и FI-IJ можем пройти по FH-HI-IJ. Зачёркиваем HJ, FI.
3. Вместо GI выгоднее пройти по GF. Зачёркиваем GI.
4. Вместо EH выгоднее пройти по EF. Зачёркиваем EH.
5. Зачёркиваем BF, потому что выгоднее пройти по BG-GF или BE-EF.
6. Зачёркиваем DG потому что выгоднее пройти по DB-BG.
7. Зачёркиваем CE потому что выгоднее пройти по CB-BE.
8. Зачёркиваем AC, CB, AB, AD, потому что выгоднее пройти по AK-KD-DB.
Наш самый выгодный путь – AK-KD-DB-BG-GF-FH-HI-IJ, длина которого равна 8.