На рисунке представлена схема дорог, связывающих города A, B, C, D, E, F, H, I, G. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Какова длина самого длинного пути из города A в город G? Длиной пути считать количество дорог, составляющих этот путь.
При решении будем каждый раз брать конкретную дорогу AB и смотреть, нет ли более длинного пути из A в B (Буквы приведены для примера).
1. Зачеркнём FG т.к. из F в G выгоднее пройти через FI-IG.
2. Зачеркнём EG т.к. из E в G выгоднее пройти через EF-FI-IG.
3. Зачеркнём CF, CG т.к. из C в G выгоднее пройти через CE-EF-FI-IG.
4. Зачеркнём HI т.к. из H в I выгоднее пройти через HF-FI.
5. Зачеркнём DH, HF т.к. из D в G выгоднее пройти через DC-CE-EF-FI-IG.
Получаем путь AD-DC-CE-EF-FI-IG длиной 6.