Как найти длину пути между вершинами графа

Алгоритм Дейкстры. Разбор Задач

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

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

Введение

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

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

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

Как ведёт себя алгоритм Дейкстры на исходном графе, мы разберём, когда выпишем алгоритм. Но для начала зададимся другим вопросом: «почему не применить поиск в ширину для нашего графа?». Известно, что метод BFS находит оптимальный путь от произвольной вершины в ориентированном графе до любой другой вершины, но это справедливо только для рёбер с единичным весом.

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

Чтобы этого избежать предлагается использовать алгоритм Дейкстры. Опишем его:

Инициализация:

Основный цикл алгоритма:

• Пока все вершины не исследованы (или формально ), повторяем:

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

Примеры работы

Рассмотрим граф выше, в нём будем искать пути от до всего остального.

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

Теперь рассмотрим граф с отрицательными весами, упомянутый выше. Напомню, алгоритм Дейкстры на таком графе может работать некорректно.

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

Оценка сложности алгоритма

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

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

Что еще можно сказать о куче:

• это сбалансированное бинарное дерево,
• ключ текущего узла всегда меньше, либо равен ключей дочерних узлов.

Интересную задачу с использованием куч я разбирал ранее в этом посте.

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

Далее перейдём к разбору задач!

Задача №1

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

Решение

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

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

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

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

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

Стоит пояснить, что поиск по осуществляется, только для существующих связей а это вес ребра .

Задача №2

Предлагается решить более практическую задачу. Пусть городов, между ними существуют пути, заданные массивом edges[i] = [city_a, city_b, distance_ab], а также дано целое число mileage.

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

Стоит отметить, что граф неориентированый, т.е. по пути между городами можно двигаться в обе стороны, а длина пути между городами a и c может быть получена как сумма длин путей a -> b и b -> c, если есть маршрут a -> b -> c

Решение

С решением данной проблемы нам поможет алгоритм Дейкстры и описанная выше реализация с помощью кучи. Поставщиком этой структуры данных станет библиотека heapq в Python.

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

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

Давайте опишем функцию решения:

def least_reachable_city(n, edges, mileage):
        """
        входные параметры:
            n --- количество городов,
            edges --- тройки (a, b, distance_ab),
            mileage --- максимально допустимое расстояние между городами 
            для соседства
        """
        # заполняем список смежности (adjacency list), в нашем случае это 
        # словарь, в котором ключи это города, а значения --- пары 
        # (<другой_город>, <расстояние_до_него>)

        graph = {}
        for u, v, w in edges:
            if graph.get(u, None) is None:
                graph[u] = [(v, w)]
            else:
                graph[u].append((v, w))
            if graph.get(v, None) is None:
                graph[v] = [(u, w)]
            else:
                graph[v].append((u, w))
        
        # локально объявим функцию, которая будет считать кратчайшие пути в 
        # графе от вершины, до всех вершин, удовлетворяющих условию
        def num_reachable_neighbors(city):
            # создаем кучу, из одного элемента с парой, задающей нулевую 
            # длину пути до самого исходного города
            heap = [(0, city)]
            # и массив, содержащий города и кратчайшие 
            # расстояния до них от исходного
            distances = {}
            # затем, пока куча не пуста, извлекаем ближайший 
            # от посещенных городов город
            while heap:
                currDist, neighb = heapq.heappop(heap)
                # если кратчайшее ребро ведет к городу, где мы уже знаем 
                # оптимальный маршрут, то завершаем итерацию
                if neighb in distances:
                    continue
                # в остальных случаях, и если сосед не является отправным 
                # городом, мы добавляем новую запись в массив кратчайших расстояний
                if neighb != city:    
                    distances[neighb] = currDist
                # обрабатываем всех смежных городов с соседом, добавляя их в кучу 
                # но только если: а) до них еще не известен кратчайший маршрут и б) путь до них через neighb не выходит за пределы mileage
                for node, d in graph[neighb]:
                    if node in distances:
                        continue
                    if currDist + d <= mileage:
                        heapq.heappush(heap, (currDist + d, node))
            # возвращаем количество городов, прошедших проверку
            return len(distances)
        
        # выполним поиск соседей для каждого из городов
        cities_neighbors = {num_reachable_neighbors(city): city for city in range(n)}
        # вернём номер города, у которого наименьшее число соседей
        # в пределах досигаемости
        return cities_neighbors[min(cities_neighbors)]

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

Заключение

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

Стоит еще раз отметить, что алгоритм не работает, когда в графе существуют отрицательные веса. Для этого существует подход динамического программирования — алгоритм Беллмана – Форда, что может послужить темой другой статьи. Несмотря на это, алгоритм Дейкстры является представителем идеального баланса простоты и мощи, для решения прикладных задач.

Статья подготовлена в преддверии старта курса «Алгоритмы для разработчиков». Узнать о курсе подробнее, а также зарегистрироваться на бесплатный демоурок можно по ссылке.

Информация

[1] Условия задач взяты из книги «Algorithms Illuminated: Part 2: Graph Algorithms and Data Structures» от Tim Roughgarden,
[2] и с сайта leetcode.com.
[3] Решения авторские.

vector<int> bfs(int s) {
    // длина любого кратчайшего пути не превосходит n - 1,
    // поэтому n - достаточное значение для "бесконечности";
    // после работы алгоритма dist[v] = n, если v недостижима из s
    vector<int> dist(n, n);
    dist[s] = 0;
    queue<int> q;
    q.push(s);

    while (!q.empty()) {
        int v = q.front();
        q.pop();
        for (int u : adj[v]) {
            if (dist[u] > dist[v] + 1) {
                dist[u] = dist[v] + 1;
                q.push(u);
            }
        }
    }

    return dist;
}

// теперь bfs принимает 2 вершины, между которыми ищется пути
// bfs возвращает кратчайший путь из s в t, или же пустой vector, если пути нет
vector<int> bfs(int s, int t) {
    vector<int> dist(n, n);
    vector<int> p(n, -1);
    dist[s] = 0;
    queue<int> q;
    q.push(s);

    while (!q.empty()) {
        int v = q.front();
        q.pop();
        for (int u : adj[v]) {
            if (dist[u] > dist[v] + 1) {
                p[u] = v;
                dist[u] = dist[v] + 1;
                q.push(u);
            }
        }
    }
    
    // если пути не существует, возвращаем пустой vector
    if (dist[t] == n) {
        return {};
    }

    vector<int> path;
    while (t != -1) {
        path.push_back(t);
        t = p[t];
    }
    
    // путь был рассмотрен в обратном порядке, поэтому его нужно перевернуть
    reverse(path.begin(), path.end());
    return path;
}

// INF - infinity - бесконечность
const long long INF = (long long) 1e18 + 1;

vector<long long> dijkstra(int s) {
    vector<long long> dist(n, INF);
    dist[s] = 0;
    vector<bool> used(n);
    
    while (true) {
        // находим вершину, из которой будем релаксировать
        int v = -1;
        for (int i = 0; i < n; i++) {
            if (!used[i] && (v == -1 || dist[i] < dist[v])) {
                v = i;
            }
        }
        
        // если не нашли подходящую вершину, прекращаем работу алгоритма
        if (v == -1) {
            break;
        }
        
        for (auto &e : adj[v]) {
            int u = e.first;
            int len = e.second;
            if (dist[u] > dist[v] + len) {
                dist[u] = dist[v] + len;
            }
        }
    }
    
    return dist;
}

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

Например, существует два пути [0—3—4—6—7] а также [0—3—5—6—7] от вершины 0 к вершине 7 на следующем Graphе. Напротив, нет пути из вершины 7 в любую другую вершину.

Потренируйтесь в этой проблеме

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

Этот подход демонстрируется ниже на C++, Java и Python:

Как напечатать полный путь?

Идея состоит в том, чтобы сохранить полный путь между исходной и целевой вершинами в массиве, используя рекурсия. Мы можем легко добиться этого, используя Поиск в глубину (DFS) определить путь между вершинами. Это показано ниже на C++, Java и Python:

Временная сложность приведенных выше решений равна O(V + E), куда V а также E — общее количество вершин и ребер в Graph соответственно.

 
Упражнение: Расширьте решение, чтобы напечатать все пути между заданными вершинами (ссылка на решение)

Пусть
—
граф (или псевдограф).

Расстояние в графе удовлетворяют
аксиомам метрики

1) 
,

2) 
 (не
в ориентированном графе)

3) 

4) 
 в
связном графе (не в ориентированном
графе).

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

• Определение
  Диаметром графа G
  называется величина
  .

Пусть
.

• Определение
  Максимальным удалением (эксцентриситетом)
  в графе G
  от вершины
   называется
  величина
  .

• Определение
  Радиусом графа G
  называется величина
  

• Определение
  Центром графа Gназывается
  любая вершина
   такая,
  что
  .

Алгоритм фронта волны

Пусть
 ориентированный
граф с n³2 вершинами и v,w
(v¹w)
– заданные вершины из V.

Алгоритм поиска
минимального пути из
 в

 в
ориентированном графе

(алгоритм
фронта волны).

1)     Помечаем
вершину
 индексом
0, затем помечаем вершины Î образу вершины

 индексом
1. Обозначаем их FW₁
(v).
Полагаем k=1.

2)       
Если
 или
k=n-1,
и одновременно
то вершина
 не
достижима из
.
Работа алгоритма заканчивается.

В противном случае продолжаем:

3)       
Если
,
то переходим к шагу 4.

В противном случае мы нашли
минимальный путь из
 в

 и
его длина равна k.
Последовательность вершин

есть этот минимальный путь. Работа
завершается.

4)       
Помечаем индексом k+1
все непомеченные вершины, которые
принадлежат образу множества вершин c
индексом k.
Множество вершин с индексом k+1
обозначаем
.
Присваиваем k:=k+1
и переходим к 2).

• Замечания
  Множество
   называется
  фронтом волны k^го
  уровня.

·         
Вершины
 могут
быть выделены неоднозначно, что
соответствует случаю, если
 несколько
минимальных путей из
 в

.

Чтобы найти расстояния в
ориентированном графе, необходимо
составить матрицу минимальных расстояний
R(D)между
его вершинами. Это квадратная матрица
размерности
,
элементы главной диагонали которой
равны нулю (,
i=1,..,n).

Сначала составляем матрицу
смежности. Затем переносим единицы из
матрицы смежности в матрицу минимальных
расстояний (,
если
).
Далее построчно заполняем матрицу
следующим образом.

Рассматриваем первую строку,
в которой есть единицы. Пусть это строка
− i-тая
и на пересечении с j-тым
столбцом стоит единица (то есть
).
Это значит, что из вершины
 можно
попасть в вершину
 за
один шаг. Рассматриваем j-тую
сроку (строку стоит вводить в рассмотрение,
если она содержит хотя бы одну единицу).
Пусть элемент
.
Тогда из вершины
 в
вершину
 можно
попасть за два шага.

Таким образом, можно записать

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

• Пример Найдем
  расстояния в ориентированном графе D,
  изображенном на рис. 7. В данной задаче
  количество вершин n=7,
  следовательно, матрицы смежности 
  и минимальных расстояний между вершинами
  ориентированного графа Dбудут
  иметь размерность 7×7.

Рис.7.

Матрица смежности:

                  

.

Начинаем заполнять матрицу
R(D)
минимальных расстояний: сначала ставим
нули по главной диагоналии r_ij=a_ij,
если a_ij=1,
(т.е. переносим единицы из матрицы
смежности). Рассматриваем первую строку.
Здесь есть две единицы, то есть из первой
вершины за один шаг можно попасть во
вторую и шестую. Из второй вершины можно
попасть за один шаг в третью (путь в
первую вершину нас не интересует),
следовательно, можно записать
.
Из шестой вершины можем добраться за
один шаг в пятую и седьмую, а значит,
,

.
Теперь ищем маршруты, исходящие из
первой вершины, состоящие из 3 шагов: за
2 шага идем в третью вершину, оттуда за
один шаг попадаем в четвертую, поэтому

.
В итоге получаем следующую матрицу:

Таким образом, диаметром
исследуемого ориентированного графа
будет
.

Для каждой вершины заданного
ориентированного графа найдем максимальное
удаление (эксцентриситет) в графе G от
вершины нее по формуле, которая была
приведена выше
:
r(v_i)
− максимальное из расстояний, стоящих
в i-той
строке. Таким образом,

r(v₁)=3,
r(v₂)=3,
r(v₃)=5,
r(v₄)=4,
r(v₅)=2,
r(v₆)=2,
r(v₇)=3.

Значит, радиусом графа G
будет

Соответственно, центрами
графа G будут
вершины v₅
иv₆
, так как величины их эксцентриситетов
совпадают с величиной радиуса.

Опишем теперь нахождение
минимального пути из вершины v₃
в вершинуv₆
по алгоритму фронта волны. Обозначим
вершину v₃
как V₀,
а вершину v₆—
как W
(см. рис. 8). Множество вершин, принадлежащих
образу V₀,
состоит из одного элемента — это вершина
v₄,
которую, согласно алгоритму, обозначаем
как V₁:
FW₁(v₃)={v₄}.

Поскольку искомая вершина
не принадлежит фронту волны первого
уровня
,
продолжаем работу алгоритма. Строим
фронт волны второго уровня — это множество
вершин, принадлежащих образу вершиныV₁:
FW₂(v₃)={v₇},
обозначаем v₇≡V₂.
В образ вершины V₂
входят две вершины —v₅
и v₄,
но, так как v₄
уже была помечена как V₀,
то фронт волны третьего уровня состоит
из одного элемента: FW₃(v₃)={v₅},
v₅≡V₃.
Из непомеченных вершин в образ вершины
V₃
входят v₁
и v₂,
соответственно, FW₄(v₃)={v₁,
v₂},
v₁≡V₄,
v₂≡V₄.
Теперь помечены все вершины, кроме v₆,
которая входит в образ вершины
,
то есть FW₅(v₃)={v₆≡W},
работа алгоритма закончена. Минимальный
путь (5 шагов) из вершины v₃
в вершинуv₆
выглядит так: v₃v₄v₇v₅v₁v₆.

Рис.8.

Минимальный путь в
нагруженном ориентированном графе по
методу Форда-Беллмана

Найти минимальный путь в
нагруженном ориентированном графе из
вершины
 в
вершину
 по
методу Форда-Беллмана.

Рассмотрим сначала общую
задачу – нахождения минимального пути
из вершины v_нач
в v_кон.

Пусть D=(V,X)
– нагруженный ориентированный граф,
V={v₁,…,v_n},
n>1.
Введем величины
,
где i=1,…,n,
k=0,1,2,…,n–1.

Для каждого фиксированного
i и
k
величина
 равна
длине минимального пути среди путей из
v_нач
в v_i
содержащих не более k
дуг. Если путей нет, то
.

Положим также
.

Составляем матрицу длин
дуг C(D)=[c_ij]
порядка n:

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

                     

.                 
(3.1)

Алгоритм Форда-Беллмана
нахождения минимального пути в нагруженном
ориентированном графе D из v_нач
в v_кон.(
v_нач
≠ v_кон).

(
записываем в виде матрицы, i—
строка, k-столбец).

1)     Составляем
таблицу
,
i=1,…,n,
k=0,…,n-1.
Если
,
то пути из v_нач
в v_кон
нет. Конец алгоритма.

2)     Если
 то
это число выражает длину любого
минимального пути из v_нач
в v_кон.
Найдем минимальное k₁³1,
при котором
.
По определению
 получим,
что k₁—
минимальное число дуг в пути среди всех
минимальных путей из v_начв
v_кон.

3)     Затем
определяем номера i₂,…,

 такие,
что

,

,

,

то есть восстанавливаем по
составленной таблице и матрице стоимости
искомый минимальный путь из v_нач
в v_кон.

• Пример

Найдем минимальный путь из
вершины v₂
в v₆
в ориентированном нагруженном графе
D,
изображенном на рис. 9. В рассматриваемом
графе количество вершин n=7,
следовательно, матрица длин дуг
ориентированного графа Dбудет
иметь размерность 7×7.

Рис.
9.

Матрица длин дуг для рассматриваемого
графа будет выглядеть следующим образом:

                

.

Согласно алгоритму, составляем
таблицу стоимости минимальных путей
из вершины v₂
в вершину v_i
не более, чем за k
шагов, k=0,…n-1
(n=7,
следовательно, k=0,…6).
Как было определено выше,
,
и
 для
всех остальных вершин v_i≠
v₂,
то есть первый столбец таблицы состоит
из элементов, равных
,
кроме элемента
.
Второй столбец таблицы повторяет вторую
строку матрицы стоимости, поскольку
представляет собой стоимость возможных
путей из вершины v₂
за один шаг. Далее по формуле (3.1) находим
по столбцам все оставшиеся элементы
таблицы. Например, чтобы найти элемент

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

В конечном итоге получаем следующую
таблицу:

Теперь необходимо по
построенной таблице и по матрице C(D)
восстановить минимальный путь из вершины
v₂
в v₆,
который будет строиться с конца, то
есть, начиная с вершины v6.
Для этого выбираем минимальное из чисел,
стоящих в строке, соответствующей v₆
в таблице. Это число – 21 – длина
минимального искомого пути. В первый
раз такая длина была получена при
количестве шагов, равном 4. В вершину v₆
мы можем попасть за один шаг из вершин
v₁
и v₇
(длина соответствующих дуг 8 и 5
соответственно – данные из матрицы
C(D)).
Выбираем минимальную по длине из этих
дуг. Далее, в вершину v₇
можно попасть из v₄
и v₅(длина
соответствующих дуг 7 и 3 соответственно).
Продолжая аналогичным образом, найдем
искомый путь за 4 шага минимальной длины
из вершины v₂
в v₆:
v₂v₃v₅v₇v₆.

78