Рассмотрим ориентированную сеть G=(I,U) без контуров, с одним источником s и стоком t. Числа на дугах l_ij означают их длину. найдем следующим образом: источнику т.е. вершине 1 присваиваем метку Е₁=0, число 0 означает, что это кратчайший путь до источника. Вершине 2 присваиваем метку Е₂=Е₁+l₁₂ . Далее последовательно будем присваивать метки вершинам 3,4,…,n по правилу:

Е_j=min(E_i+l_ij), j=3,4,…,n

{(i,j)}

{(i,j)}- означает множество дуг (i,j), входящих в вершину j. Число E_j равно длине кратчайшего пути от вершины s до вершины j.

Помечая вершины таким образом мы дойдем до стока. Метка E_t и будет означать длину кратчайшего пути от источника до стока.

Если в сети надо найти длину максимального пути, то пометки вершин 1 и 2 расставляют аналогично, а метки каждой последующей вершины находят по формуле:

Е_j=max(E_i+l_ij), j=3,4,…,n

{(i,j)}

Найдем кратчайший путь для нашего примера:

Е₂=E₁+l₁₂=0+1=1

Определив пометки вершин, начиная со второй, будем помечать * дугу, для которой в формуле находится минимальное значение. В самом начале всегда помечаем * дугу(1,2).

Е₃=min(0+2;1+3)=2 Метим * дугу (1,3) так как этой дуге соответствует min.

Е₄=min(1+5;2+5)=6 Метим * дугу (2,4) так как этой дуге соответствует min.

Е₅=min(2+12;6+7)=6 Метим * дугу (4,5) так как этой дуге соответствует min.

Е₆=min(1+6;13+3)=7 Метим * дугу (4,6) так как этой дуге соответствует min.

Длина кратчайшего пути от 1 до 6 равна:

l_min=E₆=7

Сам кратчайший путь найдем двигаясь с конца графика: от вершины 6 к началу графика – к вершине 1 вдоль помеченных * дуг в направлении, противоположном их ориентации.

l_min=(1,2,4,6)