Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

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

Читайте также:
  1. Address Where You Will Stay in the U.S. – вы указываете данные своего работодателя. Данные о работодателе должны СОВПАДАТЬ С ДАННЫМИ В ГРАФЕ “CONFIRMED EMPLOYER”!!!
  2. Marilyn Manson: Ну, это – ссылка на фильм, «Chitty Chitty Bang Bang» (прим. На русский перевели как «Пиф-паф ой-ой-ой», как мне говорит кинопоиск), ты его смотрел?
  3. Автоматический поиск несоответствия в словах собеседника
  4. Алгоритм поиска подстроки Кнута-Морриса-Пратта (на основе префикс-функции)
  5. Алгоритм поиска подстроки, основанный на конечных автоматах
  6. Базы данных, информационно-справочные и поисковые системы
  7. В которой Организуется Поиск, а Пятачок чуть не встречается снова со Слонопотамом

Пусть дан некоторый конечный граф G=(V,E), состоящий из N вершин, и две его вершины a, bÎV. Пусть для каждого ребра графа e задано положительное вещественное число l(e), которое будем называть длиной ребра. Требуется найти путь между вершинами графа a и b минимальной длины, т.е. требуется найти последовательность {x1,…,xn}, где xiÎV, x1=a, xn=b, (xi, xi+1)ÎE с минимально возможной S l(xi,xi+1).

Стандартным решением данной задачи является алгоритм Дейкстры.

Основная идея алгоритма заключается в следующем.

Пусть множество Qn представляет собой множество n ближайших вершин к вершине a вместе с длинами пути от a до этих вершин. Т.е. в каждом элементе множества qiÎQn содержится номер соответствующей вершины xi и длина пути от a до этой вершины li: qi=(xi,li). Можно предполагать, что последовательность {li} является неубывающей.

Утверждается, что ближайшая вершина графа к a из вершин, не внесенных в Qn, задается следующим соотношением:

argmin(v,wÎV, wÎ Qn, vÏ Qn, (w, v) ÎE: lw+|(w,v)|) (*)

здесь и далее под wÎ Qn, vÏ Qn имеется в виду, что w встречается среди вершин, внесенных в Qn, а v – нет; длина ребра (w, v) обозначается |(w,v)|. Т.о. элемент qn+1 складывается из вершины v, на которой достигается указанный минимум и соответствующей длины ln+1 = lw+|(w,v)|.

Доказательство. Допустим, найдена вершина sÏ Qn с минимальной длиной до a. Пусть кратчайший путь от a до s проходит по последовательности вершин графа {a,x2,…,xn,s}. Длина пути {a,x2,…,xn} меньше длины пути до s, поэтому xnÎ Qn, но тогда длина пути {a,x2,…,xn,s} должна совпадать с длиной кратчайшего пути от a до найденного выше w.

¢

 

При поиске значения (*), формально, требуется перебрать все вершины wÎ Qn и для каждой из них требуется перебрать все смежные вершины. Будем далее предполагать, что в графе отсутствуют кратные ребра и петли, тогда процедура (*) требует выполнения O(N2) операций, из чего следует, что суммарное время работы алгоритма есть O(N3).

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

Для реализации алгоритма Дейкстры следует добавить в каждую вершину w графа вещественное число lw, характеризующее длину кратчайшего пути от вершины a до вершины w и логическую переменную sw, указывающую – посчитана ли на данный момент эта кратчайшая длина пути.

Для упрощения дальнейшей жизни (т.е. для поиска, собственно, кратчайшего пути при определенных значения lw) можно в каждом элементе также хранить ссылку на вершину, из которой мы в данную вершину пришли. Для текущей вершины w будем эту ссылку называть backw. Т.о. элементы Qi представляются в виде q=(w, lw, sw, backw).

Будем предполагать, что конкретная техника нам позволяет инициализировать все lw значением = плюс бесконечность (+INF), что мы и сделаем. Инициализируем все sw значением = FALSE.

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


Дата добавления: 2015-10-30; просмотров: 102 | Нарушение авторских прав


Читайте в этой же книге: SortB (A, N, M, B) | То return QFindStatP (A, p, j, k,N ) | QFindStat5(A,1,N,k) | Структуры данных. | Struct SStack3 st3; | Стек. Реализация 5 (на основе указателя на указатель). | Struct SQueue | Стандартная ссылочная реализация списков | InsertData( value, head, current); | Реализация L2-списка на основе двух стеков |
<== предыдущая страница | следующая страница ==>
Поиск пути в графе с наименьшим количеством промежуточных вершин| Добавление элемента

mybiblioteka.su - 2015-2024 год. (0.006 сек.)