![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Алгоритм БеллманаСтр 1 из 3Следующая ⇒
Алгоритм Беллмана решения задачи о кратчайшем пути. Алгоритм Флойда отыскания кратчайших путей между всеми парами вершин графа Алгоритм Беллмана Алгоритм определяет длины кратчайших путей от фиксированной вершины s до всех остальных вершин графа. Он корректно работает с дугами отрицательной длины и, в случае присутствия в графе контура отрицательной длины, обнаруживает его и сообщает о невозможности построения кратчайших путей. Заметим, что всякий кратчайший путь – это простая цепь, поэтому в любом кратчайшем пути в графе G с множеством вершин { s, v 1, v 2, … vn } не более n дуг. Обозначим через Тогда
Здесь Зная числа Чтобы определить, есть ли в графе G контур отрицательной длины, нужно рассчитать числа Алгоритм может окончить работу быстрее, чем за n шагов. Не обязательно, чтобы в графе существовали кратчайшие пути, содержащие n дуг. Если все числа Пример 1. Определим кратчайшие пути от вершины 1 до всех остальных вершин графа, изображенного на рис. 1. В графе есть дуги отрицательной длины, поэтому применим алгоритмом Беллмана.
На первом шаге находятся пути из одной дуги до вершин 2, 4, 5. Значит, пути, состоящие не более чем из двух дуг, следует искать только до вершин, в которые входят дуги выходящие из вершин 2, 4, 5 (рис. 2). Над кружками с номерами вершин на рис. 2 стоят длины путей до этих вершин, найденные на предыдущем шаге.
Заполним вторую строку табл. 1. Таблица 1
Уменьшились длины путей до вершин 2, 3, 6, 7, 8, 9. Значит, имеет смысл искать более короткие пути до тех вершин графа, в которые входят дуги из перечисленных вершин (рис. 3).
Заполняем третью строку табл. 1. На третьем шаге уменьшились длины путей до вершин 3, 5, 6, 8, 9. Постараемся найти более короткие пути до
тех вершин графа, в которые входят дуги, выходящие из перечисленных вершин (рис. 4).
Заполняем четвертую строку таблицы. Уменьшились длины путей до вершин 3, 5, 8, 9. Продолжаем действовать по алгоритму Беллмана (рис. 5).
Заполняем пятую строку таблицы. Уменьшились длины путей до вершин 3, 5, 9. Следовательно, нужно пересчитать длины путей до вершин 2, 3, 4, 5, 6, 7, 9.
Заполняем шестую строку таблицы. Уменьшилась длина пути до вершины 3. Нужно пересчитать длины путей до вершин 2, 5, 6.
Заполняем седьмую строку таблицы. Длины седьмой строки повторяют длины шестой строки. Кратчайшие пути найдены и среди них есть пути, состоящие из шести дуг. Построим дерево кратчайших путей (рис. 6). Длина кратчайшего пути до вершины 4 была найдена уже в первой строке. Значит, этот путь состоит из одной дуги. Включаем в дерево дугу (1, 4). Во второй строке стоят длины кратчайших путей до вершин 2 и 7. Следовательно, эти пути включают в себя две дуги. Из расчетов (и диаграммы) вытекает, что предпоследняя вершина кратчайшего пути как до вершины 2, так и до вершины 7 – это вершина 4. В дерево кратчайших путей добавляем дуги (4, 2) и (4, 7).
Пример 2. Покажем, как алгоритм Беллмана обнаруживает контур отрицательной длины.
Для этого достаточно обойти контур 2-3-4-2 нужное число раз. Без дальнейших пояснений приведем таблицу алгоритма Беллмана (табл. 2).
В четвертой строке табл. 2 уменьшилась длина пути до второй вершины. Путь из четырех дуг 1-2-3-4-2 оказался короче пути из одной дуги (1, 2). Алгоритм обнаружил в графе контур отрицательной длины.
,
|