Все материалы, размещенные на этой страничке украдены с других сайтов. Владельцев авторских и прочих прав прошу меня простить.

Граф G задается множеством точек (вершин) х₁, х₂,..., х_n. (которое обозначается через Х) и множеством линий (ребер) а₁, а₂,...,а_m. (которое обозначается символом А), соединяющих между собой все или часть этих точек. Таким образом, граф G полностью задается (и обозначается) парой (Х, А). Если ребра из множества А ориентированы, что обычно показывается стрелкой, то они называются дугами, и граф с такими ребрами называется ориентированным графом, .
    Например, если дорога имеет не двух-, а одностороннее движение то направление этого движения будет показано стрелкой.
    Если ребра не имеют ориентации, то граф называется неориентированным , (двухстороннее движение).
    В ориентированном графе дуга обозначается упорядоченной парой, состоящей из начальной и конечной вершин (т.е. двумя концевыми вершинами дуги), ее направление предполагается заданным от первой вершины ко второй. Так, например, на рис. 2 обозначение (х₁ ,х₃) относится к дуге а₁.
    Другое, употребляемое чаще описание ориентированного графа G состоит в задании множества вершин Х и соответствия Г, которое показывает как между собой связаны вершины. Соответствие Г называется отображением множества Х в Х, а граф в этом случае обозначается парой G=(Х, Г). Так, например, для графа на рис. 2:
    Г (х₁)={х₂, х₃}, т.е. вершины х₂ и х₃ являются конечными вершинами дуг, у которых начальной вершиной является вершина х₁.
    На рис. 3: Г (х₁)={х₂, х₄, х₅}, (неориентированное ребро представляется как две противоположно направленные дуги, соединяющие те же самые вершины.)
   Путем (или ориентированным маршрутом) ориентированного графа называется последовательность дуг, в которой конечная вершина всякой дуги, отличной от последней, является начальной вершиной следующей.
Так, на рис. 5 последовательности дуг

а₆, а₅, а₉, а₈, а₄. (1)
а₁, а₆, а₅, а₉. (2)
а₁, а₆, а₅, а₉, а₁₀, а₆, а₄. (3)

ä₂, ä₄, ä₈, ä₁₀, (4)
ä₂, ä₇, ä₈, ä₄, ä₃, (5)
ä₁₀ , ä₇ , ä₄ , ä₈ , ä₇ , ä₂. (6)

Процедура находит путь минимального веса в графе G = (V, E) заданном весовой матрицей W у которой элемент w_ij  равен весу ребра соединяющего i-ую и j-ую вершины. При этом предполагается, что все элементы w_ij  неотрицательны. Путь ищется из вершины номер u₁  к вершине номер u₂ . Процедура использует алгоритм Дейкстры. Для представления веса, равного бесконечности, используется число GM, передаваемое в алгоритм. Это число можно задавать в зависимости от конкретной задачи.

Алгоритм по которому происходит поиск заключается в следующем:

1. всем веpшинам пpиписывается вес - вещественное число, d(i) := GM для всех вершин кроме вершины с номером u₁ , а d(u₁ ) := 0
2. всем веpшинам пpиписывается метка m(i) := 0
3. вершина u₁  объявляется текущей: t := u₁ 
4. для всех вершин у которых m(i) равно 0, пересчитываем вес по формуле: d(i) := min{d(i), d(t)+W[t,i]}
5. среди вершин для которых выполнено m(i) = 0 ищем ту для которой d(i) минимальна, если минимум не найден, т.е. вес всех не "помеченных" вершин равен бесконечности (GM), то путь не существует, покидаем алгоритм
6. иначе найденную вершину c минимальным весом полагаем текущей и помечаем (m(t) := 1)
7. если t = u₂ , то найден путь веса d(t), покидаем алгоритм
8. переходим на шаг 4.

На выходе имеем переменную length, которая определяет длину пути (length равно -1 если пути не существует, length равно 0, если u₁  равно u₂ ), переменную Weight - вес пути и массив Path содержащий последовательность номеров вершин определяющих путь. В алгоритме не упомянуто, как же определить сам путь, но это легко выяснить, если посмотреть блок-схему.

Алгоритм предназначен для нахождения К путей минимальной длины во взвешеном графе соединяющих вершины u₁ , u₂ . Ищутся пути, которые не содержат петель. Алгоритм прислал Pavel Mikheyev.

Итак задача состоит в отыскании нескольких минимальных путей, поэтому возникает вопрос о том чтобы не получить путь содержащий петлю, в случае поиска одного пути минимального веса, это условие выполняется по необходимости, в данном же случае мы используем алгоритм Йена, позволяющий находить K кратчайших простых цепей.

Работа алгоритма начинается с нахождения кратчайшего пути, для этого будем использовать уже описанный алгоритм Дейкстры. Второй путь ищем перебирая кратчайшие отклонения от первого, третий кратчайшие отклонения от второго и т.д. Более точное пошаговое описание:

1. Найти минимальный путь P₁  = (v ¹₁ , ..., v ¹_L[1] ). Положить k = 2. Включить P₁  в результирующий список.
2. Положить MinW равным бесконечности. Найти отклонение минимального веса, от (k–1)-го кратчайшего пути P_k-1  для всех i = 1, 2, ..., L[k-1], выполняя для каждого i шаги с 3-го по 6-й.
3. Проверить, совпадает ли подпуть, образованный первыми i вершинами пути P_k-1 , с подпутем, образованным первыми i вершинами любого из путей j = 1, 2, ..., k–1. Если да, положить W[v ^k-1_i , v ^j_i+1 ] равным бесконечности в противном случае ничего не изменять (чтобы в дальнейшем исключить получение в результат одних и тех же путей).
4. Используя алгоритм нахождения кратчайшего пути, найти пути от v ^k-1_i  к u₂ , исключая из рассмотрения корни (v ^k-1₁ , ..., v ^k-1_i ) (чтобы исключить петли), для этого достаточно положить равными бесконечности элементы столбцов и строк матрицы W, соответствующие вершинам входящим в корень.
5. Построить путь, объединяя корень и найденное кратчайшее ответвление, если его вес меньше MinW, то запомнить его.
6. Восстановить исходную матрицу весов W и возвратиться к шагу 3.
7. Поместить путь минимального веса (MinW), найденый в результате выполнения шагов с 3 по 6, в результирующий список. Если k = K, то алгоритм заканчивает работу, иначе увеличить k на единицу и вернуться к шагу 2.

Алгоритм использует массив p для результирующего списка путей, и массив length для хранения соответствующих длин, при этом если начиная с некоторого i элементы length[i] равны -1, значит существует только i-1 кратчайшех путей без петель.