Кратчайшие пути. 
Алгоритмы их нахождения

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ ТЮМЕНСКОЙ ОБЛАСТИ ТЮМЕНСКАЯ ГОСУДАРСТВЕННАЯ АКАДЕМИЯ МИРОВОЙ ЭКОНОМИКИ, УПРАВЛЕНИЯ И ПРАВА ФАКУЛЬТЕТ УПРАВЛЕНИЯ

Кафедра математики и информатики

Курсовая работа

по дисциплине: «Технологии программирования»

на тему: «Кратчайшие пути. Алгоритмы их нахождения»

Выполнил:

студент 481 группы Батусов И.В.

Проверил:

старший преподаватель Наурусова Г. А.

ТЮМЕНЬ 2010

• Введение
• Глава 1. Анализ теоретического материала
• 1.1 Граф
• 1.2 Пути и маршруты
• 1.2.1 Волновой алгоритм
• 1.2.2 Алгоритм Дейкстры
• 1.2.3 Алгоритм Беллмана-Форда
• 1.2.4 Алгоритм Флойда — Уоршелла
• 1.2.5 Алгоритм Йена
• Глава 2. Разработка программы поиска кратчайших путей в графе
• 2.1 Постановка задачи
• 2.2 Технические задачи
• 2.3 Кодовая реализация
• Заключение
• Список использованной литературы
• Приложения

Благодаря своему широкому применению, теория о нахождении кратчайших путей в последнее время интенсивно развивается.

Нахождение кратчайшего пути — жизненно необходимо и используется практически везде, начиная от нахождения оптимального маршрута между двумя объектами на местности (например, кратчайший путь от дома до университета), в системах автопилота, для нахождения оптимального маршрута при перевозках, коммутации информационного пакета в Internet и т. п.

Кратчайший путь рассматривается при помощи некоторого математического объекта, называемого графом.

Существуют три наиболее эффективных алгоритма нахождения кратчайшего пути:

алгоритм Дейкстры (используется для нахождения оптимального маршрута между двумя вершинами);

алгоритм Флойда (для нахождения оптимального маршрута между всеми парами вершин);

алгоритм Йена (для нахождения k-оптимальных маршрутов между двумя вершинами).

Объект курсовой работы: кратчайшие пути

Предмет работы: алгоритмы нахождения кратчайших путей.

Цель: с помощью программы Microsoft Visual Basic Express Edition разработать приложение, позволяющее искать кратчайшие пути в произвольном графе.

Задачи, решение которых необходимо для достижения поставленной цели:

1) Исследование графа

2) Обзор понятий: пути и маршруты; дать определение кратчайшего пути

3) Изучение алгоритмов поиска кратчайших путей

4) Постановка технической задачи для разработки программы поиска кратчайших путей

5) Разработка программы поиска кратчайших путей

Актуальность данной работы заключается в том, что часто бывает полезно и наглядно изображать некоторую ситуацию в виде графов. Графы встречаются во многих областях под разными названиями: «структуры» в гражданском строительстве, «сети» в электротехнике, «социограммы» в социологии и экономике, «молекулярные структуры» в химии, «дорожные карты», электрические или газовые «распределительные сети» и так далее. И по этому крайне важно уметь находить кратчайшие пути в графе.

Глава 1. Анализ теоретического материала

1.1 Граф

Граф G задается множеством точек или вершин x_1, х₂,…, х_{n (}которое обозначается через X) и множеством линий или ребер a_1, а₂…, а_n (которое обозначается символом А), соединяющих между собой все или часть этих точек. Таким образом, граф G полностью задается (и обозначается) парой (X, А).

Если ребра из множества А ориентированы, что обычно показывается стрелкой, то они называются дугами, и граф с такими ребрами называется ориентированным графом (рис. 1.1 (а)). Если ребра не имеют ориентации, то граф называется неориентированным (рис. 1.1 (6)). В случае когда G = (X, А) является ориентированным графом и мы хотим пренебречь направленностью дуг из множества А, то неориентированный граф, соответствующий G, будем обозначать как G = (X, А).

Далее, когда дуга обозначается упорядоченной парой, состоящей из начальной и конечной вершин (т.е. двумя концевыми вершинами дуги), ее направление предполагается заданным от первой вершины ко второй. Так, например, на рис. 1.1 (а) обозначение (х₁, х₂) относится к дуге а_2, а (х₂, х₁) — к дуге а₂.

Другое, употребляемое чаще описание ориентированного графа G состоит в задании множества вершин X и соответствия Г, которое показывает, как между собой связаны вершины. Соответствие Г называется отображением множества X в X, а граф в этом случае обозначается парой G = (X, Г).

Для графа на рис. 1.1 (а) имеем Г (x₁) = {х₂, х₅}, т. е. вершины х₂ и х₅ являются конечными вершинами дуг, у которых начальной вершиной является х_1.

Г (x₂) ={x₁, x₃},

Г (x₃) ={x₁},

Г (x₄) =Ш-пустое множество,

Г (x₅) ={x₄}

Рис. 1.1 (а) Ориентированный граф, (б) Неориентированный граф, (в) Смешанный граф.

В случае неориентированного графа или графа, содержащего и дуги, и неориентированные ребра (см., например, графы, изображенные на рис. 1.1 (6) и 1.1 (в)), предполагается, что соответствие Г задает такой эквивалентный, ориентированный граф, который получается из исходного графа заменой каждого неориентированного ребра двумя противоположно направленными дугами, соединяющими те же самые вершины. Так, например, для графа, приведенного на рис. 1.1 (6), имеем Г (х₅) = {х_1, х₃, x₄},

Г (х₁) = {х₅} и т. д.

Поскольку Г (x₁) представляет собой множество таких вершин x_i Є Х, для которых в графе G существует дуга (х_i, x_j), то через Г^-1 (x_i) естественно обозначить множество вершин х_k, для которых в G существует дуга (х_k, x_i). Отношение Г^-1 (х_i) принято называть обратным соответствием. Для графа, изображенного на рис 1.1 (а), имеем

Г^-1 (x₁) ={x₂. x₃},

Г^-1 (x₂) ={x₁},

и т.д.

Вполне очевидно, что для неориентированного графа Г^-1 (x_i) = Г (х_i) для всех х₁ Є X.

Когда отображение Г действует не на одну вершину, а на множество вершин Х_q = {х₁, x₂, …, х_q}, то под Г (Х_q) понимают объединение

Г (x₁) U Г (x₂) U… U Г (x_q),

т.е. Г (Х_q) является множеством таких вершин х_i Є X, что для каждой из них существует дуга (х_i, х_j,) в G, где х_i Є Х_q. Для графа, приведенного на рис. 1.1 (а), Г ({x₂, х₅}) = {х₁, х_3,, x₄} и Г ({x₁, х₃}) = {х_2,, х₅, х₁}

Отображение Г (Г (x_i)) записывается как Г^{2 (}x_i). Аналогично «тройное» отображение Г (Г (Г (х_i))) записывается как Г^{3 (}x_i) и т. д. Для графа, показанного на рис. 1.1 (а), имеем:

Г² (x₁) = Г (Г (x₁)) = Г ({х₂, x₅}) = {х₁, х₃, x₄},

Г³ (x₁) =Г (Г² (x₁)) =Г ({x₁, x₃, x₄}) ={x₁, x₃, x₅}

и т.д.

Аналогично понимаются обозначения ^Г-2 (х_i), ^Г-3 (х_i) и т. Д

1.2 Пути и маршруты

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

Дуги, имеющие общие концевые вершины, называются смежными.

Ориентированной цепью (орцепью) называется такой путь, в котором каждая дуга используется не больше одного раза. Простой орцепью называется такой путь, в котором каждая вершина используется не более одного раза. Очевидно, что простая орцепь является также орцепью, но обратное утверждение неверно. Маршрут есть неориентированный «двойник» пути, и это понятие рассматривается в тех случаях, когда можно пренебречь направленностью дуг в графе. Иногда дугам графа сопоставляются числа называемые весом, или длиной, или стоимостью (ценой) дуги. Тогда граф называется графом со взвешенными дугами. Иногда веса приписываются вершинам графа, и тогда получается граф с взвешенными вершинами. Если в графе веса приписаны и дугам, и вершинам, то он называется просто взвешенным. Вес пути в графе определяется как сумма весов ребер этого пути. Кратчайшим путем между двумя вершинами называется путь наименьшего веса, соединяющий эти вершины.

Кратчайший путь можно найти с помощью следующих алгоритмов:

Волновой алгоритм

Алгоритм Дейкстры

Алгоритм Беллмана — Форда

Алгоритм Флойда — Уоршелла

Алгоритм Йена

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

1.2.1 Волновой алгоритм

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

Суть алгоритма заключается в следующем. На двумерной клетчатой карте (матрице), состоящей из «проходимых» и «непроходимых» клеток, обозначена клетка старта и клетка финиша. Цель алгоритма — проложить кратчайший путь от клетки старта к клетке финиша, если это, конечно, возможно. От старта во все направления распространяется волна, причем каждая пройденная волной клетка помечается как «пройденная». Волна, в свою очередь, не может проходить через клетки помеченные как «пройденные» или «непроходимые». Волна движется, пока не достигнет точки финиша или пока не останется не пройденных клеток. Если волна прошла все доступные клетки, но так и не достигла клетку финиша, значит, путь от старта до финиша проложить невозможно. После достижения волной финиша, от старта прокладывается путь до финиша и сохраняется в массиве.

Волновой алгоритм состоит из двух этапов.

На первом этапе моделируется процесс распространения волны от ячейки, А по свободным ячейкам ДРП (Дискретного Рабочего Поля).

При распространении волны от ячейки А, алгоритм последовательно строит f1 (А) — первый, f2 (А) — второй,., fk (А) — k-ый ее фронты. Если проведение пути возможно, то на k+1-ом шаге окажется, что ячейка В є Оk+1 (А). Если в следующий фронт не удается включить ни одной свободной ячейки, т. е. Оk (А) = Оk+1 (А), то при данных условиях путь провести невозможно.

Т.о. первый этап волнового алгоритма определяет возможность проведения пути между, А и В.

На втором этапе, начиная с ячейки В, по определенным правилам, выполняется переход от ячейки k-ого фронта к ячейке k-1 фронта до ячейки А. Пройденные ячейки — искомый путь.

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

Распространение волны заключается в присваивании ячейкам, соседним с ячейкой предыдущего фронта, значения весовой функции. Вес ячейки k-ого фронта Pk является функцией веса ячейки k-1-ого фронта.

Метод кодирования ячеек по mod3 базируется на основном требовании к весам: Pk-1? Pk? Pk+1. Ячейкам, включенным в последующие фронты, можно присваивать не сами веса, а их значения по mod3 (1,2,3,1,2,3,.). Проведение пути заключается в отслеживании отметок (1,2,3). Если ячейка имеет несколько соседних ячеек с одинаковыми метками, то используется правило приоритетных направлений.

При движении от ячейки В к ячейке, А используется следующее правило приоритетов: <,^, >, v.

1.2.2 Алгоритм Дейкстры

Алгоримтм Демйкстры (Dijkstra's algorithm) — алгоритм находит кратчайшее расстояние от одной из вершин графа до всех остальных (если таковые имеются). Алгоритм работает только для графов без рёбер отрицательного веса. Алгоритм широко применяется в программировании и технологиях, например, его использует протокол OSPF для устранения кольцевых маршрутов.

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

Сначала помечается исходная вершина; следующей, очевидно, будет помечена вершина, ближайшая к исходной, и смежная с ней.

Пусть на каком-то шаге уже помечено несколько вершин. Известны кратчайшие пути, ведущие из исходной вершины к помеченным. Для каждой из непомеченных вершин проделаем следующее:

Рассмотрим все дуги, ведущие из помеченных вершин в одну непомеченную. Каждая такая дуга является последней дугой на пути из исходной вершины в эту непомеченную.

Выберем из этих путей кратчайший. А затем выберем среди них самый короткий ко всем непомеченным вершинам, и пометим вершину, к которой он ведет.

Алгоритм завершится, когда будут помечены все достижимые вершины.

В результате работы алгоритма Дейкстры строится Дерево кратчайших путей.

1.2.3 Алгоритм Беллмана-Форда

Алгоритм Беллмана — Форда применяется для нахождения кратчайшего расстояния от вершины [s] до остальных вершин. Одна из его ключевых особенностей, отличающая его от алгоритма Дейкстры, заключается в том, что он способен работать на графах, где вес ребер может быть задан отрицательным числом. Алгоритм может обнаруживать побочное явление таких графов — циклы отрицательной величины по которым можно вечно крутиться, уменьшая расстояние до вершин. Процесс не закончится. Поэтому, цикл проверки вершин ограничен числом N (числом самих вершин). Этого достаточно для того, чтобы просчитать минимальное расстояние до любой вершины, а главное алгоритм в любом случае завершится.

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

1.2.4 Алгоритм Флойда — Уоршелла

Алгоритм Флойда — Уоршелла — динамический алгоритм для нахождения кратчайших расстояний между всеми вершинами взвешенного ориентированного графа.

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

Следует заметить, что если в графе существует контур отрицательной сумарной длины, то вес любого пути, проходящего через вершину из этого контура, можно сделать сколь угодно малой, «прокрутившись» в контуре необходимое количество раз. Поэтому поставленная задача разрешима не всегда. В случае описанном выше, алгоритм Флойда прекращает свою работу. Останавливаясь подробнее надо заметить, что если граф неориентированный (W [i, j] - симметрична), то ребро с отрицательным весом является как раз таким контуром (туда-сюда можно бегать пока не сделаем вес достаточно малым)

Алгоритм Флойда предполагает последовательное преобразование матрицы весов W. В конечном итоге получаем матрицу, элементы d [i, j] которой представляют из себя вес минимального пути соединяющего i и j вершины.

На выходе получаем матрицу D минимальных весов и матрицу P при помощи которой можно восстановить путь минимального веса следующим образом: значение p [i, j] будет равно номеру последней вершины в пути между i и j. Переменная s на выходе равна 1, если алгоритм отработал полностью, и нулю, если в ходе работы алгоритма найден контур отрицательного веса.

1.2.5 Алгоритм Йена

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

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

Пошаговое описание:

Найти минимальный путь P1= (v11,., v1L [1]). Положить k = 2. Включить P1 в результирующий список.

Положить MinW равным бесконечности. Найти отклонение минимального веса, от (k-1) — го кратчайшего пути Pk-1 для всех i=1,2,., L [k-1], выполняя для каждого i шаги с 3-го по 6-й.

Проверить, совпадает ли подпуть, образованный первыми i вершинами пути Pk-1, с подпутем, образованным первыми i вершинами любого из путей j=1,2,., k-1). Если да, положить W [vk-1i, vji+1] равным бесконечности в противном случае ничего не изменять (чтобы в дальнейшем исключить получение в результат одних и тех же путей).

Используя алгоритм нахождения кратчайшего пути, найти пути от vk-1i к u2, исключая из рассмотрения корни (vk-11,., vk-1i) (чтобы исключить петли), для этого достаточно положить равными бесконечности элементы столбцов и строк матрицы W, соответствующие вершинам входящим в корень.

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

Восстановить исходную матрицу весов W и возвратиться к шагу 3.

Поместить путь минимального веса (MinW), найденный в результате выполнения шагов с 3 по 6, в результирующий список. Если k = K, то алгоритм заканчивает работу, иначе увеличить k на единицу и вернуться к шагу 2.

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

Глава 2. Разработка программы поиска кратчайших путей в графе

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

С помощью программы Microsoft Visual Basic Express Edition разработать приложение, позволяющее находить кратчайшие пути в графе по алгоритму Флойда.

Осуществить:

· ввод произвольного графа с клавиатуры;

· поиск кратчайших путей;

· очистка полей вывода;

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

2.2 Технические задачи

1.

Введение

1.1 Наименование программы Наименование программы: «Алгоритм Флойда» 1.2 Назначение и область применения Программа предназначена для нахождения кратчайших путей между всеми вершинами графа, которая обрабатывает следующие данные:

1.2.1 матрица достижимости 1.2.2 матрица весов ребер 1.2.3 вершину начала пути 1.2.4 вершину конца пути Программа предоставляет форму визуального представления введенных данных.

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

3. Требования к программной документации 3.1 Предварительный состав программной документации Состав программной документации должен включать в себя:

3.1.1 техническое задание;

3.1.2 программный код;

3.1.3 визуальное представление программы.

4. Стадии и этапы разработки 4.2 Этапы разработки На стадии разработки технического задания должен быть выполнен этап разработки, согласования и утверждения настоящего технического задания.

На стадии рабочего проектирования должны быть выполнены перечисленные ниже этапы работ:

1. разработка программы;

2. разработка программного кода;

3. испытания программы.

На стадии внедрения должен быть выполнен этап разработки подготовка и передача программы.

2.3 Кодовая реализация

При запуске программы появляется форма, рисунок 1.

Рис. 1.

При нажатии Файл >Новый граф, рисунок 2, программа запрашивает количество вершин графа для задания размерности массивов

Рис. 2.

n = InputBox («введите количество вершин графа») — 1

ReDim puti (n, n), graf (n, n), ves (n, n), dugi (n, n), vivod (n, n)

далее пользователь вводит матрицу достижимости и матрицу весов ребера, рисунок 3.

Рис. 3.

For i = 0 To n

For j = 0 To n

If j = i Then

graf (i, j) = 0

ves (i, j) = o_O

Else

graf (i, j) = InputBox («если вершина «& j + 1 & «достижима из вершины «& i + 1 & «то ставте 1, иначе оставте 0», 0)

End If

If graf (i, j) = 1 Then

ves (i, j) = InputBox («введите вес ребра» & i + 1 & «—» & j + 1 & ««)

Else: ves (i, j) = o_O

End If

которые выводятся на экран, рисунок 4.

Рис. 4.

RichTextBox1. Text = RichTextBox1. Text & graf (i, j) & ««

If ves (i, j) = o_O Then RichTextBox2. Text = RichTextBox2. Text & «#» & «| «Else RichTextBox2. Text = RichTextBox2. Text & ves (i, j) & «|»

Next

RichTextBox1. Text = RichTextBox1. Text & vbCrLf

RichTextBox2. Text = RichTextBox2. Text & vbCrLf

Next

При нажатии Файл >Рассчитать пути, рисунок 5, программа копирует матрицу весов ребер и создает матрицу путей.

Рис. 5.

For i = 0 To n

For j = 0 To n

dugi (i, j) = ves (i, j)

If ves (i, j) = o_O Then puti (i, j) = «#» Else puti (i, j) = j + 1

Next

Next

Далее проверяются все пути и кратчайшие запоминаются.

For i = 0 To n

For j = 0 To n

For k = 0 To n

If i <> j And dugi (j, i) <> o_O And i <> k And dugi (i, k) <> o_O And (dugi (j, k) = o_O Or dugi (j, k) > dugi (i, k) + dugi (j, i)) Then

puti (j, k) = puti (j, i) & puti (i, k)

dugi (j, k) = dugi (i, k) + dugi (j, i)

End If

Next

Next

Next

Полученные данные выводятся, рисунок 4.

Рис. 4.

For i = 0 To n

For j = 0 To n

If puti (i, j) <> «#» Then puti (i, j) = i + 1 & puti (i, j)

If dugi (i, j) <> o_O Then vivod (i, j) = dugi (i, j) Else vivod (i, j) = «#»

Next

For j = 0 To n

RichTextBox3. Text = RichTextBox3. Text & vivod (i, j) & «| «

RichTextBox4. Text = RichTextBox4. Text & i & puti (i, j) & «| «

Next

RichTextBox3. Text = RichTextBox3. Text & vbCrLf

RichTextBox4. Text = RichTextBox4. Text & vbCrLf

Next

При нажатии Правка >Очистить, рисунок 5, оба поля очищаются

Рис. 5.

RichTextBox1. Text = «»

RichTextBox2. Text = «»

RichTextBox3. Text = «»

RichTextBox4. Text = «»

TextBox1. Text = «»

TextBox2. Text = «»

TextBox3. Text = «»

TextBox4. Text = «»

Для того чтобы найти конкретный путь и его вес требуется ввести начало и конец в поля изображенные на рисунке 6 и нажать нопку «Найти путь»

Рис. 5.

nach = TextBox1. Text

kon = TextBox2. Text

For i = 0 To n

For j = 0 To n

If i = nach — 1 And j = kon — 1 Then

TextBox3. Text = puti (i, j)

TextBox4. Text = vivod (i, j)

End If

Next

Next

Искомый путь и его вес будут выведены в соответствующих полях, рисунок 6.

Рис. 6.

Заключение

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

В I главе была рассмотрена теория графов в общем, изучены понятия путей и маршрутов, подробно рассмотрены такие алгоритмы нахождения кратчайших путей в графе, как волновой алгоритм, алгоритм Дейкстры, алгоритм Белламна-Форда, алгоритм Флойда-Уоршелла и алгоритм Йена. Названные алгоритмы могут найти свое применение в программах для транспортных и коммуникационных сетей, таких как коммутация информационного пакета в Internet, где вершины — роутеры, а ребра это связи между роутерами. Таким образом, чем короче будет путь, тем быстрее пакет достигнет пункта назначения и меньше будут информационные потери.

Во II главе работы были реализованы поставленные задачи. С помощью Microsoft Visual Basic Express Edition был разработан программный продукт «Алгоритм Флойда» для нахождения кратчайших путей графа между всеми его вершинами. Преимуществом данной программы является то, что в ней реализованы принципы динамического программирования, то есть, пользователь сам определяет количество вершин графа, количество ребер (дуг) и их вес. В программе использован алгоритм Флойда — Уоршелла, который помогает последовательно вычислить все значения длин кратчайших путей между вершинами. На каждом шаге алгоритм генерирует две двумерные матрицы, одна из которых содержит длины кратчайших путей между всеми вершинами графа, а другая содержит сами пути.

1. Касьянов В. Н., Евстигнеев В. А. «Графы в программировании: обработка, визуализация и применение», 2003, 1104с.

2. Кормен Т. М. «Алгоритмы. Построение и анализ», 2005, 1296с.

3. ru. wikipedia.org. Электронный ресурс

4. algolist. manual.ru. Электронный ресурс

5. comp-science. narod.ru. Электронный ресурс

6. dmtsoft.ru. Электронный ресурс

7. forum. sources.ru. Электронный ресурс

Приложения

Приложение 1

Тест программы Используемый граф изображен на рисунке 7.

Рис. 7.

Кратчайший путь между вершинами «1» и «5» пролегает через вершину «3». Вес этого пути «8» .