Алгоритмы теории графов: Алгоритм Форда – Беллмана

Размещено на http://www.allbest.ru/

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

к курсовой работе по дисциплине “Математика”

на тему “Алгоритмы теории графов: Алгоритм Форда - Беллмана”

Содержание

Введение

1. Теоретическая часть

1.1 Постановка задачи

1.2 Основные понятия теории графов

1.3 Выбор алгоритма

2. Практическая часть

2.1 Поиск минимального пути

2.2 Построение матрицы смежности

2.3 Построение матрицы инцидентности

Заключение

Список литературы

Приложение

Введение

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

1. Теоретическая часть

1.1 Постановка задачи

1) Определить минимальный путь из х₁ в х₇ в нагруженном орграфе D, причем он должен иметь минимальное число дуг среди всех возможных минимальных путей. Орграф D изображен на рисунке 1, около каждой дуги указана ее длина.

Рисунок 1

Составлена (7 _? 7) - матрица C(D) длин дуг нагруженного орграфа D. Эта матрица представлена на рисунке 2.

	х1	х2	х3	х4	х5	х6	х7
х1	?	?	9	?	?	2	12
х2	1	?	?	?	1	2	4
х3	2	1	?	?	1	?	2
х4	?	1	1	?	?	1	?
х5	1	2	?	2	?	?	?
х6	?	?	?	?	1	?	8
х7	?	2	1	?	1	2	?

Рисунок 2

2) Составить матрицу смежности A = (a_ij) для данного графа.

3) Составить матрицу инцидентности B = (b_ij) для данного графа.

1.2 Основные понятия теории графов

Пусть х - не пустое множество и Х - некоторый набор пар элементов из V вида (х, щ), х, щ € V. Элементы множества V - вершины, множества X - ребра графа.

X = {( х₁, х₂), (х₂, х₃), (х₁, х₄), (х₄, х₄)}

Ребро вида (х, х) называется петлей, одинаковые пары во множестве X называются кратными ребрами.

Количество одинаковых пар (х, щ) называется кратностью ребра х, щ.

Множество V и набор Х определяют псевдограф G(V, X), т. е. граф с кратными ребрами и петлями.

Псевдограф без петель называется мультиграфом.

Если во множестве X нет кратных ребер, то G(V, X) называется графом.

Если во множестве Х пары являются упорядоченными, то граф называется ориентированным графом или орграфом.

Ребра орграфа называются дугами.

Если граф не ориентированный и х = (х, щ) - ребро, то вершины х и щ называются концами ребра х.

Если же граф ориентированный, то х называется началом дуги х, а щ - концом дуги х.

Вершина х и ребро х называются инцидентными.

Вершины х и щ называются смежными, если они имеют общую вершину.

Степенью вершины х называется число д(х) ребер графа инцидентных данной вершине.

Вершина, имеющая степень 0 называется изолированной, 1 - висячей.

Последовательность х_i1x_i1, х_i2x_i2, …, х_ikx_ik, х_ik+1, k ? 1, х_ij € V, x_ij € X, в которой чередуются вершины и ребра (дуги) и ребро x_ij (х_ij, х_ij+1) называется маршрутом, соединяющим вершины х_i1 и х_ik+1.

х_i1 называется начальной вершиной. х_ik+1 называется конечной вершиной. Остальные - внутренние.

Одна и та же вершина может быть одновременно и начальной, и конечной, и внутренней.

Если нет кратных ребер, то маршрут однозначно восстанавливается по последовательности вершин.

Для орграфа маршрут называется путь.

Число ребер или дуг в маршруте (пути) называется его длинной.

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

Незамкнутый маршрут, в котором все ребра попарно различны называется цепью.

Цепь, в которой все вершины попарно различны называется простой.

Замкнутый маршрут, в котором все ребра попарно различны называется циклом.

Цикл, в котором внутренние вершины попарно различны называется простым.

Матричные способы задания графов.

Пусть ?(х, x) - граф

V = {х₁, х₂, …, х_n}

X = {x₁, x₂, …, x_n}

Матрицей смежости называется квадратная матрица А n - ого порядка, элементы которой определяются формулой:

A = (a_ij) a_ij = 1, (х_i, х_j) € X

0, (х_i, х_j) не € X

Если дан псевдограф, то a_ij = 0, (х_i, х_j) € X

k, k - кратность ребра

Матрицей инцидентности называется матрица В размера M x N, элементы которой определяются по формуле:

B = (b_ij) b_ij = 0, х_i не инцидентна x_j

1, х_i есть конец дуги x_j

-1, х_i есть начало дуги x_j

Пусть D - ориентированный мультиграф с непустым множеством дуг, тогда:

1) сумма строк матрицы B(D) есть нулевая строка

2) любая строка B(D) есть линейная комбинация остальных

3) ранг матрицы B(D) не превосходит числа вершин - 1 (минус 1)

4) для любого контура в D сумма столбцов матрицы B(D) соответствующих дугов входящих в этот контур равна нулевому столбцу.

A(G) - матрица смежности

A^k(G) = A * A * … * A

Элемент q^k_ij матрицы A^k(G) ориентированного псвдографа равен числу всех путей длины k из вершины х_i в х_j.

Теорема: для того, чтобы n - вершинный орграф D с матрицей смежности A(D) имел хотя бы один контур необходимо и достаточно, чтобы матрица k = A² + + A³ + … + Aⁿ имела не нулевые диагональные элементы.

Объединением графов G₁(V₁, X₁) и G₂(V₂, X₂) называется граф

G = G₁ U G₂ (V₁UV₂, X₁UX₂)

Пересечением графов G₁ и G₂, где V₁ - пересечение V₂ ? Ш называется граф (V₁?V₂ = Ш) G₁?G₂ (V₁?V₂, X₁?X₂)

Подграфом графа G называется граф, все вершины и ребра которого содержатся среди вершин и ребер графа G.

Подграф называется собственным, если он отличен от самого графа.

Вершина щ орграфа D (графа G) называется достижимой из вершины V, если существует путь (маршрут) из V в щ или V = щ.

Граф называется связным, если для любых двух его вершин существует маршрут, соединяющий их.

Компонентой связности графа G называется его связный подграф не являющийся собственным подграфом никакого другого связанного подграфа.

Пусть орграф D имеет множество вершин V = {V₁, V₂, …, V_n}.

Матрицей достижимости орграфа D называется квадратная матрица T(D) порядка n, у которой t_ij = 1, х_j достижимо из х_i

0, х_j не достижимо из х_i

Матрицей связности S(D) орграфа D называется квадратная матрица порядка n, у которой S_ij = 1, х_j достижимо из х_i, х_i достижимо из х_j

0, в противном случае

Матрицей связности неориентированного графа G называется квадратная матрица S(G) порядка n у которой:

S_ij = 1, если i = j или если существует маршрут, соединяющий V_i и V_j

0, в противном случае

1.3 Выбор алгоритма

Для решения поставленной задачи будем использовать алгоритм Форда - Бэллмана.

Назовем орграф D = (V, X) нагруженным, если на множестве дуг X определена некоторая функция l: X > R, которую часто называют весовой функцией. Тем самым в нагруженном орграфе D в каждой дуге x € X поставлено в соответствие некоторое действительное число l(x). Значение l(x) будем называть длинной дуги x. Для этого пути р нагруженного орграфа D обозначим через l(р) сумму длин входящих в р дуг, при этом каждая дуга учитывается столько раз, сколько она входит в путь. Величину l(р) будем называть длинной пути р в нагруженном орграфе D. Ранее так называлось количество дуг в пути р. В связи с этим заметим, что если длины дуг выбраны равными l, то l(р) выражает введенную ранее длину пути р в ненагруженном орграфе. Следовательно, любой ненагруженный орграф можно считать нагруженным с длинами дуг, равными l. Аналогично определяется и нагруженный граф, а также длина маршрута в нем.

Пусть в нагруженном орграфе D из вершины х в вершину щ, где х ? щ, называется минимальным, если он имеет минимальную длину среди всех путей орграфа D из х в щ. Аналогично определяется и минимальный маршрут в нагруженном графе G.

Если в нагруженном орграфе D имеются замкнутые пути отрицательной длины, то для заданных вершин х₁, щ орграфа D, где х ? щ, минимального пути из х в щ может и не быть. Действительно, если в D имеется замкнутый путь у отрицательной длины и существует путь из х в щ, проходящий хотя бы через одну вершину, содержащуюся в у, то очевидно, что в D найдется путь р из х в щ вида р = р₁П у П р₂, где р₁, р₂ - пути в D (возможно также, что либо р₁, либо р₂ является пустой последовательностью; при этом предполагаем, что Ш П у = у П Ш = у). Но тогда р₁ П у П у П р₂, р₁ П у П у П у П р₂ … также пути в D из х в щ, и длина каждого следующего пути в этой последовательности отличается от длины предыдущего на l(у) < 0, а значит, длины путей из х в щ могут принимать сколь угодно малые отрицательные значения. Аналогичная ситуация имеет место в случае, когда в нагруженном графе G вершины х, щ находятся в одной компоненте связности, содержащей хотя бы одно ребро отрицательной длины. В таких случаях имеют смысл лишь задачи поиска минимальных путей (маршрутов) среди путей (маршрутов), число дуг (ребер) в которых ограничено сверху.

Приведем некоторые свойства минимальных путей (маршрутов) в нагруженном орграфе D = (V, X) (графе G = (V, X)):

1) если существует x € X l(x) > 0, то любой минимальный путь (маршрут) является простой цепью;

2) если х₁ х₂ … х_k - минимальный путь (маршрут), то для любых номеров i, j таких, что 1 ? i < j ? k, путь (маршрут) х_i х_i+1 также является минимальным;

3) если х … и щ - минимальный путь (маршрут) среди путей из х в щ (среди маршрутов, соединяющих х, щ), содержащих не более k+1 дуг (ребер), то х … u - минимальный путь (маршрут) среди путей из х в u (среди маршрутов, соединяющих х, u), содержащих не более k дуг (ребер).

Рассмотрим теперь задачу поиска минимальных путей (маршрутов) в нагруженном орграфе (графе). При этом для определенности рассуждения будем проводить для орграфа (для графа они аналогичны).

Замечание 1. При решении некоторых практических задач возникает необходимость поиска максимальных путей в нагруженном орграфе. Такая задача легко сводится к исследуемой ниже задаче поиска минимальных путей заменой знаков при длинах дуг на противоположные.

Пусть D = (V, X) - нагруженный орграф, V = { х₁, …, х_n}, n > 2. Введем величины л_i^(k), где i = 1, …, n, k = 1, 2, …. Для каждых фиксированных i и k величина л_i^(k) равна длине минимального пути среди путей из х₁ в х_i, содержащих не более k дуг; если же таких путей нет, то л_i^(k) = ?. Кроме того, если произвольную вершину х € V считать путем из х в х нулевой длины, то величины л_i^(k) можно ввести также и для k = 0, при этом

л₁⁽⁰⁾ = 0, л_i⁽⁰⁾ = ?, i = 2, …, n. (1)

Введем также в рассмотрение квадратную матрицу C(D) = [с_ij] порядка n с элементами

c_ij = l(х_i, х_j), если (х_i, х_j) € X;

?, если (х_i, х_j) € Х,

которую будем называть матрицей длин дуг нагруженного орграфа D.

Следующее утверждение дает простые формулы дл вычисления величин л_i^(k).

Утверждение 1. При i - 2, …, n, k ? 0 выполняется равенство

л_i^(k+1) = min {л_j^(k)+c_ij} (2)

1 ? j ? n

а при i - 1, k ? 0 справедливо равенство

л_i^(k+1) = min{0; min {л_j^(k)=c_j1}} (3)

1 ? j ? n

Используя утверждение 1, нетрудно описать алгоритм нахождения таблицы значении величин л_i^(k) (будем записывать в виде матрицы, где i - номер строки, k+1 - номер столбца). Действительно, используя рекуррентные соотношения (2), (3) и исходя из (1), последовательно определяем набор величин л₁^(k), …, л_n^(k) ((k+1) столбец матрицы), начиная с k = 0, а затем шаг за шагом увеличивая значение k до любой необходимой величины.

Будем теперь предполагать, что в D отсутствуют простые контуры отрицательной длины (ниже в утверждении 5 приводится простой метод проверки этого условия). Для дальнейших рассуждений нам понадобятся дополнительные утверждения.

Утверждение 2. Из всякого замкнутого пути отрицательной длины можно выделить простой контур отрицательной длины.

Утверждение 3. Если в нагруженном орграфе отсутствуют простые контуры отрицательной длины, то в нем нет замкнутых путей отрицательной длины.

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

Замечание 2. При определении нагруженного графа мы предполагали, что величины l(x), x € X, конечны. Между тем величины л_i^(k) (i = 1, 2, …, n, k = 0, 1, …, n - 1) можно аналогичным образом определить и для случая, когда для некоторых x € X выполняется l(x) = ?. При этом сохраняет силу утверждение 1, а следовательно, и алгоритм построения таблицы величин л_i^(k). Отметим, однако, что теперь могут существовать вершины, достижимые из х₁ с длинами минимальных путей из х₁ в эти вершины, равными ?, т. е. мы уже не можем судить по л_i^(n-1) о достижимости вершин х_i из х₁.

Замечание 3. Если при некотором k₀, где 0 ? k₀ ? n - 2, выполняются равенства л_i^(k0) = л_i^{(k0 + 1)}, i = 1, 2, …, n, и, в частности, л_i^{(n - 1)} = л_i^(k0), i = 1, 2, …, n, т. е. в данном случае значения л_i^(k) при k > k₀ не несут никакой дополнительной информации, и тогда имеет смысл оборвать процесс последовательного определения наборов величин л₁^(k), …, л_n^(k) на значении k = k₀.

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

Утверждение 5. Пусть в орграфе D = (V, X), где V = { х₁, …, х_n}, любая вершина х_i, i € {2, …, n}, достижима из х₁. Тогда, для того чтобы в D отсутствовали простые контуры отрицательной длины, необходимо и достаточно, чтобы выполнялось условие л_i^{(n -1)} = л_i⁽ⁿ⁾, i = 1, …, n.

Алгоритм (алгоритм Форда - Беллмана) нахождения минимального пути в нагруженном орграфе D из х₁ в х_i1, (i ? 1):

Шаг 1. Пусть мы уже составили таблицу величин л_i^(k), i = 1, 2, …, n, k = 0, 1, 2, …, n - 1. Если л_i^(n-1) = ?, то вершина х_i1 не достижима из х₁ (предполагаем, что все величины l(x), x € X конечны). В этом случае работа алгоритма заканчивается.

Шаг 2. Пусть л_i1^(n-1) < ?, тогда число л_i1^(n-1) выражает длину любого минимального пути из х₁ в х_i1 в нагруженном орграфе D. Определим минимальное число k ? 1, при котором выполняется равенство л_i1^(k1) = л_i1^(n-1). По определению чисел л_i^(k) получаем, что k₁ - минимальное число дуг в пути среди всех минимальных путей х₁ в х_i1 в нагруженном орграфе D.

Шаг 3. Последовательно определяем номера i₂, …, i_k1+1 такие, что

л_i2^(k1-1) + с_i2,i1 = л_i1^(k1)

л_i3^(k1-2) + с_i3,i2 = л_i1^{(k1 - 1)}

^{. . . . . . . . . . . . . . . .} (4)

л_i⁽⁰⁾ + c_{i j} = л_i⁽¹⁾

^{k1+1 k1+1 k1 k1}

(эти номера найдутся в силу (2)).

Из (4) с учетом того, что л_i1^(k1)=л_i1^{(n - 1)} < ?, имеем c_{i2, i1}<?,…,c_i, _i < ?, л_i⁽⁰⁾ < ?,

^{k1+1 k1 k1+1}

откуда, используя (1), получаем

(х_i2, х_i1), …, (х_i, х_i) € X, l(х_i2, х_i1) = c_{i2, i1}, …, l(х_i2, х_i1) = c_i,I;

^{k1+1 k1 k1+1 k1 k1+1 k1}

л_i⁽⁰⁾ = 0, i = 1, х_i = х₁ (5)

^{k1+1 k1+1 k1+1}

Складывая равенства (4) и учитывая (5), имеем

l(х_1k1 х_i … х_i2 х_i1) = л_i1^(k1), (6)

т. е. х₁ х_i … х_i2 х_i1 - исходный минимальный путь из х₁ в х_i1 в нагруженном орграфе D. Заметим, что в этом пути ровно k_i дуг. Следовательно мы определили путь с минимальным числом дуг среди всех минимальных путей из х₁ в х_i1 в нагруженном орграфе D.

Замечание 4. Номера i₂, i₃, …, i_k1, удовлетворяющие (6), вообще говоря, могут быть выделены неоднозначно. Эта неоднозначность соответствует случаям, когда существует несколько различных путей из х₁ в х_i1 c минимальным числом дуг среди минимальных путей из х₁ в х_i1 в нагруженном орграфе D.

Замечание 5. Алгоритм можно модифицировать, с тем х₁ в х_i1, содержащих не более k₀ дуг, где k₀ - заданное число, k₀ > 1. Xтобы определить минимальный путь из х₁ в заданную вершину х_i1 среди путей из х₁ в х_i1. Для этого в алгоритме вместо л_i^{(n - 1)} следует воспользоваться л_i1^(k0). Отметим, что при использовании указанной модификации алгоритма предположение об отсутствии простых контуров отрицательной длины излишне. При том, если в орграфе D имеются простые контуры отрицательной длины, может выполняться неравенство л₁^(k0) < 0.

Замечание 6. Алгоритм и его модификация, описанная выше, после соответствующего изменения в терминологии и обозначениях применимы и к неориентированному графу G. При этом условие отсутствия простых контуров отрицательной длины заменяется условием отсутствия ребер отрицательной длины.

Замечание 7. Нетрудно доказать, что утверждение 1, а следовательно, и алгоритм вместе с его модификацией останутся справедливыми и для нагруженного ориентированного псевдографа. При этом в случае кратных дуг следует учитывать лишь дуги минимальной длины, а при наличии петель - лишь, петли отрицательной длины. Это замечание переносится и на неориентированные псевдографы.

2. Практическая часть

2.1 Поиск минимального пути

Составим таблицу

	лi(0)	лi(1)	лi(2)	лi(3)	лi(4)	лi(5)	лi(6)
i1
i2
i3
i4
i5
i6
i7

и будем последовательно определять ее элементы, используя рекуррентное соотношение (2) и исходя из (1).

л₁⁽⁰⁾ = 0, л_i⁽⁰⁾ = ?, i = 2, …, n.

Используя (2) определим элементы л_i^(k), i = 2, 3, 4, 5, 6, 7; k = 1, 2, 3, 4, 5, 6.

л₂⁽¹⁾ = min{л_j⁽⁰⁾ + c_j2}, 1 ? j ? 7

при j = 1 л₁⁽⁰⁾ + с₁₂ = 0 + ? = ?

при j = 2 л₂⁽⁰⁾ + с₂₂ = ? + ? = ?

при j = 3 л₃⁽⁰⁾ + с₃₂ = ? + 1 = ?

при j = 4 л₄⁽⁰⁾ + с₄₂ = ? + 1 = ?

при j = 5 л₅⁽⁰⁾ + с₅₂ = ? + 2 = ?

при j = 6 л₆⁽⁰⁾ + с₆₂ = ? + ? = ?

при j = 7 л₇⁽⁰⁾ + с₇₂ = ? + 2 = ?

Следовательно л₂⁽¹⁾ = ?

л₃⁽¹⁾ = min{л_j⁽⁰⁾ + c_j3}, 1 ? j ? 7

при j = 1 л₁⁽⁰⁾ + с₁₃ = 0 + 9 = 9

при j = 2 л₂⁽⁰⁾ + с₂₃ = ? + ? = ?

при j = 3 л₃⁽⁰⁾ + с₃₃ = ? + ? = ?

при j = 4 л₄⁽⁰⁾ + с₄₃ = ? + 1 = ?

при j = 5 л₅⁽⁰⁾ + с₅₃ = ? + ? = ?

при j = 6 л₆⁽⁰⁾ + с₆₃ = ? + ? = ?

при j = 7 л₇⁽⁰⁾ + с₇₃ = ? + 1 = ?

Следовательно л₂⁽¹⁾ = 9

л₄⁽¹⁾ = min{л_j⁽⁰⁾ + c_j4}, 1 ? j ? 7

при j = 1 л₁⁽⁰⁾ + с₁₄ = 0 + ? = ?

при j = 2 л₂⁽⁰⁾ + с₂₄ = ? + ? = ?

при j = 3 л₃⁽⁰⁾ + с₃₄ = ? + ? = ?

при j = 4 л₄⁽⁰⁾ + с₄₄ = ? + ? = ?

при j = 5 л₅⁽⁰⁾ + с₅₄ = ? + 2 = ?

при j = 6 л₆⁽⁰⁾ + с₆₄ = ? + ? = ?

при j = 7 л₇⁽⁰⁾ + с₇₄ = ? + ? = ?

Следовательно л₄⁽¹⁾ = ?

л₅⁽¹⁾ = min{л_j⁽⁰⁾ + c_j5}, 1 ? j ? 7

при j = 1 л₁⁽⁰⁾ + с₁₅ = 0 + ? = ?

при j = 2 л₂⁽⁰⁾ + с₂₅ = ? + 1 = ?

при j = 3 л₃⁽⁰⁾ + с₃₅ = ? + 1 = ?

при j = 4 л₄⁽⁰⁾ + с₄₅ = ? + ? = ?

при j = 5 л₅⁽⁰⁾ + с₅₅ = ? + ? = ?

при j = 6 л₆⁽⁰⁾ + с₆₅ = ? + ? = ?

при j = 7 л₇⁽⁰⁾ + с₇₅ = ? + 1 = ?

Следовательно л₅⁽¹⁾ = ?

л₆⁽¹⁾ = min{л_j⁽⁰⁾ + c_j6}, 1 ? j ? 7

при j = 1 л₁⁽⁰⁾ + с₁₆ = 0 + 2 = 2

при j = 2 л₂⁽⁰⁾ + с₂₆ = ? + 2 = ?

при j = 3 л₃⁽⁰⁾ + с₃₆ = ? + ? = ?

при j = 4 л₄⁽⁰⁾ + с₄₆ = ? + 1 = ?

при j = 5 л₅⁽⁰⁾ + с₅₆ = ? + ? = ?

при j = 6 л₆⁽⁰⁾ + с₆₆ = ? + ? = ?

при j = 7 л₇⁽⁰⁾ + с₇₆ = ? + 2 = ?

Следовательно л₆⁽¹⁾ = 2

л₇⁽¹⁾ = min{л_j⁽⁰⁾ + c_j7}, 1 ? j ? 7

при j = 1 л₁⁽⁰⁾ + с₁₇ = 0 + 12 = 12

при j = 2 л₂⁽⁰⁾ + с₂₇ = ? + 4 = ?

при j = 3 л₃⁽⁰⁾ + с₃₇ = ? + 2 = ?

при j = 4 л₄⁽⁰⁾ + с₄₇ = ? + ? = ?

при j = 5 л₅⁽⁰⁾ + с₅₇ = ? + ? = ?

при j = 6 л₆⁽⁰⁾ + с₆₇ = ? + 8 = ?

при j = 7 л₇⁽⁰⁾ + с₇₇ = ? + ? = ?

Следовательно л₇⁽¹⁾ = 12

л₂⁽²⁾ = min{л_j⁽¹⁾ + c_j2}, 1 ? j ? 7

при j = 1 л₁⁽¹⁾ + с₁₂ = 0 + ? = ?

при j = 2 л₂⁽¹⁾ + с₂₂ = ? + ? = ?

при j = 3 л₃⁽¹⁾ + с₃₂ = 9 + 1 = 10

при j = 4 л₄⁽¹⁾ + с₄₂ = ? + 1 = ?

при j = 5 л₅⁽¹⁾ + с₅₂ = ? + 2 = ?

при j = 6 л₆⁽¹⁾ + с₆₂ = 2 + ? = ?

при j = 7 л₇⁽¹⁾ + с₇₂ = 12 + 2 = 14

Следовательно л₂⁽²⁾ = 10

л₂⁽²⁾ = min{л_j⁽¹⁾ + c_j2}, 1 ? j ? 7

при j = 1 л₁⁽¹⁾ + с₁₂ = 0 + ? = ?

при j = 2 л₂⁽¹⁾ + с₂₂ = ? + ? = ?

при j = 3 л₃⁽¹⁾ + с₃₂ = 9 + 1 = 10

при j = 4 л₄⁽¹⁾ + с₄₂ = ? + 1 = ?

при j = 5 л₅⁽¹⁾ + с₅₂ = ? + 2 = ?

при j = 6 л₆⁽¹⁾ + с₆₂ = 2 + ? = ?

при j = 7 л₇⁽¹⁾ + с₇₂ = 12 + 2 = 14

Следовательно л₂⁽²⁾ = 10

л₃⁽²⁾ = min{л_j⁽¹⁾ + c_j3}, 1 ? j ? 7

при j = 1 л₁⁽¹⁾ + с₁₃ = 0 + 9 = 9

при j = 2 л₂⁽¹⁾ + с₂₃ = ? + ? = ?

при j = 3 л₃⁽¹⁾ + с₃₃ = 9 + ? = ?

при j = 4 л₄⁽¹⁾ + с₄₃ = ? + 1 = ?

при j = 5 л₅⁽¹⁾ + с₅₃ = ? + ? = ?

при j = 6 л₆⁽¹⁾ + с₆₃ = 2 + ? = ?

при j = 7 л₇⁽¹⁾ + с₇₃ = 12 + 1 = 13

Следовательно л₃⁽²⁾ = 9

л₄⁽²⁾ = min{л_j⁽¹⁾ + c_j4}, 1 ? j ? 7

при j = 1 л₁⁽¹⁾ + с₁₄ = 0 + ? = ?

при j = 2 л₂⁽¹⁾ + с₂₄ = ? + ? = ?

при j = 3 л₃⁽¹⁾ + с₃₄ = 9 + ? = ?

при j = 4 л₄⁽¹⁾ + с₄₄ = ? + ? = ?

при j = 5 л₅⁽¹⁾ + с₅₄ = ? + 2 = ?

при j = 6 л₆⁽¹⁾ + с₆₄ = 2 + ? = ?

при j = 7 л₇⁽¹⁾ + с₇₄ = 12 + ? = ?

Следовательно л₄⁽²⁾ = ?

л₅⁽²⁾ = min{л_j⁽¹⁾ + c_j5}, 1 ? j ? 7

при j = 1 л₁⁽¹⁾ + с₁₅ = 0 + ? = ?

при j = 2 л₂⁽¹⁾ + с₂₅ = ? + 1 = ?

при j = 3 л₃⁽¹⁾ + с₃₅ = 9 + 1 = 10

при j = 4 л₄⁽¹⁾ + с₄₅ = ? + ? = ?

при j = 5 л₅⁽¹⁾ + с₅₅ = ? + ? = ?

при j = 6 л₆⁽¹⁾ + с₆₅ = 2 + 1 = 3

при j = 7 л₇⁽¹⁾ + с₇₅ = 12 + 1 = 13

Следовательно л₅⁽²⁾ = 3

л₆⁽²⁾ = min{л_j⁽¹⁾ + c_j6}, 1 ? j ? 7

при j = 1 л₁⁽¹⁾ + с₁₆ = 0 + 2 = 2

при j = 2 л₂⁽¹⁾ + с₂₆ = ? + 2 = ?

при j = 3 л₃⁽¹⁾ + с₃₆ = 9 + ? = ?

при j = 4 л₄⁽¹⁾ + с₄₆ = ? + 1 = ?

при j = 5 л₅⁽¹⁾ + с₅₆ = ? + ? = ?

при j = 6 л₆⁽¹⁾ + с₆₆ = 2 + ? = ?

при j = 7 л₇⁽¹⁾ + с₇₆ = 12 + 2 = 14

Следовательно л₆⁽²⁾ = 2

л₇⁽²⁾ = min{л_j⁽¹⁾ + c_j7}, 1 ? j ? 7

при j = 1 л₁⁽¹⁾ + с₁₇ = 0 + 12 = 12

при j = 2 л₂⁽¹⁾ + с₂₇ = ? + 4 = ?

при j = 3 л₃⁽¹⁾ + с₃₇ = 9 + 2 = 11

при j = 4 л₄⁽¹⁾ + с₄₇ = ? + ? = ?

при j = 5 л₅⁽¹⁾ + с₅₇ = ? + ? = ?

при j = 6 л₆⁽¹⁾ + с₆₇ = 2 + 8 = 10

при j = 7 л₇⁽¹⁾ + с₇₇ = 12 + ? = ?

Следовательно л₇⁽²⁾ = 10

л₂⁽³⁾ = min{л_j⁽²⁾ + c_j2}, 1 ? j ? 7

при j = 1 л₁⁽²⁾ + с₁₂ = 0 + ? = ?

при j = 2 л₂⁽²⁾ + с₂₂ = 10 + ? = ?

при j = 3 л₃⁽²⁾ + с₃₂ = 9 + 1 = 10

при j = 4 л₄⁽²⁾ + с₄₂ = ? + 1 = ?

при j = 5 л₅⁽²⁾ + с₅₂ = 3 + 2 = 5

при j = 6 л₆⁽²⁾ + с₆₂ = 2 + ? = ?

при j = 7 л₇⁽²⁾ + с₇₂ = 10 + 2 = 12

Следовательно л₂⁽³⁾ = 5

л₃⁽³⁾ = min{л_j⁽²⁾ + c_j3}, 1 ? j ? 7

при j = 1 л₁⁽²⁾ + с₁₃ = 0 + 9 = 9

при j = 2 л₂⁽²⁾ + с₂₃ = 10 + ? = ?

при j = 3 л₃⁽²⁾ + с₃₃ = 9 + ? = ?

при j = 4 л₄⁽²⁾ + с₄₃ = ? + 1 = ?

при j = 5 л₅⁽²⁾ + с₅₃ = 3 + ? = ?

при j = 6 л₆⁽²⁾ + с₆₃ = 2 + ? = ?

при j = 7 л₇⁽²⁾ + с₇₃ = 10 + 1 = 11

Следовательно л₃⁽³⁾ = 9

л₄⁽³⁾ = min{л_j⁽²⁾ + c_j4}, 1 ? j ? 7

при j = 1 л₁⁽²⁾ + с₁₄ = 0 + ? = ?

при j = 2 л₂⁽²⁾ + с₂₄ = 10 + ? = ?

при j = 3 л₃⁽²⁾ + с₃₄ = 9 + ? = ?

при j = 4 л₄⁽²⁾ + с₄₄ = ? + ? = ?

при j = 5 л₅⁽²⁾ + с₅₄ = 3 + 2 = 5

при j = 6 л₆⁽²⁾ + с₆₄ = 2 + ? = ?

при j = 7 л₇⁽²⁾ + с₇₄ = 10 + ? = ?

Следовательно л₄⁽³⁾ = 5

л₅⁽³⁾ = min{л_j⁽²⁾ + c_j5}, 1 ? j ? 7

при j = 1 л₁⁽²⁾ + с₁₅ = 0 + ? = ?

при j = 2 л₂⁽²⁾ + с₂₅ = 10 + 1 = 11

при j = 3 л₃⁽²⁾ + с₃₅ = 9 + 1 = 10

при j = 4 л₄⁽²⁾ + с₄₅ = ? + ? = ?

при j = 5 л₅⁽²⁾ + с₅₅ = 3 + ? = ?

при j = 6 л₆⁽²⁾ + с₆₅ = 2 + 1 = 3

при j = 7 л₇⁽²⁾ + с₇₅ = 10 + 1 = 11

Следовательно л₅⁽³⁾ = 3

л₆⁽³⁾ = min{л_j⁽²⁾ + c_j6}, 1 ? j ? 7

при j = 1 л₁⁽²⁾ + с₁₆ = 0 + 2 = 2

при j = 2 л₂⁽²⁾ + с₂₆ = 10 + 2 = 12

при j = 3 л₃⁽²⁾ + с₃₆ = 9 + ? = ?

при j = 4 л₄⁽²⁾ + с₄₆ = ? + 1 = ?

при j = 5 л₅⁽²⁾ + с₅₆ = 3 + ? = ?

при j = 6 л₆⁽²⁾ + с₆₆ = 2 + ? = ?

при j = 7 л₇⁽²⁾ + с₇₆ = 10 + 2 = 12

Следовательно л₆⁽³⁾ = 2

л₇⁽³⁾ = min{л_j⁽²⁾ + c_j7}, 1 ? j ? 7

при j = 1 л₁⁽²⁾ + с₁₇ = 0 + 12 = 12

при j = 2 л₂⁽²⁾ + с₂₇ = 10 + 4 = 14

при j = 3 л₃⁽²⁾ + с₃₇ = 9 + 2 = 11

при j = 4 л₄⁽²⁾ + с₄₇ = ? + ? = ?

при j = 5 л₅⁽²⁾ + с₅₇ = 3 + ? = ?

при j = 6 л₆⁽²⁾ + с₆₇ = 2 + 8 = 10

при j = 7 л₇⁽²⁾ + с₇₇ = 10 + ? = ?

Следовательно л₇⁽³⁾ = 10

л₂⁽⁴⁾ = min{л_j⁽³⁾ + c_j2}, 1 ? j ? 7

при j = 1 л₁⁽³⁾ + с₁₂ = 0 + ? = ?

при j = 2 л₂⁽³⁾ + с₂₂ = 5 + ? = ?

при j = 3 л₃⁽³⁾ + с₃₂ = 9 + 1 = 10

при j = 4 л₄⁽³⁾ + с₄₂ = 5 + 1 = 6

при j = 5 л₅⁽³⁾ + с₅₂ = 3 + 2 = 5

при j = 6 л₆⁽³⁾ + с₆₂ = 2 + ? = ?

при j = 7 л₇⁽³⁾ + с₇₂ = 10 + 2 = 12

Следовательно л₂⁽⁴⁾ = 5

л₃⁽⁴⁾ = min{л_j⁽³⁾ + c_j3}, 1 ? j ? 7

при j = 1 л₁⁽³⁾ + с₁₃ = 0 + 9 = 9

при j = 2 л₂⁽³⁾ + с₂₃ = 5 + ? = ?

при j = 3 л₃⁽³⁾ + с₃₃ = 9 + ? = ?

при j = 4 л₄⁽³⁾ + с₄₃ = 5 + 1 = 6

при j = 5 л₅⁽³⁾ + с₅₃ = 3 + ? = ?

при j = 6 л₆⁽³⁾ + с₆₃ = 2 + ? = ?

при j = 7 л₇⁽³⁾ + с₇₃ = 10 + 1 = 11

Следовательно л₃⁽⁴⁾ = 6

л₄⁽⁴⁾ = min{л_j⁽³⁾ + c_j4}, 1 ? j ? 7

при j = 1 л₁⁽³⁾ + с₁₄ = 0 + ? = ?

при j = 2 л₂⁽³⁾ + с₂₄ = 5 + ? = ?

при j = 3 л₃⁽³⁾ + с₃₄ = 9 + ? = ?

при j = 4 л₄⁽³⁾ + с₄₄ = 5 + ? = ?

при j = 5 л₅⁽³⁾ + с₅₄ = 3 + 2 = 5

при j = 6 л₆⁽³⁾ + с₆₄ = 2 + ? = ?

при j = 7 л₇⁽³⁾ + с₇₄ = 10 + ? = ?

Следовательно л₄⁽⁴⁾ = 5

л₅⁽⁴⁾ = min{л_j⁽³⁾ + c_j5}, 1 ? j ? 7

при j = 1 л₁⁽³⁾ + с₁₅ = 0 + ? = ?

при j = 2 л₂⁽³⁾ + с₂₅ = 5 + 1 = 6

при j = 3 л₃⁽³⁾ + с₃₅ = 9 + 1 = 10

при j = 4 л₄⁽³⁾ + с₄₅ = 5 + ? = ?

при j = 5 л₅⁽³⁾ + с₅₅ = 3 + ? = ?

при j = 6 л₆⁽³⁾ + с₆₅ = 2 + 1 = 3

при j = 7 л₇⁽³⁾ + с₇₅ = 10 + 1 = 11

Следовательно л₅⁽⁴⁾ = 3

л₆⁽⁴⁾ = min{л_j⁽³⁾ + c_j6}, 1 ? j ? 7

при j = 1 л₁⁽³⁾ + с₁₆ = 0 + 2 = 2

при j = 2 л₂⁽³⁾ + с₂₆ = 5 + 2 = 7

при j = 3 л₃⁽³⁾ + с₃₆ = 9 + ? = ?

при j = 4 л₄⁽³⁾ + с₄₆ = 5 + 1 = 6

при j = 5 л₅⁽³⁾ + с₅₆ = 3 + ? = ?

при j = 6 л₆⁽³⁾ + с₆₆ = 2 + ? = ?

при j = 7 л₇⁽³⁾ + с₇₆ = 10 + 2 = 12

Следовательно л₆⁽⁴⁾ = 2

л₇⁽⁴⁾ = min{л_j⁽³⁾ + c_j7}, 1 ? j ? 7

при j = 1 л₁⁽³⁾ + с₁₇ = 0 + 12 = 12

при j = 2 л₂⁽³⁾ + с₂₇ = 5 + 4 = 9

при j = 3 л₃⁽³⁾ + с₃₇ = 9 + 2 = 11

при j = 4 л₄⁽³⁾ + с₄₇ = 5 + ? = ?

при j = 5 л₅⁽³⁾ + с₅₇ = 3 + ? = ?

при j = 6 л₆⁽³⁾ + с₆₇ = 2 + 8 = 10

при j = 7 л₇⁽³⁾ + с₇₇ = 10 + ? = ?

Следовательно л₇⁽⁴⁾ = 9

л₂⁽⁵⁾ = min{л_j⁽⁴⁾ + c_j2}, 1 ? j ? 7

при j = 1 л₁⁽⁴⁾ + с₁₂ = 0 + ? = ?

при j = 2 л₂⁽⁴⁾ + с₂₂ = 5 + ? = ?

при j = 3 л₃⁽⁴⁾ + с₃₂ = 6 + 1 = 7

при j = 4 л₄⁽⁴⁾ + с₄₂ = 5 + 1 = 6

при j = 5 л₅⁽⁴⁾ + с₅₂ = 3 + 2 = 5

при j = 6 л₆⁽⁴⁾ + с₆₂ = 2 + ? = ?

при j = 7 л₇⁽⁴⁾ + с₇₂ = 9 + 2 = 11

Следовательно л₂⁽⁵⁾ = 5

л₃⁽⁵⁾ = min{л_j⁽⁴⁾ + c_j3}, 1 ? j ? 7

при j = 1 л₁⁽⁴⁾ + с₁₃ = 0 + 9 = 9

при j = 2 л₂⁽⁴⁾ + с₂₃ = 5 + ? = ?

при j = 3 л₃⁽⁴⁾ + с₃₃ = 6 + ? = ?

при j = 4 л₄⁽⁴⁾ + с₄₃ = 5 + 1 = 6

при j = 5 л₅⁽⁴⁾ + с₅₃ = 3 + ? = ?

при j = 6 л₆⁽⁴⁾ + с₆₃ = 2 + ? = ?

при j = 7 л₇⁽⁴⁾ + с₇₃ = 9 + 1 = 10

Следовательно л₃⁽⁵⁾ = 6

л₄⁽⁵⁾ = min{л_j⁽⁴⁾ + c_j4}, 1 ? j ? 7

при j = 1 л₁⁽⁴⁾ + с₁₄ = 0 + ? = ?

при j = 2 л₂⁽⁴⁾ + с₂₄ = 5 + ? = ?

при j = 3 л₃⁽⁴⁾ + с₃₄ = 6 + ? = ?

при j = 4 л₄⁽⁴⁾ + с₄₄ = 5 + ? = ?

при j = 5 л₅⁽⁴⁾ + с₅₄ = 3 + 2 = 5

при j = 6 л₆⁽⁴⁾ + с₆₄ = 2 + ? = ?

при j = 7 л₇⁽⁴⁾ + с₇₄ = 9 + ? = ?

Следовательно л₄⁽⁵⁾ = 5

л₅⁽⁵⁾ = min{л_j⁽⁴⁾ + c_j5}, 1 ? j ? 7

при j = 1 л₁⁽⁴⁾ + с₁₅ = 0 + ? = ?

при j = 2 л₂⁽⁴⁾ + с₂₅ = 5 + 1 = 6

при j = 3 л₃⁽⁴⁾ + с₃₅ = 6 + 1 = 7

при j = 4 л₄⁽⁴⁾ + с₄₅ = 5 + ? = ?

при j = 5 л₅⁽⁴⁾ + с₅₅ = 3 + ? = ?

при j = 6 л₆⁽⁴⁾ + с₆₅ = 2 + 1 = 3

при j = 7 л₇⁽⁴⁾ + с₇₅ = 9 + 1 = 10

Следовательно л₅⁽⁵⁾ = 3

л₆⁽⁵⁾ = min{л_j⁽⁴⁾ + c_j6}, 1 ? j ? 7

при j = 1 л₁⁽⁴⁾ + с₁₆ = 0 + 2 = 2

при j = 2 л₂⁽⁴⁾ + с₂₆ = 5 + 2 = 7

при j = 3 л₃⁽⁴⁾ + с₃₆ = 6 + ? = ?

при j = 4 л₄⁽⁴⁾ + с₄₆ = 5 + 1 = 6

при j = 5 л₅⁽⁴⁾ + с₅₆ = 3 + ? = ?

при j = 6 л₆⁽⁴⁾ + с₆₆ = 2 + ? = ?

при j = 7 л₇⁽⁴⁾ + с₇₆ = 9 + 2 = 11

Следовательно л₆⁽⁵⁾ = 2

л₇⁽⁵⁾ = min{л_j⁽⁴⁾ + c_j7}, 1 ? j ? 7

при j = 1 л₁⁽⁴⁾ + с₁₇ = 0 + 12 = 12

при j = 2 л₂⁽⁴⁾ + с₂₇ = 5 + 4 = 9

при j = 3 л₃⁽⁴⁾ + с₃₇ = 6 + 2 = 8

при j = 4 л₄⁽⁴⁾ + с₄₇ = 5 + ? = ?

при j = 5 л₅⁽⁴⁾ + с₅₇ = 3 + ? = ?

при j = 6 л₆⁽⁴⁾ + с₆₇ = 2 + 8 = 10

при j = 7 л₇⁽⁴⁾ + с₇₇ = 9 + ? = ?

Следовательно л₇⁽⁵⁾ = 8

л₂⁽⁶⁾ = min{л_j⁽⁵⁾ + c_j2}, 1 ? j ? 7

при j = 1 л₁⁽⁵⁾ + с₁₂ = 0 + ? = ?

при j = 2 л₂⁽⁵⁾ + с₂₂ = 5 + ? = ?

при j = 3 л₃⁽⁵⁾ + с₃₂ = 6 + 1 = 7

при j = 4 л₄⁽⁵⁾ + с₄₂ = 5 + 1 = 6

при j = 5 л₅⁽⁵⁾ + с₅₂ = 3 + 2 = 5

при j = 6 л₆⁽⁵⁾ + с₆₂ = 2 + ? = ?

при j = 7 л₇⁽⁵⁾ + с₇₂ = 9 + 2 = 11

Следовательно л₂⁽⁶⁾ = 5

л₃⁽⁶⁾ = min{л_j⁽⁵⁾ + c_j3}, 1 ? j ? 7

при j = 1 л₁⁽⁵⁾ + с₁₃ = 0 + 9 = 9

при j = 2 л₂⁽⁵⁾ + с₂₃ = 5 + ? = ?

при j = 3 л₃⁽⁵⁾ + с₃₃ = 6 + ? = ?

при j = 4 л₄⁽⁵⁾ + с₄₃ = 5 + 1 = 6

при j = 5 л₅⁽⁵⁾ + с₅₃ = 3 + ? = ?

при j = 6 л₆⁽⁵⁾ + с₆₃ = 2 + ? = ?

при j = 7 л₇⁽⁵⁾ + с₇₃ = 9 + 1 = 10

Следовательно л₃⁽⁶⁾ = 6

л₄⁽⁶⁾ = min{л_j⁽⁵⁾ + c_j4}, 1 ? j ? 7

при j = 1 л₁⁽⁵⁾ + с₁₄ = 0 + ? = ?

при j = 2 л₂⁽⁵⁾ + с₂₄ = 5 + ? = ?

при j = 3 л₃⁽⁵⁾ + с₃₄ = 6 + ? = ?

при j = 4 л₄⁽⁵⁾ + с₄₄ = 5 + ? = ?

при j = 5 л₅⁽⁵⁾ + с₅₄ = 3 + 2 = 5

при j = 6 л₆⁽⁵⁾ + с₆₄ = 2 + ? = ?

при j = 7 л₇⁽⁵⁾ + с₇₄ = 9 + ? = ?

Следовательно л₄⁽⁶⁾ = 5

л₅⁽⁶⁾ = min{л_j⁽⁵⁾ + c_j5}, 1 ? j ? 7

при j = 1 л₁⁽⁵⁾ + с₁₅ = 0 + ? = ?

при j = 2 л₂⁽⁵⁾ + с₂₅ = 5 + 1 = 6

при j = 3 л₃⁽⁵⁾ + с₃₅ = 6 + 1 = 7

при j = 4 л₄⁽⁵⁾ + с₄₅ = 5 + ? = ?

при j = 5 л₅⁽⁵⁾ + с₅₅ = 3 + ? = ?

при j = 6 л₆⁽⁵⁾ + с₆₅ = 2 + 1 = 3

при j = 7 л₇⁽⁵⁾ + с₇₅ = 9 + 1 = 10

Следовательно л₂⁽⁶⁾ = 3

л₆⁽⁶⁾ = min{л_j⁽⁵⁾ + c_j6}, 1 ? j ? 7

при j = 1 л₁⁽⁵⁾ + с₁₆ = 0 + 2 = 2

при j = 2 л₂⁽⁵⁾ + с₂₆ = 5 + 2 = 7

при j = 3 л₃⁽⁵⁾ + с₃₆ = 6 + ? = ?

при j = 4 л₄⁽⁵⁾ + с₄₆ = 5 + 1 = 6

при j = 5 л₅⁽⁵⁾ + с₅₆ = 3 + ? = ?

при j = 6 л₆⁽⁵⁾ + с₆₆ = 2 + ? = ?

при j = 7 л₇⁽⁵⁾ + с₇₆ = 9 + 2 = 11

Следовательно л₆⁽⁶⁾ = 2

л₇⁽⁶⁾ = min{л_j⁽⁵⁾ + c_j7}, 1 ? j ? 7

при j = 1 л₁⁽⁵⁾ + с₁₇ = 0 + 12 = 12

при j = 2 л₂⁽⁵⁾ + с₂₇ = 5 + 4 = 9

при j = 3 л₃⁽⁵⁾ + с₃₇ = 6 + 2 = 8

при j = 4 л₄⁽⁵⁾ + с₄₇ = 5 + ? = ?

при j = 5 л₅⁽⁵⁾ + с₅₇ = 3 + ? = ?

при j = 6 л₆⁽⁵⁾ + с₆₇ = 2 + 8 = 10

при j = 7 л₇⁽⁵⁾ + с₇₇ = 9 + ? = ?

Следовательно л₇⁽⁶⁾ = 8

Заполним таблицу получившимися значениями

	лi(0)	лi(1)	лi(2)	лi(3)	лi(4)	лi(5)	лi(6)
i1	0	0	0	0	0	0	0
i2	?	?	10	5	5	5	5
i3	?	9	9	9	6	6	6
i4	?	?	?	5	5	5	5
i5	?	?	3	3	3	3	3
i6	?	2	2	2	2	2	2
i7	?	12	10	10	9	8	8

Величина л₇⁽⁶⁾ = 8 выражает длину минимального пути из х₁ в х₇ в нагруженном орграфе D. Найдем минимальное число k ? 1, при котором выполняется равенство л₇^(k+1) = л₇⁽⁶⁾. Получаем, что k = 5. Таким образом, минимальное число дуг в пути среди всех минимальных путей из х₁ в х₇ в нагруженном орграфе D равняется 5. Определим теперь последовательность номеров i₁, i₂, i₃, i₄, i₅, i₆, где i₁ = 7, удовлетворяющих (4), для этого используем формулу (2). Из таблицы получаем, что в качестве такой последовательности гадо взять номера 7, 3, 4, 5, 6, 1, так как

л₃⁽⁴⁾ +c₃₇ = 6 + 2 = л₇⁽⁵⁾

л₄⁽³⁾ +c₄₃ = 5 + 1 = л₃⁽⁴⁾

л₅⁽²⁾ +c₅₄ = 3 + 2 = л₄⁽³⁾

л₆⁽¹⁾ +c₆₅ = 2 + 1 = л₅⁽²⁾

л₁⁽⁰⁾ +c₁₆ = 0 + 2 = л₆⁽¹⁾

Тогда х₁ х₆ х₅ х₄ х₃ х₇ - искомый минимальный путь из х₁ в х₇ в нагруженном орграфе D, причем он содержит минимальное число дуг среди всех возможных минимальных путей из х₁ в х₇.

2.2 Построение матрицы смежности

Рисунок 1

Построим матрицу смежности для данного орграфа.

2.3 Построение матрицы инцидентности

Произвольно обозначим ребра орграфа Х1, Х2, …, Х23, как показано на рисунке 2.

орграф граф инцидентность матрица

Рисунок 2

Построим матрицу инцидентности для данного орграфа.

Заключение

Приведенный в данной работе алгоритм позволяет по таблице величин л_i^(k), i = 1, 2, …, n, k = 0, 1, …, n - 1, определить минимальный путь в нагруженном орграфе D из х₁ в любую достижимую вершину, причем из всех возможных путей он выделяет путь с наименьшим числом дуг.

Список литературы

1. Нефедов В. Н. Курс дискретной математики / В. Н. Нефедов, В. А. Осипова. Изд - во МАИ, 2012. 262 с.

2. Емеличев В. А. Лекции по теории графов. / В. А. Емеличев, О. И. Мельников. М.: Наука, Гл. ред. физ. - мат. лит., 1990. 384 с.

3. Свами М. Графы, сети, алгоритмы / М. Свами, К. Тхуласираман. М.: Мир, 2014. 455 с.

...