На рисунке представлена схема дорог, связывающих города A, K, I, H, G, F, B, C, E, J, D. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Какова длина самого длинного пути из города A в город D? Длиной пути считать количество дорог, составляющих этот путь.
При решении будем каждый раз брать конкретную дорогу AB и смотреть, нет ли более длинного пути из A в B (Буквы приведены для примера).
1. Зачеркнём CD т.к. из C в D выгоднее пройти через CJ-JD.
2. Зачеркнём EJ т.к. из E в J выгоднее пройти через EC-CJ.
3. Зачеркнём FC т.к. из F в C выгоднее пройти через FE-EC.
4. Зачеркнём AK, KG т.к. из A в G выгоднее пройти через AI-IH-HG.
5. Зачеркнём IF, HF т.к. из I в F выгоднее пройти через FH-HG-GF.
6. Зачеркнём AB, BC т.к. из A в C выгоднее пройти через AI-IH-HG-GF-FE-FC.
Получаем путь AI-IH-HG-GF-FE-EC-CJ-JD длиной 8.