Поиск самого длинного пути в ориентированном графе (страница 2)

При решении будем каждый раз брать конкретную дорогу 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.

Ответ: 6

При решении будем каждый раз брать конкретную дорогу AB и смотреть, нет ли более длинного пути из A в B (Буквы приведены для примера).

1. Заметим, что через середину идти совсем невыгодно, зачеркнём все дороги оттуда.

2. Также заметим дорогу LN, делающую левое направление более выгодным. Зачеркнём все дороги справа.

3. Зачеркнём OQ т.к. из O в Q выгоднее пройти через OP-PQ.

4. Зачеркнём LM т.к. из L в M выгоднее пройти через LN-NM.

Получаем путь AB-BE-EI-IO-OP-PQ-QL-LN-NM длиной 9.

Ответ: 9

При решении будем каждый раз брать конкретную дорогу AB и смотреть, нет ли более длинного пути из A в B (Буквы приведены для примера).

1. Зачёркиваем EH, потому что выгоднее пройти по EF-FH или EG-GH.

2. Зачёркиваем DF и CE потому что выгоднее пройти по CD-DE-EF.

3. Зачёркиваем BE и DG потому что выгоднее пройти по BD-DE-EG.

3. Зачёркиваем AD потому что выгоднее пройти по AC-CD или AB-BD.

Теперь нам не важно, пойдём мы по AB или по AC. По EG или по EF. Длина всегда будет одинакова и равна 5. Для примера возьмём путь AC-CD-DE-EF-FH.

Ответ: 5

При решении будем каждый раз брать конкретную дорогу AB и смотреть, нет ли более длинного пути из A в B (Буквы приведены для примера).

1. Зачеркнём FI т.к. из F в I выгоднее пройти через FH-HI или FG-GI.

2. Зачеркнём DF т.к. из D в F выгоднее пройти через DE-EF.

3. Зачеркнём JE, JF т.к. из J в F выгоднее пройти через JC-CD-DE-EF.

4. Зачеркнём JC т.к. из J в C выгоднее пройти через JB-BC.

5. Зачеркнём AB т.к. из A в B выгоднее пройти через AJ-JB.

6. Зачеркнём очевидно невыгодные дороги AK, KE.

Получаем путь AJ-JB-BC-CD-DE-EF-FG-GI длиной 8.

Ответ: 8

При решении будем каждый раз брать конкретную дорогу AB и смотреть, нет ли более длинного пути из A в B (Буквы приведены для примера).

1. Зачеркнём CF, CE, DF т.к. из C в F выгоднее пройти через CD-DE-EF.

2. Зачеркнём AD, AC т.к. из A в D выгоднее пройти через AB-BC-CD.

3. Зачеркнём очевидно невыгодные дороги AG, GE.

Получаем путь AB-BC-CD-DE-EF длиной 5.

Ответ: 5

При решении будем каждый раз брать конкретную дорогу AB и смотреть, нет ли более длинного пути из A в B (Буквы приведены для примера).

1. Зачеркнём очевидно невыгодный путь AE.

2. Зачеркнём DE т.к. выгоднее пройти через DF-FE.

3. Зачеркнём AD, AC т.к. выгоднее пройти через AB-BC-CD.

4. Зачеркнём AF, AG т.к. выгоднее пройти через AH-HG-GF.

5. Зачеркнём AH т.к. выгоднее пройти через AB-BH.

6. Зачеркнём BC т.к. выгоднее пройти через BH-HG-GC.

7. Зачеркнём GF т.к. выгоднее пройти через GC-CD-DF.

Получаем путь AB-BH-HG-GC-CD-DF-FE-EI длиной 8.

Ответ: 8

При решении будем каждый раз брать конкретную дорогу AB и смотреть, нет ли более длинного пути из A в B (Буквы приведены для примера).

1. Зачеркнём очевидно невыгодный путь BF.

2. Нужно заметить, что выгоднее всего будет пройти через вертикальную дорогу DH.

Зачеркнём ненужные дороги и получим путь AB-BC-CD-DH-HI-IF-FJ длиной 7.

Ответ: 7