№12. Решение задачи нахождения кратчайшего пути в графе с использованием алгоритма Дейкстры

Цель: научить находить кратчайший путь в графе при помощи алгоритма Дейкстры.

Оборудование: практикум, тетрадь для лабораторных и практических работ.

Литература:

1. Кристофидес Н. Теория графов. Алгоритмический подход. - М.: Мир, 1979. С. 175-189.
2. Новиков Ф. А. Дискретная математика для программистов. - СПб.: Питер, 2000. С. 228-232.
3. Таха, Хемди. Введение в исследование операций - М.: Издательский дом "Вильямс", 2005. С. 250-265.

Время выполнения: 2 часа.

ВОПРОСЫ ВХОДНОГО КОНТРОЛЯ:

1. Дайте определение графа, приведите примеры.
2. Сформулируйте определение пути (маршрута).
3. Дайте понятие кратчайшего пути.
4. Сформулируйте постановку задачи нахождения кратчайшего пути от заданного узла до всех остальных узлов в графе.
5. Объясните суть алгоритма Дейкстры.

КРАТКИЕ ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ:

Алгоритм Дейкстры разработан для поиска кратчайшего пути между заданным исходным узлом и любым другим узлом сети. В процессе выполнения этого алгоритма при переходе от узла i к следующему узлу j используется специальная процедура пометки ребер. Обозначим через u_i кратчайшее расстояние от исходного узла 1 до узла i, через d_ij — длину ребра (i, j). Тогда для узла j определим метку [u_j, i] следующим образом.

[u_j, i] = [u_i + d_ij, i], d_ij > 0

Метки узлов в алгоритме Дейкстры могут быть двух типов: временные и постоянные. Временная метка впоследствии может быть заменена на другую временную, если будет найден более короткий путь к данному узлу. Когда же станет очевидным, что не существует более короткого пути от исходного узла к данному, статус временной метки изменяется на постоянный.

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

1) Исходному узлу (узел 1) присваивается постоянная метка [0, —]. Полагаем i = 1;

2) Вычисляются временные метки [u_i + d_ij, i] для всех узлов j, которые можно достичь непосредственно из узла i и которые не имеют постоянных меток. Если узел j уже имеет метку [u_j, k], полученную от другого узла k, и, если u_i + d_ij < u_j, тогда метка [u_j, k] заменяется на [u_i + d_ij, i].

3) Если все узлы имеют постоянные метки, процесс вычислений заканчивается. В противном случае выбирается метка [u_r, s] с наименьшим значением расстояния u_r среди всех временных меток (если таких меток несколько, то выбор произволен). Полагаем i = r и повторяем этап 2.

МЕТОДИЧЕСКИЕ УКАЗАНИЯ:

1. Найти кратчайшие пути от вершины 1 ко всем остальным вершинам графа.

Решение.

СОДЕРЖАНИЕ РАБОТЫ:

ВОПРОСЫ ВЫХОДНОГО КОНТРОЛЯ:

1. Дайте определение графа, приведите примеры.
2. Сформулируйте определение пути (маршрута).
3. Дайте понятие кратчайшего пути.
4. Сформулируйте постановку задачи нахождения кратчайшего пути от заданного узла до всех остальных узлов в графе.
5. Объясните суть алгоритма Дейкстры.

ДОМАШНЕЕ ЗАДАНИЕ:

Выучить алгоритм Дейкстры.