Графы. Алгоритм Дейкстры | OTUS

Курсы

Программирование
iOS Developer. Basic
-23%
Python Developer. Professional
-13%
Golang Developer. Professional
-17%
Python Developer. Basic
-16%
iOS Developer. Professional
-13%
C# ASP.NET Core разработчик
-18%
Unity Game Developer. Professional
-11%
React.js Developer
-12%
Android Developer. Professional
-7%
Software Architect
-12%
C++ Developer. Professional
-8%
Разработчик C#
-8%
Backend-разработчик на PHP
-8%
Архитектура и шаблоны проектирования
-12%
Программист С Разработчик на Spring Framework MS SQL Server Developer AWS для разработчиков Cloud Solution Architecture Разработчик голосовых ассистентов и чат-ботов Vue.js разработчик VOIP инженер Нереляционные базы данных Супер - интенсив по паттернам проектирования Супер-практикум по использованию и настройке GIT IoT-разработчик Advanced Fullstack JavaScript developer Супер-интенсив Azure
Инфраструктура
Мониторинг и логирование: Zabbix, Prometheus, ELK
-17%
DevOps практики и инструменты
-18%
Архитектор сетей
-21%
Инфраструктурная платформа на основе Kubernetes
-22%
Супер-интенсив «IaC Ansible»
-16%
Супер-интенсив по управлению миграциями (DBVC)
-16%
Administrator Linux. Professional
-5%
Administrator Linux.Basic
-10%
Супер-интенсив «ELK»
-10%
Базы данных Сетевой инженер AWS для разработчиков Cloud Solution Architecture Разработчик голосовых ассистентов и чат-ботов Внедрение и работа в DevSecOps Супер-практикум по работе с протоколом BGP Супер - интенсив по паттернам проектирования Супер - интенсив по Kubernetes Супер-интенсив «СУБД в высоконагруженных системах»
Специализации Курсы в разработке Подготовительные курсы
+7 499 938-92-02

Графы. Алгоритм Дейкстры

Статья расскажет о базовых понятиях теории графов, а также о некоторых известных алгоритмах графов. Отдельное внимание будет уделено алгоритмической последовательности Дейкстры (Dijkstra's algorithm).

Из теории

Граф представляет собой абстрактный объект из множества вершин (узлов) и набора ребер – связей между парами вершин. Эта тема чрезвычайно обширна — в той же Википедии соответствующей терминологии уделена целая страница. Более точное определение можно получить в дискретной математике, где изучают графы (их появлению способствовали работы Эйлера).

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

Для примера рассмотрим неориентированный граф G. Он представляет собой упорядоченную пару G:=(V, E), где:

  • E — множество пар вершин (ребер);
  • V — непустое множество вершин (узлов).

Ребра и узлы графа — это его элементы, количество узлов называют порядком, а количество ребер — размером.

Граф_1-1801-73a14e.png

На рисунке ниже представлен связный ацикличный граф — дерево:

Screenshot_2-1801-017108.png

Словарь терминов

В таблице ниже представлена выборка основных терминов из теории алгоритмов графов:

Screenshot_3-1801-955f06.png

Следует рассмотреть главные понятия: 1. Маршрут — конечная последовательность узлов, где каждый узел за исключением последнего соединяется со следующим с помощью ребра. 2. Цепь — маршрут, не имеющий повторяющихся рёбер. Простая цепь — маршрут без повторяющихся узлов. 3. Ориентированный маршрут (путь) в орграфе — конечная последовательность дуг и узлов, где каждый элемент инцидентен как предыдущему, так и последующему. 4. Длина пути (цикла) — количество ребер, составляющих этот путь. 5. Цикл (путь)— цепь, где совпадают первый и последний узел. Путь простой, если ребра не повторяются, а также элементарный, если является простым, и не повторяются узлы. 6. Матрица смежности, матрица инцидентности, список смежности, список ребер — методы представления графов.

Виды графов:

  1. Ориентированный – (орграф) — рёбрам присвоено направление.
  2. Неориентированный – пара узлов упорядоченной не является.
  3. Связный — между любой парой узлов есть хотя бы один путь.
  4. Дерево — связный ациклический граф (нет циклов, между парами вершин есть лишь по одному пути). Здесь корень дерева — это узел, имеющий нулевую степень захода, а листья — узел с нулевой степень исхода.
  5. Взвешенный – каждому ребру поставлено в соответствие определенное число — вес ребра.

Ищем кратчайший путь в графе. Алгоритм Дейкстры

Хорошо известен алгоритм графов, который был изобретён в 1959 году учёным Эдсгером Дейкстрой (Нидерланды). Он позволяет находить кратчайшие пути от одной из вершин до всех остальных. Сегодня алгоритм графов, который создал известный ученый Дейкстра, часто применяется в программировании и других технологиях — в тех же протоколах маршрутизации. В этом алгоритме графов дан взвешенный орграф G(V, E), не имеющий дуг отрицательного веса. Надо найти кратчайшие пути от какой-либо вершины a графа G до остальных узлов.

Идея алгоритма графов следующая: надо определить массив D[], где для любой вершины v будет храниться текущая длина D[v] кратчайшего пути из s в v. Изначально D[s]=0, причем для всех остальных узлов данная длина равна бесконечности (речь идет о некотором значении, которое заведомо больше возможной длины пути).

Также для каждой вершины мы сохраняем v, несмотря на то, помечена она либо ещё нет, то есть определяется булевский массив U[]. Поначалу все узлы не помечены, поэтому первоначальное значение элементов массива — false. Сам дейкстровский алгоритм состоит из n итераций (по числу узлов), а на очередной итерации выбирают вершину v с самой маленькой величиной D[v] среди тех, которые ещё не помечены.

Выбранная вершина v отмечается помеченной, после чего на текущей итерации из узла v выполняются релаксации — просматриваются все ребра (v, to), которые исходят из вершины v, причем для каждого узла to алгоритм пробует улучшить значение D[to].

Если длина текущего ребра = len, то в коде релаксация будет выглядеть следующим образом:

Screenshot_4-1801-5247b8.png

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

Если же не все вершины являются достижимыми из вершины s, тогда значения D[v] так и останутся для них бесконечными. В результате несколько последних итераций алгоритма станут как раз выбирать эти вершины, однако выполнять полезной работы эти итерации не станут (бесконечное расстояние не способно прорелаксировать другие). То есть алгоритм можно сразу останавливать, делая это в тот момент, когда в качестве выбранной вершины будет браться вершина, имеющая бесконечное расстояние.

На рисунке ниже — взвешенный граф, иллюстрирующий работу этого алгоритма графов в программе на C++:

Screenshot_5-1801-eab951.png

А вот и сам код программы:

Screenshot_6-1801-ec83d6.png

Вместо заключения

Ниже будут представлены еще два популярных алгоритма обхода графа — поиск в глубину и поиск в ширину.

Поиск в глубину

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

1-1801-579024.gif

Поиск в ширину

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

2-1801-866e75.gif

Также существуют алгоритмы Форда, Косарайю, Тарьяна и другие.

Algo_970x90-1801-545cb2.png

Источники: • http://inf-w.ru/?page_id=7359; • https://proglib.io/p/graphs-algoguide/.

Не пропустите новые полезные статьи!

Спасибо за подписку!

Мы отправили вам письмо для подтверждения вашего email.
С уважением, OTUS!

Автор
0 комментариев
Для комментирования необходимо авторизоваться