Задача о кратчайших путях.
Пусть дан граф с неотрицательными весами на дугах. Представляют интерес две задачи:
Какова длина кратчайшего пути, ведущего из одной вершины в другую? Каков этот путь?
Каковы длины кратчайших путей от выделенной вершины до всех остальных вершин графа?
Алгоритм, который будет описан, называется алгоритмом Дейкстры. Дейкстра Еусгер родился в 1930 году в Нидерландах. Считается одним из основоположников программирования как учебной дисциплины. С 1984 года работает в Техасе.
Согласно алгоритму отыскивается кратчайшее расстояние от вершины v0 к вершине z простого взвешенного графа G(V, E). Если граф не является простым, то его можно сделать таковым, отбрасывая все петли заменяя каждое множество параллельных ребер кратчайшим ребром (ребром с наименьшим весом). Обозначим через wi j - вес ребра (vi, vj). Начинаем от вершины v0 и просматриваем граф в ширину, помечая вершины vi значениями-метками их расстояний от v0. Метки могут быть временными или окончательными
Временная метка вершины vj – это минимальное расстояние от вершины v0 до вершины vj, когда в определении пути на графе учитываются не все маршруты из v0 в vj.
Окончательная метка – это минимальное расстояние от вершины v0 до вершины vj. Таким образом, в каждый момент времени работы алгоритма некоторые вершины будут иметь окончательные метки, а некоторые – временные. Алгоритм заканчивается, когда вершина vn получит окончательную метку, т.е. расстояние от v0 до z..
Каждой вершине vk присваивается упорядоченная пара (m(vk), vr). Первая координата этой пары является меткой вершины vk, а вторая координата – предыдущую вершину пути от v0 к vk.
Вначале вершине v0 присваивается окончательная метка 0 (нулевое расстояние до самой себя), а каждой из остальных вершин присваивается временная метка ∞. На каждом шаге одной вершине с временной меткой присваивается окончательная и поиск продолжается дальше. На каждом шаге метки меняются следующим образом:
Когда вершина vk получит постоянную метку m(vk) каждой вершине vj, смежной к vk, присваивается новая временная метка m(vj), равная минимуму между ее старой временной меткой и числом (wk j + m(vk)).
Смежная с vk вершина, получившая наименьшую временную метку, делается постоянной (имеет постоянную метку).
Если вершина z не имеет постоянной метки, то возвращаемся к пункту 1.
Если z имеет постоянную метку m(z), то эта метка является кратчайшим расстоянием от v0 к z
Для нахождения пути надо рассмотреть постоянные метки в обратном направлении от z к v0.
П р и м е р 1.
Рассмотрим пример варианта поиска кратчайшего пути поиска кратчайшего пути на графе, представленном на рисунке.
. 10 z
5 2
v1 v4
7 1 8 3 6
3 3 5
v0 2 v2 5 v3 7 v5
Процесс назначения меток вершинам графа на каждом шаге представляется в виде таблицы.
Рамочками выделены окончательные метки, т.е. расстояние от них до v0 ( вторая координата – номер предыдущей вершины). По такой таблице легко восстановить путь перемещения от v0 к z и обратно. Кратчайшим путем является перемещение v0, v2, v1, v3, v4, z. Кратчайшее расстояние равно 11.
Следует отметить высокую эффективность алгоритма Дейкстры и его широкую применимость в окружающем нас мире. Бортовые компьютеры современных автомобилей с помощью алгоритма Дейкстры позволяют находить трассу кратчайшего пути. Маршрут доставки сообщения с одного сервера на другой и заторы, являющиеся важнейшими элементами глобальной сети интернет, также находится с помощью алгоритма Дейкстры.
П р и м е р 2 .
Для графа, приведенного на рисунке, найти длины кратчайших путей от вершины v0 ко всем остальным и восстановить кратчайший путь от v0 к v6.
v1 1 v8 1 v7
1
1 1 1
3
v0 v6
v2 1 v3 2
2 4 3
v4 1 v5
Кратчайший путь от v0 в v7 имеет следующий вид .Это расстояние равно 4. Путь через вершину v2 более длинный и равен %
Нижние постоянные метки дают кратчайшее расстояние от v0 до соответствующей вершины.
- Дискретная математика.
- Множества.
- П римеры
- Или по другому
- Операции над множествами.
- Основные свойства операций над множествами.
- Алгебра высказываний.
- Логические операции над высказываниями.
- Отрицание.
- Конъюнкция.
- Эквиваленция
- Импликация.
- Формулы алгебры высказываний.
- Элементарные высказывания, символы логических переменных – формулы;
- Если f1 и f2 – формулы алгебры высказываний, то
- Других формул алгебры высказываний нет.
- Равносильность формул.
- Совершенная дизъюнктивная нормальная форма.
- Приведение формулы к сднф.
- Совершенная конъюнктивная нормальная форма.
- Приведение формулы к скнф.
- Полнота и замкнутость.
- Минимизация днф.
- Способы задания булевых функций.
- Табличный способ задания.
- Графический способ задания.
- Аналитический способ задания.
- Элементы теории графов.
- Матрицы графов.
- Некоторые общие понятия теории графов.
- Взвешенные графы и алгоритмы поиска кратчайшего пути.
- Задача о кратчайших путях.
- Элементы теории алгоритмов.
- Понятие автомата.
- Машина Тьюринга.
- Автомат Мили.
- Правило суммы.
- Правило прямого произведения.
- Размещения с повторениями.
- Размещения без повторений.
- Перестановки.
- Сочетания.
- Сочетания с повторениями.