Оптимизация пути в графах с контурами

Для графов с контурами поиск максимального пути затруднён, т.к. он может не существовать. Для отыскания минимального пути существуют разные алгоритмы.

Алгоритм Форда.

Общая постановка задачи:

Задан произвольный связный орграф, каждой дуге которого приписано положительное число. Найти минимальный путь между двумя вершинами графа.

Примечание: Порядковая функция графа не задана.

Решение: Для поиска минимального пути между x₀ и x_n руководствуются следующими правилами:

1. Вершине x₀ приписывается метка l₀ =0. Всем остальным x_i приписывается l_i=¥.

2. Выбирается произвольная дуга x₀®x_i и вершине x_i приписывается метка l_i¢=l₀+l(x₀,x_i), где l(x₀,x_j) - вес дуги между x₀ и x_i.

3. Для вершины x_j с меткой l_j ищется вершина x_i, от которой идёт такая дуга в x_j, что l_j¢ < l_j и где: l_j¢=l_i+l(x_i,x_j).

Вершине x_j приписывается метка l_j¢.

4. После разметки всех вершин графа для произвольной вершины x_j с меткой l_j рассматриваем все вершины x_i с дугами, ведущими в вершину x_j, и выбирается новая метка l_j¢ < l_j и такая, что l_j¢ является минимальной из всех возможных меток.

5. Процедура пункта 4 проводится для каждой вершины графа возможно и не один раз, пока не будут получены минимальные метки у каждой вершины графа.

6. Выбор минимального пути осуществляют по правилам получения минимального пути для графа без контуров.