- •Основы теории графов
- •Введение
- •Глава 1. Способы задания графов. Операции над графами. Метрические характеристики графов. Упорядочивание элементов орграфов
- •1. Способы задания графов. Операции над графами. Метрические характеристики графов
- •Основные понятия и определения
- •1.2. Операции над графами
- •1.3. Маршруты, цепи, циклы
- •. Способы задания графов
- •1.5. Метрические характеристики графа.
- •1.6. Упорядочивание дуг и вершин орграфа
- •1.8. Определение экстремальных путей на графах.
- •1.9. Порядковая функция орграфа без контуров.
- •Вопросы для повторения.
- •Глава 2. Нахождение минимальных и максимальных путей на орграфах
- •1. Нахождение кратчайших путей. Алгоритм Дейкстры
- •2. Нахождение кратчайших путей. Алгоритм Беллмана-Мура
- •Алгоритм нахождения максимального пути
- •4. Особенности алгоритмов теории графов
- •Вопросы для повторения.
- •Задачи для самостоятельного решения.
- •Глава 3. Остовы графов, фундаментальные циклы. Эйлеровы и гамильтоновы графы. Доминирующие множества и клики
- •1. Деревья (основные определения)
- •2. Задача об остове экстремального веса
- •3. Обходы графов. Фундаментальные циклы
- •4. Клики, независимые множества
- •Вопросы для повторения.
- •Глава 4. Планарные графы
- •1. Планарность графов
- •2. Алгоритм укладки графа на плоскости
- •Вопросы для повторения.
- •Глава 5. Потоки в сетях
- •1. Потоки в сетях
- •Теорема Форда-Фалкерсона
- •Случайные графы
- •Заключение
- •Библиографический список
- •Оглавление
- •Основы теории графов
- •394026 Воронеж, Московский просп., 14
2. Нахождение кратчайших путей. Алгоритм Беллмана-Мура
Веса дуг могут быть и отрицательными.
Этап 1. Нахождение длин кратчайших путей от вершины s до всех остальных вершин графа.
Шаг 1. Присвоение начальных значений. - множество вершин в очереди.
Шаг 2. Корректировка меток и очереди.
Удаляем из очереди Q вершину, находящуюся в самом начале очереди. Для каждой вершины хi, непосредственно достижимой из , корректируем её метку по формуле
.
Если при этом , то корректируем очередь вершин, иначе продолжаем перебор вершин и корректировку временных меток.
Корректировка очереди. Если хi не была ранее в очереди и не находится в ней в данный момент, то ставим её в конец очереди. Если хi уже была когда-нибудь ранее в очереди или находится там в данный момент, то переставим её в начало очереди.
Шаг 3. Проверка на завершение 1-го этапа.
Если , то возвращаемся к началу 2-го шага; если же , то 1-ый этап закончен, т.е. минимальное расстояние от s до всех вершин графа найдены.
Этап 2. Построение кратчайшего пути от s до t.
Совпадает с соответствующим этапом в алгоритме Дейкстры и выполняется по формуле
Пример. Задана весовая матрица Ω сети G:
Рис. 35
Рассчитать кратчайший путь от узла х1 до узла х6.
Решение.
Этап 1. Первая итерация.
Шаг 1.
Шаг 2. множество вершин непосредственно достижимых из вершины .
х2 надо было поставить в конец очереди, но Q было пусто, поэтому конец очереди совпал с началом.
Шаг 3. Нет. Переход на начало 2-го шага.
Вторая итерация.
Шаг 2.
Вершину х4 надо поставить в начало очереди, но она уже стоит там.
Шаг 3. Нет, переход на третью итерацию 2 –го шага.
Третья итерация.
Шаг 2.
Вершину х3 надо ставить в начало очереди, но она уже там.
Вершину х5 передвигаем из конца очереди в начало.
Шаг 3. Нет, переход на четвёртую итерацию 2 –го шага.
Четвёртая итерация.
Шаг 2.
Шаг 3. Нет.
Пятая итерация.
Шаг 2.
Шаг 3. Нет.
Шестая итерация.
Шаг 2.
Q содержало только вершину x6 и она встала в начало очереди.
Шаг 3. Нет.
Седьмая итерация.
Шаг 2.
Шаг 3. Конец 1-го этапа. Найдены минимальные расстояния до всех вершин от первой. Эти расстояния таковы:
Этап 2.
Шаг 4. Полагаем . Пусть - множество вершин, непосредственно предшествующих . .
Первая итерация.
или
Включаем дугу (х5, х6) в кратчайший путь. . Возвращаемся на 4-ый шаг.
Вторая итерация. Нет.
; ,
.
Включаем дугу (х3, х5) в кратчайший путь. .Возвращаемся на 4-ый шаг.
Третья итерация. Нет.
.
. Включаем дугу (х4, х3) в кратчайший путь. . Возвращаемся на 4-ый шаг.
Четвёртая итерация. Нет. .
. Включаем дугу (х2, х4) в кратчайший путь . Возвращаемся на 4-ый шаг.
Пятая итерация. Нет. .
. Включаем дугу (х1, х2) в кратчайший путь . Возвращаемся на 4-ый шаг.
Шестая итерация. Да. Задача закончена. Искомый кратчайший путь от вершины х1 до вершины х6 имеет нулевой вес и состоит из следующих дуг: