Волновой алгоритм построения длиннейшего пути

Во взвешенном графе

Используется волновой алгоритм построения кратчайшего пути для взвешенного графа со следующими отличиями.

1. В п. 1 волнового алгоритма построения кратчайшего пути присваиваем всем вершинам вес 0, тогда автоматически будут строиться длиннейшие пути.

2. В п. 2 алгоритма полагаем .

Пример 3.3. Найти длиннейший путь в графе (рис. 3.3) между вер-

Рассмотрим краткое решение этой задачи. 1. Результаты прямого прохода алгоритма приведены в табл. 3.4.   2. Обратный ход:

шинами x_н и x_к, используя волновой алгоритм.

Таблица 3.4

x1	x2	x3	x4	x5	x6	M
						2,3
						3,4
						4,5
						5,6
						Æ

 

Дуги-претенденты: (x₁ x₂), (x₁ x₃), (x₂ x₄),(x₃ x₄),(x₃ x₅), (x₄ x₆), (x₅ x₆).

3. Построены три длиннейшие пути:

L₁: (x₁ x₂), (x₂ x₄), (x₄ x₆); L₂: (x₁ x₃), (x₃ x₄), (x₄ x₆);L₃: (x₁ x₃), (x₃ x₅), (x₅ x₆).