Нахождение кpатчайших пyтей в гpафе


Содержание

АЛГОРИТМЫ НАХОЖДЕНИЯ КРАТЧАЙШИХ ПУТЕЙ НА ГРАФАХ

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

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

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

Построение дерева решений

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

Пример 1. Найти кратчайший путь от вершины 1 до вершины 6 в ориентированном графе, изображенном на рис. 10.1, а. Построим для данного графа матрицу смежности весов (рис. 10.1, б). Символ «прочерк» в матрице смежности обозначает отсутствие связности между соответствующими вершинами. Последовательно просматриваем строки матрицы смежности Л и строим дерево решений.

Дерево поиска для решения данной задачи имеет вид, представленный на рис. 10.2. Из рисунка видно, что существуют шесть различных путей из вершины 1 в вершину 6: (1, 2, 4, 5, 6), (1, 2, 4, 6), (1, 2, 5, 6), (1, 4, 5, 6), (1, 4, 6) и (1, 3, 6). Из этих возможных путей путь (1, 2, 4, 5, 6) — максимальный с длиной, равной 14, и путь (1, 2, 5, 6) — минимальный с длиной 7.

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

Рис. 10.1. Исходный граф (а) и его матрица смежности (б)

Рис. 10.2. Дерево перебора решений

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

Дерево решений показывает все возможные пути. Имеется шесть вариантов путей от первой до шестой вершины. Кратчайший путь равен x-V2-Vs— V6).

06. Задача о кратчайшем пути в графе

Граф – совокупность 2х конечных множеств: вершин и ребер (или дуг).

Не ориентированный граф Ориентированный граф

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

Путь в ориентируемом графе – последовательность сцепленных ориентированных дуг, в которых начало каждой следующей дуги совпадает с концом предыдущей.

В неориентированном графе цикл называют контуром.

Граф может быть задан в матричном виде

Вершины предки (предшествующие)

В графике не должно быть

А) тупиковых событий (не выходит ни 1 стрелки, за исключением последнего события);

Б) хвостовых событий (не предшествует ни одна вершина, за исключением первого события);

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

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

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

1. Начальный шаг алгоритма.

Выделенной вершине присваивается метка и поставим рядом *, то есть и назовём такую метку Конечной, а вершину – Помеченной.

2. Общий шаг (повторяется многократно).

Рассмотрим все дуги, выходящие из отмеченной (помеченной) вершины. На первом шаге отмеченная вершина это вершина . Вычислим метки для вершин, в которые ведут дуги из : — это сумма метки и длины дуги, ведущей из в вершину . Из всех меток, которые получит вершина , выбираем наименьшую, отмечаем её * и считаем конечной. Повторяем общий шаг для определения конечных меток для всех вершин.

Рассмотрим работу Форда на примере.

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

Из вершины выходят 2 дуги, ведущие в вершины и с длинами , .

Из ведут 3 дуги в , и и т. д.

Начальный шаг (применяется однократно).

Вершине присваивается метка . Вершину считаем помеченной.

1) Вершина имеет конечную метку. Из неё выходят 2 дуги в и . Вычисляем две метки и и записываем их рядом с вершинами и . Соответственно других дуг, ведущих в и нет, поэтому эти метки конечные, отмечаем их * и изобразим две конечные (окончательные) метки на рис. 1.

2) Вершина имеет конечную метку. Из неё выходят 3 дуги, ведущие в , , и .

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

Изобразим вычисленные три метки для , , и на рис. 2. Вершина имеет конечную метку. Из неё выходят 3 стрелки в , , и . Вычисляем метки: для вершины , для вершины и для вершины .

В вершину не входят другие дуги. Из двух меток вершины выбираем наименьшую, это метка , она окончательная. Изобразим метки вершин , , и на рис.2, причем окончательные метки вершин и отмечаем *.

3) Вершина имеет конечную метку, из неё выходит единственная дуга в . Для получаем метку , т. е. , она не окончательная.

Из вершины в вершину идёт дуга, . Вычислим метку .

Вершина имеет окончательную метку.

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

4) Вершина имеет конечную метку, из неё ведут две дуги, вычисляем соответствующие метки в и в . Для вершин уже вычислены две метки. Из трех вычисленных меток , , выбираем меньшую и отмечаем её *.

Далее повторяем общий шаг пока не рассмотрим все оставшиеся вершины. При этом вершина получит окончательную метку *, вершина — *.

Двигаясь из в по помеченным меткам, получим кратчайший путь из вершины в вершину

Кратчайший путь из в равен 15, .

Также можно найти кратчайшие пути из в любую вершину , они равны окончательной метке вершины

Кратчайший путь в ациклическом графе

Задача:
Пусть дан ациклический ориентированный взвешенный граф. Требуется найти вес кратчайшего пути из [math]u[/math] в [math]v[/math] .


Содержание

Решение [ править ]

Воспользуемся принципом оптимальности на префиксе.
Пусть [math]d[/math] — функция, где [math]d(i)[/math] — вес кратчайшего пути из [math]u[/math] в [math]i[/math] . Ясно, что [math]d(u)[/math] равен [math]0[/math] . Пусть [math]w(i, j)[/math] — вес ребра из [math]i[/math] в [math]j[/math] . Будем обходить граф в порядке топологической сортировки. Получаем следующие соотношения:

Так как мы обходим граф в порядке топологической сортировки, то на [math]i[/math] -ом шаге всем [math]d(j)[/math] ( [math]j[/math] такие, что существует ребро из [math]j[/math] в [math]i[/math] ) уже присвоены оптимальные ответы, и, следовательно, [math]d(i)[/math] также будет присвоен оптимальный ответ.

Реализация [ править ]

Реализуем данный алгоритм:

Пример [ править ]

Пусть дана матрица смежности графа [math]w[/math] со следующими весами ребер:

1 2 3 4 5 6 7 8
1 2
2 1 1 4 3
3 1
4
5 3 1
6 5 2
7 2
8 1

Требуется найти вес кратчайшего пути из 2 в 4.
Массив [math]p[/math] будет выглядеть следующим образом:

[math]i[/math] 1 2 3 4 5 6 7 8
[math]p[i][/math] 2 3 6 7 1 5 8 4

Массив [math]d[/math] будет выглядеть следующим образом:

[math]i[/math] 1 2 3 4 5 6 7 8
[math]d[i][/math] 1 1 5 3 2 4 4

Ответ равен [math]5[/math] .

Альтернативный способ решения [ править ]

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

Илон Маск рекомендует:  Что такое код yp_first

Графы: разные виды представления графов. Алгоритмы Дейкстры и Флойда: реализация на Python. Минимальное остовное дерево

Раскрашивание графов

Обход вершин графа

Поиск в глубину — ПВГ (Depth First Search — DFS)

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

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

Порядок обхода вершин при поиске в ширину

Поиск кратчайших путей в графах (объединение разделов по Дейкстре и Флойду)

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

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

Примеры формулировки задачи

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

Вариант 2. Имеется некоторое количество авиарейсов между городами мира, для каждого известна стоимость. Стоимость перелёта из A в B может быть не равна стоимости перелёта из B в A. Найти маршрут минимальной стоимости (возможно, с пересадками) от Копенгагена до Барнаула.

Идея алгоритма Дейкстры

Алгоритм состоит и 2 повторяющихся шагов:

  • Добавление новой вершины («Расти» — GROW)
  • «Релаксация», т.е. пересчёт расстояний до других вершин с учётом добавленной вершины (RELAX).

Более подробное описание:

Обозначения:

Граф $G = (V,E)$, где $V$ — вершины, $E$ — рёбра.

$v_0$ — начальная вершина (от которой мы ищем кратчайшее растояние до всех остальных)

$R_i$ — известное нам расстояние от вершиеы $v_0$ до вершины $i$-ой.

$D$ — множество вершин до которых мы знаем кратчайшее расстояние от $v_0$.

Граф $G=(V,E)$, где $V$ — вершины, $E$ — рёбра.

$v_0$ — начальная вершина

$R_i$ — кратчайщее расстояние от $v_0$ до $i$-ой вершины

Инициализация алгоритма:

$D = \<\>$ — пустое множество.

$R_ = 0$ — расстояние от $v_0$ до $v_0$ = 0.

$v = v_0$ — расти будем от вершины $v$.

Повторять (общий шаг алгоритма)

$GROW(V/D,v)$ — Добавляем вершину $v$ из множества $V/D$ в множество $D$.

$RELAX(V/D,v)$ — пробегаем достижимые из $v$ вершины до которых мы ещё не знаем кратчайшее расстояние и обновляем расстояния $R_i$ от вершины $v$.

$v$ — вершина с минимальным $R$ из множества $V/D$.

Алгоритм


Каждой вершине $v$ из $V$ сопоставим значение $a[v]$ — минимальное известное расстояние от этой вершины до начальной $s$. Алгоритм работает пошагово — на каждом шаге он рассматривает одну вершину и пытается улучшить текущее расстояние до этой вершины. Работа алгоритма завершается, когда все вершины посещены, либо когда вычислены расстояния до всех вершин, достижимых из начальной.

Инициализация. Значение $a[s]$ самой начальной вершины полагается равным 0, значение остальных вершин — бесконечности (в программировании это реализуется присваиванием большого, к примеру, максимально возможного для данного типа, значения). Это отражает то, что расстояния от $s$ до других вершин пока неизвестны.

Шаг алгоритма. Если все вершины посещены, алгоритм завершается. В противном случае, из ещё не посещённых вершин выбирается вершина v, имеющая минимальное расстояние от начальной вершины $s$ и добавляется в список посещенных. Эта вершина находится, используя перебор всех непосещенных вершин. При этом суммируется расстояние от старта до одной из посещенных вершин u до непосещенной $v$. Для первого шага $s$ — единственная посещенная вершина с расстоянием от старта (то есть от себя самой), равным 0.

Алгоритм Флойда

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

Пусть вершины графа пронумерованы от 1 до $n$ и введено обозначение $d_^k$ для длины кратчайшего пути от $i$ до $j$, который кроме самих вершин $i,\; j$ проходит только через вершины $1 \ldots k$. Очевидно, что $d_^<0>$ — длина (вес) ребра $(i,\;j)$, если таковое существует (в противном случае его длина может быть обозначена как $\infty$)

Существует два варианта значения $d_^,\;k \in \mathbb (1,\;\ldots,\;n)$:

  1. Кратчайший путь между $i,\;j$ не проходит через вершину $k$, тогда $d_^=d_^$
  2. Существует более короткий путь между $i,\;j$, проходящий через $k$, тогда он сначала идёт от $i$ до $k$, а потом от $k$ до $j$. В этом случае, очевидно, $d_^=d_^ + d_^$

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

Тогда рекуррентная формула для $d_^k$ имеет вид:

$d_^0$ — длина ребра $(i,\;j)$

Алгоритм Флойда — Уоршелла последовательно вычисляет все значения $d_^$, $\forall i,\; j$ для $k$ от 1 до $n$. Полученные значения $d_^$ являются длинами кратчайших путей между вершинами $i,\; j$.

Алгоритм Прима

Алгоритм Прима — алгоритм построения минимального остовного дерева взвешенного связного неориентированного графа. Алгоритм впервые был открыт в 1930 году чешским математиком Войцехом Ярником, позже переоткрыт Робертом Примом в 1957 году, и, независимо от них, Э. Дейкстрой в 1959 году.

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

Вход: Связный неориентированный граф $G(V,E)$

Выход: Множество $T$ рёбер минимального остовного дерева

Обозначения:

  • $d_i$ — расстояние от $i$-й вершины до построенной части дерева
  • $p_i$ — предок $i$-й вершины, то есть такая вершина $u$, что $(i,u)$ самое короткое рёбро соединяющее $i$ с вершиной из построенного дерева.
  • $w(i,j)$ — вес ребра $(i,j)$
  • $Q$ — приоритетная очередь вершин графа, где ключ — $d_i$
  • $T$ — множество ребер минимального остовного дерева

Псевдокод:

Для каждой вершины $i \in V$: $d_i \gets \infty$, $p_i \gets nil$

НАХОЖДЕНИЕ КРАТЧАЙШИХ ПУТЕЙ В ГРАФЕ

Рассматрим ориентированные графы G(X, E) каждой дуге eE которого ставится в соответствие вещественное число l(e). Т.е. на множестве Е создана функция l:ER. Такой граф принято называть нагруженным. Само число l называется весом дуги.

Можно увидеть аналогию между, например, картой автомобильных или железных дорог. Тогда множество вершин Х будет соответствовать городам, множество дуг — магистралям, соединяющим города, а веса — расстояниям. (На практике, при этом, фактически получится неориентированный граф).

В связи с изложенной аналогией будем называть веса дуг расстояниями.

Определение 2.1. Пусть имеется последовательность вершин x, x1, …, xn, которая определяет путь в нагруженном графе G(X, E), тогда длина этого пути определяется как .

Естественный интерес представляет нахождение кратчайшего пути между двумя заданными вершинами x и y.

Алгоритм Форда отыскания кратчайшего пути.

Будем предполагать, что все расстояния в графе положительны. (Если это не так, то ко всем весам можно всегда добавить такую константу, что все эти веса станут положительными).

Пусть мы ищем путь от вершины x к вершине xn. Будем каждой вершине xi ставить в соответствие некоторое число i по следующим правилам.

1 Положим = 0, i = (достаточно большое число) для i > 0.

2 Ищем в графе дугу (xi, xj) удовлетворяющую следующему условию

после чего заменяем j на

Пункт 2 повторяется до тех пор, пока невозможно будет найти дугу, удовлетворяющую условию (1). Обоснуем этот алгоритм и укажем как определяется кратчайший путь.

Отметим, что n монотонно уменьшается, то после завершения алгоритма найдется дуга , такая, что для которой последний раз уменьшалось n. (Иначе вообще нет пути между x и xn или для верно (1)).

По этой же самой причине найдется вершина , такая , что

этот процесс может продолжаться и дальше, так что получится строго убыва-ю-щая последовательность . Отсюда следует, что при некото-ром k мы получим .

Покажем, что — минимальный путь с длиной n, т.е. длина любого другого пути между x и xn не превышает kn.

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

После завершения алгоритма имеем следующие соотношения

Сложив все эти неравенства, получим

что и требовалось доказать.

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

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

Алгоритм Флойда

Обозначим lij длину дуги (xi, xj), если таковой не существует примем lij = , кроме того, положим lii = 0. Обозначим длину кратчайшего из путей из xi в xj с промежуточными вершинами из множества x1, …, xm. Тогда можно получить следующие уравнения

Уравнение (2) очевидно. Обоснуем уравнение (3). Рассмотрим кратчай-ший путь из xi в xj с промежуточными вершинами из множества x1, …, xm, xm+1. Если этот путь не содержит xm+1, то . Если же он содержит xm+1, то деля путь на отрезки от xi до xm+1 и от xm+1 до xj, получаем равенство .

Уравнения (2) и (3) позволяют легко вычислить матрицу расстояний dij между всеми парами вершин графа G(X, E). На первом этапе согласно (2) составляем nn матрицу равную матрице lij весов ребер (n — число вершин G(X, E)). n раз производим вычисление по итерационной формуле (3), после чего имеем — матрицу расстояний.

Отметим, что алгоритм Флойда непосредственно не указывает сам кратчайший путь между вершинами, а только его длину. Алгоритм Флойда можно модифицировать таким образом, чтобы можно было находить и сами пути. Для этого получим вспомогательную матрицу Rij, которая будет содержать наибольший номер вершины некоторого кратчайшего пути из xi в xj (Rij=0, если этот путь не содержит промежуточных вершин).

Эта матрица вычисляется параллельно с по следующим правилам


Последнее выражение следует из обоснования (3).

Теперь кратчайший путь выписывается из следующего рекурсивного алгоритма:

1. Если Rij = 0 то выполнить 2,

иначе выполнить 3.

2. Если i=j то выписать xi и закончить,

3. Выписать кратчайший путь между xi и .

4. Выписать кратчайший путь между и xj.

Пункты 3 и 4 предполагают рекурсивное обращение к рассмотренному алгоритму.

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

Напомним, что бинарным отношением на множестве Х называется произвольное подмножество E X X.

Транзитивным называется отношение, удовлетворяющее следующему условию: если (x, y) E и (y, z) E, то (x, z) E для всех x, y, z X. Отметим, что бинарное отношение можно однозначно представить орграфом G(X, E). Теперь для произвольного отношения Е определим новое отношение Е* следующим образом

E* = <(x, y) | если в G(X, E) существует путь ненулевой длины из x в y>.

Легко проверить, что Е* — транзитивное отношение. Кроме того, Е* является наименьшим транзитивным отношением на Х в том смысле, что для произвольного транзитивного отношения F E выполняется E* F. Отно-ше-ние Е* называется транзитивным замыканием отношения Е.

Если отношение Е представить в виде графа G(X, E) в котором каждая дуга имеет вес 1, то транзитивное замыкание Е* можно вычислить с помощью алгоритма Флойда. При этом надо учесть, что

Для большего удобства алгоритм Флойда в этом случае можно моди-фи-ци-ровать следующим образом.

Вместо (3) запишем

где — дизъюнкция (логическое сложение),

— конъюнкция (логическое умножение).

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

Модифицированный таким образом алгоритм называется алгоритмом Уоршелла.

8.Нахождение кратчайших путей в графе

В этом параграфе рассматриваются ориентированные графы G(X,E) каждой дугеeEкоторого ставится в соответствие вещественное числоl(e). Т.е. на множествеЕсоздана функцияl:ER. Такой граф принято называтьнагруженным. Само числоlназываетсявесомдуги.

Можно увидеть аналогию между, например, картой автомобильных или железных дорог. Тогда множество вершин Хбудет соответствовать городам, множество дуг – магистралям, соединяющим города, а веса – расстояниям. (На практике, при этом, фактически получится неориентированный граф).

В связи с изложенной аналогией будем называть веса дуг расстояниями.

Определение 8.1. Пусть имеется последовательность вершинx,x1, …,xn, которая определяет путь в нагруженном графеG(X,E), тогдадлинаэтого пути определяется как .

Естественный интерес представляет нахождение кратчайшегопути между двумя заданными вершинамиxиy.

Алгоритм Форда отыскания кратчайшего пути.

Будем предполагать, что все расстояния в графе положительны. (Если это не так, то ко всем весам можно всегда добавить такую константу, что все эти веса станут положительными).

Пусть мы ищем путь от вершины xк вершинеxn. Будем каждой вершинеxiставить в соответствие некоторое числоiпо следующим правилам.

2Ищем в графе дугу (xi,xj) удовлетворяющую следующему условию

после чего заменяем jна

Пункт 2 повторяется до тех пор, пока невозможно будет найти дугу, удовлетворяющую условию (1). Обоснуем этот алгоритм и укажем как определяется кратчайший путь.

Отметим, что nмонотонно уменьшается, то после завершения алгоритма найдется дуга , такая, что для которой последний раз уменьшалосьn. (Иначе вообще нет пути междуxиxnили для верно (1)).

По этой же самой причине найдется вершина , такая , что

этот процесс может продолжаться и дальше, так что получится строго убыва­ю­щая последовательность . Отсюда следует, что при некото­ромkмы получим .

Покажем, что – минимальный путь с длинойn, т.е. длина любого другого пути междуxиxnне превышаетkn.

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

После завершения алгоритма имеем следующие соотношения

Сложив все эти неравенства, получим

что и требовалось доказать.

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

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

Алгоритм Флойда

Обозначим lijдлину дуги (xi,xj), если таковой не существует примемlij=, кроме того, положимlii= 0. Обозначим длину кратчайшего из путей изxiвxjс промежуточными вершинами из множестваx1, …,xm. Тогда можно получить следующие уравнения

Уравнения (2) и (3) позволяют легко вычислить матрицу расстояний dijмежду всеми парами вершин графаG(X,E). На первом этапе согласно (2) составляемnnматрицу равную матрицеlijвесов ребер (n– число вершинG(X,E)).nраз производим вычисление по итерационной формуле (3), после чего имеем – матрицу расстояний.

Отметим, что алгоритм Флойда непосредственно не указывает сам кратчайший путь между вершинами, а только его длину. Алгоритм Флойда можно модифицировать таким образом, чтобы можно было находить и сами пути. Для этого получим вспомогательную матрицу Rij, которая будет содержать наибольший номер вершины некоторого кратчайшего пути из xiв xj(Rij=0, если этот путь не содержит промежуточных вершин).

Эта матрица вычисляется параллельно с по следующим правилам

Последнее выражение следует из обоснования (3).

Теперь кратчайший путь выписывается из следующего рекурсивного алгоритма:

иначе выполнить 3.

3. Выписать кратчайший путь междуxiи .

4. Выписать кратчайший путь между иxj.


Пункты 3и 4предполагают рекурсивное обращение к рассмотренному алгоритму.

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

Напомним, что бинарным отношением на множестве Хназывается произвольное подмножествоEXX.

Транзитивным называется отношение, удовлетворяющее следующему условию: если (x,y)Eи (y, z)E, то (x, z)Eдля всехx,y,zX. Отметим, что бинарное отношение можно однозначно представить орграфомG(X,E). Теперь для произвольного отношенияЕопределим новое отношениеЕ* следующим образом

Легко проверить, что Е* — транзитивное отношение. Кроме того,Е* является наименьшим транзитивным отношением наХв том смысле, что для произвольного транзитивного отношенияFEвыполняетсяE*F. Отно­ше­ниеЕ* называетсятранзитивным замыканиемотношенияЕ.

Если отношение Епредставить в виде графаG(X,E) в котором каждая дуга имеет вес 1, то транзитивное замыканиеЕ* можно вычислить с помощью алгоритма Флойда. При этом надо учесть, что

Для большего удобства алгоритм Флойда в этом случае можно моди­фи­ци­ровать следующим образом.

Вместо (3) запишем

где – дизъюнкция (логическое сложение),

 – конъюнкция (логическое умножение).

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

Модифицированный таким образом алгоритм называется алгоритмом Уоршелла.

Поиск кратчайшего пути в графе

18.12.2011, 01:26

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

Поиск кратчайшего пути на графе
Выдает ошибку Error 1 error C4996: ‘itoa’: The POSIX name for this item is deprecated. Instead, use.

Восстановление кратчайшего пути в графе
Есть алгоритм нахождения кратчайших путей(Флойд), а как восстановить путь как узнать через какие.

Нахождение кратчайшего пути в графе, алгоритм Уоршелла
Привет всем! алгоритм уоршелла, нужно найти кратчайший путь в графе. ввожу матрицу 0 1 5 1 0 2.

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

18.12.2011, 11:06 [ТС] 2

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

Добавлено через 9 часов 40 минут
Ну помогите а?

18.12.2011, 11:15 3

Флойд, Дейкстра или Форд-Беллман. Надо только матрицу смежности построить.

Добавлено через 57 секунд

Добавлено через 2 минуты
А графику уже достроите

18.12.2011, 20:42 [ТС] 4

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

Добавлено через 55 минут
Готов заплатить через Яндекс деньги! Только помогите, завтра сдать надо эту штуку. Еще бы блоксхему бы.

Добавлено через 28 минут
неужели никто не возьмется? 300-450 рублей заплачу за задачу и блоксхему.

Добавлено через 1 час 7 минут
ну возмитесь кто нибудь, завтра сдавать нужно, а я вообще в непонятках как делать

18.12.2011, 20:42
18.12.2011, 20:51 5
18.12.2011, 20:53 [ТС] 6
18.12.2011, 20:58 7
18.12.2011, 21:18 [ТС] 8

Ну как сделать то мое задание знает кто нибудь? Плачу 400 р. (прога и блоксхема)

Добавлено через 18 минут
А все, не надо, кажется я все сделал)))

18.12.2011, 21:41 9

Флойд N^3
Дейкстра N^2
Дейкстра с кучей N*logN

Добавлено через 40 секунд
Иначе не было бы смысла в Дейкстре писать 20 строк, чем во Флойде 3

18.12.2011, 21:44 [ТС] 10

Народ, подойдет код для моего задания:

18.12.2011, 21:46 11
18.12.2011, 21:50 [ТС] 12
18.12.2011, 21:50 13
19.12.2011, 02:02 [ТС] 14

А как будет выглядить матрица смежности для графа?

Добавлено через 3 часа 46 минут
Можете мне написать матрицу смежности для моего графа, пожалуйста.
Я так понял что она будет 9×9 и ставится 1 если из одной точки можно попасть в другую, а если нельзя то 0.

19.12.2011, 08:25 15
вроде так:
0 1 0 0 0 0 0 0 0
1 0 1 0 0 1 0 0 0
0 1 0 1 1 0 0 0 0
0 0 1 0 0 1 1 0 1
0 0 1 0 0 1 1 1 0
0 1 0 1 1 0 0 0 0
0 0 0 1 1 0 0 1 1
0 0 0 0 1 0 1 0 1
0 0 0 1 0 0 1 1 0
21.12.2011, 16:57 [ТС] 16

Народ, может вопрос не совсем по теме. Меня интересует как работает алгоритм Дейкстра на этом примере, я просто защищаю лабу уже второй раз подряд, заваливаюсь на одном и том же.
Вот как я ему объясняю: все расстояния между вершинами в начале равны бесконечности, начинаем из вершины м1, так как ей ничего не предшествует, кратчайший путь из м1 в м1 равен 0, потом идем дальше к вершине м2, записываем для нее расстояние от м1, допустим 1, и запоминаем для нее кратчайший путь. Далее из вершины м2 мы можем попасть в м3 или м6, идем в м3, так как логичнее сначала туда пойти, запоминаем расстояние и путь для нее, дальше у нас выбор между м5 и м4, идем в м4, запоминаем расстояние и путь для нее. а вот дальше все что бы я не говорил, он не воспринимал, и говорил, что все неправильно. Можете подсказать каким образом проходит алгоритм Дейкстра в этом графе и как мне все это преподу рассказать по шагам. Заранее спасибо)

Добавлено через 15 часов 0 минут
Ответьте, кто-нибудь..

12.04.2013, 14:21 17
12.04.2013, 14:21
12.04.2013, 14:21

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

Поиск кратчайшего пути
Как сделать что бы задача не считала стоимость проезда в обратную сторону ? #include .

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

2.2 Нахождение кратчайших путей в графе

Будем рассматривать ориентированные графы G = , дугам которых приписаны веса. Это означает, что каждой дуге ОE поставлено в соответствие некоторое вещественное число a (u, v), называемое весом данной дуги.

Нас будет интересовать нахождение кратчайшего пути между фиксированными вершинами s, t ОV. Длину такого кратчайшего пути мы будем обозначать d (s, t) и называть расстоянием от s до t (расстояние, определенное таким образом, может быть отрицательным). Если не существует ни одного пути из s в t, то полагаем d (s, t) = г . Если каждый контур нашего графа имеет положительную длину, то кратчайший путь будет всегда элементарным путем, т.е. в последовательности v1. vp не будет повторов.

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

Можно дать много практических интерпретаций задачи о кратчайших путях. Например, вершины могут соответствовать городам, а каждая дуга — некоторому пути, длина которого представлена весом дуги. Мы ищем затем кратчайшие пути между городами. Вес дуги также может соответствовать стоимости (или времени) передачи информации между вершинами. В таком случае мы ищем самый дешевый (или самый скорый) путь передачи информации. Еще одну ситуацию получаем, когда вес дуги ?u, v? равен вероятности p(u, v) безаварийной работы канала передачи информации. Если предположить, что аварии каналов не зависят друг от друга, то вероятность исправности пути передачи информации равна произведению вероятностей составляющих его дуг. Задачу нахождения наиболее надежного пути легко можно свести к задаче о кратчайшем пути, заменяя веса p(u, v) на

Сначала рассмотрим алгоритмы нахождения расстояния между вершинами, а не самих путей. Однако, зная расстояние, мы можем при условии положительной длины всех контуров легко определить кратчайшие пути. Для этого достаточно отметить, что для произвольных s, t О V (s, t) существует вершина v, такая что

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

Далее мы можем найти вершину u, для которой

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

Очевидно, что она определяет (при обращении очередности) кратчайший путь из s в t.

Таким образом, мы получаем следующий алгоритм:

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

Данные: Расстояния D[v] от фиксированной вершины s до всех остальных вершин v О V, фиксированная вершина t, матрица весов ребер, A[u, v], u, v ОV.

Результаты: СТЕК содержит последовательность вершин, определяющую кратчайший путь из s в t.

Пусть -ориентированный граф, | V| = n, | E| = m. Если выбор вершины u происходит в результате просмотра всех вершин, то сложность нашего алгоритма — O(n 2 ). Если мы просматриваем только список ПРЕДШ[v], содержащий все вершины u, такие что u (r) v, то в этом случае сложность будет O(m).

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

Далее будем всегда предполагать, что G = является ориентированным графом, |V| = n, |E| = m. В целях упрощения изложения и избежания вырожденных случаев при оценке сложности алгоритмов будем исключать ситуации, при которых «большинство» вершин изолированные.

Будем также предполагать, что веса дуг запоминаются в массиве A[u, v], u, v О V (A[u, v] содержит вес a (u, v)).

Кратчайшие пути от фиксированной вершины

Большинство известных алгоритмов нахождения расстояния между двумя фиксированными вершинами s и t опирается на действия, которые в общих чертах можно представить следующим образом: при данной матрице весов дуг A[u, v], u, v—О V, вычисляются некоторые верхние ограничения D[v] на расстояния от s до всех вершин v ОV. Каждый раз, когда мы устанавливаем, что

Алгоритмы поиска пути в графе

Для новичков Граф — это (упрощенно) множество точек, называемых вершинами, соединенных какими-то линиями, называемыми рёбрами (необязательно все вершины соединены). Можно представлять себе как города, соединенные дорогами.

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

Наглядное представление о работе перечисленных далее алгоритмов можно получить благодаря визуализатору PathFinding.js.

Алгоритм был разработан независимо Муром и Ли для разных приложений (поиск пути в лабиринте и разводка проводников соответственно) в 1959 и 1961 годах. Этот алгоритм можно сравнить с поджиганием соседних вершин графа: сначала мы зажигаем одну вершину (ту, из которой начинаем путь), а затем огонь за один элементарный промежуток времени перекидывается на все соседние с ней не горящие вершины. В последствие то же происходит со всеми подожженными вершинами. Таким образом, огонь распространяется “в ширину”. В результате его работы будет найден кратчайший путь до нужной клетки.

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

Этот алгоритм назван по имени создателя и был разработан в 1959 году. В процессе выполнения алгоритм проверит каждую из вершин графа, и найдет кратчайший путь до исходной вершины. Стандартная реализация работает на взвешенном графе — графе, у которого каждый путь имеет вес, т.е. “стоимость”, которую надо будет “заплатить”, чтобы перейти по этому ребру. При этом в стандартной реализации веса неотрицательны. На клетчатом поле вес каждого ребра графа принимается одинаковым (например, единицей).

А* (А “со звездочкой”)

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

Поиск по первому наилучшему совпадению (Best-First Search)

Усовершенствованная версия алгоритма поиска в ширину, отличающаяся от оригинала тем, что в первую очередь развертываются узлы, путь из которых до конечной вершины предположительно короче. Т.е. за счет эвристики делает для BFS то же, что A* делает для алгоритма Дейкстры.

IDA* (A* с итеративным углублением)

Расшифровывается как Iterative Deeping A*. Является измененной версией A*, использующей меньше памяти за счет меньшего количества развертываемых узлов. Работает быстрее A* в случае удачного выбора эвристики. Результат работы — кратчайший путь.

Самый молодой из перечисленных алгоритмов был представлен в 2011 году. Представляет собой усовершенствованный A*. JPS ускоряет поиск пути, “перепрыгивая” многие места, которые должны быть просмотрены. В отличие от подобных алгоритмов JPS не требует предварительной обработки и дополнительных затрат памяти.

Материалы по более интересным алгоритмам мы обозревали в подборке материалов по продвинутым алгоритмам и структурам данных.

Нахождение кpатчайших пyтей в гpафе

Есть неоpиентиpованный гpаф. Состоит из веpшин и pебеp, pебpам пpиписаны длины. Веpшин несколько тысяч (N штук), количество pебеp известно (M штук). Дополнительных сведений о соотношении числа pебеp и числа веpшин нет.

Hадо найти несколько кpатчайших путей без циклов между двумя заданными точками (K штук путей, K задается, K поpядка нескольких десятков)


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

Позволяет находить k-кратчайшие пути без циклов последовательно.

Этот алгоритм предполагает, что мы умеем находить один кратчайший путь в графе.

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

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

Илон Маск рекомендует:  Что такое код pg_free_result
Понравилась статья? Поделиться с друзьями:
Кодинг, CSS и SQL