3.3. Нахождение кратчайшего расстояния
Дан связный неориентированный взвешенный граф G. Если существует ребро с вершинами vi и vj, то стоимость перехода из vi в vj составит C(i,j) = C (vi, vj). Если же ребра vi – vj нет, то полагаем C(i,j) =.
На выходе в данном графе выделяется вершина v0. Надо найти кратчайшее расстояние от v0 до всех остальных вершин.
Для решения задачи поиска кратчайшего расстояния используется (кроме прямого перебора) два алгоритма: Форда – Беллмана и Дейкстры.
Рассмотрим простейший алгоритм поиска кратчайшего расстояния – алгоритм Форда-Беллмана. Этот алгоритм является классическим примером алгоритма на поиск транзитивного замыкания.
Общая идея работы всех алгоритмов на поиск транзитивного замыкания
Пересчитываем что-либо (в нашем случае, стоимости вершин) до тех пор, пока это что-то не стабилизируется. Как только произойдет стабилизация, необходимо остановиться. Ответ получен.
- Основные понятия. Справочный материал
- Основные понятия
- 1.2. Справочный материал. Сравнение скорости роста основных функций
- 2 Новые быстрые версии старых алгоритмов
- 2.1. Сортировки массивов
- 2.1.1 Метод прямого выбора (SelectSort)
- 2.1.2 Быстрая сортировка методом двоичных вставок (MergeSort)
- 2.2. Преобразование Фурье (бпф)
- 2.2.1. Дискретное преобразование Фурье
- 2.2.2. Полубыстрое преобразование Фурье (ппф)
- 2.2.3. Быстрое преобразование Фурье (бпф)
- 2.3. Быстрая свертка
- 2.3.1. Понятие свертки
- 2.3.2. Обычный и быстрый алгоритм свертки
- 2.4. Быстрое умножение
- 2.4.1. Быстрое умножение чисел
- 1 Суммирование
- 4 Произведения чисел вдвое меньшей
- 2.4.2. Быстрое умножение матриц
- 2.4.3. Очень быстрое умножение числе (алгоритм Шенхаге – Штрассена)
- 3. Задачи на графах
- 3.1. Справочный материал
- 3.2. Поиск минимального остова в связном неориентированном взвешенном графе
- 3.3. Нахождение кратчайшего расстояния
- 3.3.1. Алгоритм Форда – Беллмана
- 3.3.2. Алгоритм Дейкстры
- 3.4. Нахождение диаметра, радиуса и центра графа
- 3.5. Задача об изоморфизме графов
- 3.6. Задача коммивояжера. Её решение методом ветвей и границ.
- Задачи динамического программирования
- Задачи динамического программирования. Её решение методом динамического программирования.
- 4.2. Задача об оптимальном наборе самолетом скорости и высоты
- 4.3. Задача грабителя (задача о рюкзаке)
- 4.4. Задача о перемножении матриц
- 5 Классы p и np
- 5.1 Машина Тьюринга
- 5.2 Недетерменированные машины Тьюринга(ндмт)
- 5.3 Сводимость. Np-полнота.
- 5.4 Иерархия по сложности. Труднорешаемые задачи.
- Классы сложности.
- 6 Неразрешимые задачи
- 6.1 Новая модель алгоритма вычислений.
- 6.2 Нумерация программ
- 6.3 Неразрешимые проблемы
- 6.4 Теорема об ускорении
- Лабораторные работы
- Расчетно-графическое задание
- Ответы к домашним заданиям