На рисунке представлена схема дорог, связывающих города A, B, C, E, D, H, G, F, I, J, K. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Какова длина самого длинного пути из города A в город K? Длиной пути считать количество дорог, составляющих этот путь.
При решении будем каждый раз брать конкретную дорогу AB и смотреть, нет ли более длинного пути из A в B (Буквы приведены для примера).
1. Зачеркнём GJ, GK, IK т.к. из G в K выгоднее пройти через GI-IJ-JK.
2. Зачеркнём FJ т.к. из F в J выгоднее пройти через FG-GI-IJ.
3. Зачеркнём HI т.к. из H в I выгоднее пройти через HG-GI.
4. Зачеркнём DG т.к. из D в G выгоднее пройти через DF-FG или через DH-HG.
5. Зачеркнём AE т.к. из A в E выгоднее пройти через AB-BE.
6. Зачеркнём AC т.к. из A в C выгоднее пройти через AB-BC.
Теперь у нас есть много различных путей с одинаковой длиной 7. Выберем например AB-BE-EF-FG-GI-IG-GK