На рисунке представлена схема дорог, связывающих города A, F, E, C, G, I, K, M, T, L, J. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Какова длина самого длинного пути из города A в город J? Длиной пути считать количество дорог, составляющих этот путь.
При решении будем каждый раз брать конкретную дорогу AB и смотреть, нет ли более длинного пути из A в B (Буквы приведены для примера).
1. Зачеркнём TJ т.к. из T в J выгоднее пройти через TL-LJ.
2. Зачеркнём TL т.к. из T в L выгоднее пройти через TK-KL.
3. Зачеркнём IK т.к. из I в K выгоднее пройти через IT-TK.
4. Зачеркнём IT т.к. из I в T выгоднее пройти через IM-MT.
5. Зачеркнём IJ т.к. из I в J выгоднее пройти через IM-MT-TK-KL-LJ.
6. Зачеркнём AF т.к. из A в F выгоднее пройти через AE-EF.
7. Зачеркнём EC т.к. из E в C выгоднее пройти через EF-FC.
8. Зачеркнём AC т.к. из A в C выгоднее пройти через AE-EF-EC.
9. Зачеркнём AI т.к. из A в I выгоднее пройти через AE-EF-EC-CG-GI.
Получаем путь AE-EF-FC-CG-GI-IM-MT-TK-KL-LJ длиной 10.