алгоритм кратчайшего пути на графе

Обучение
Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации Главная Тексты статей Добавить статьи Форум Контакты
Едсгер Дейкстра (1930-2002) – нидерландский математик.
В различных приложениях теории графов дугам (рёбрам) графов, моделирующих реальные процессы, обычно сопоставляются какие-либо числовые характеристики. Например, если дугами изображаются транспортные магистрали, то числовой характеристикой дуги может быть пропускная способность соответствующей магистрали и т.п. В таких случаях говорят, что дугам графа приписаны определённые веса.

Пусть ‑ орграф. Если каждой дуге поставлено в соответствие число , то граф называется графом со взвешенными дугами или сетью. При этом вершины графа называют узлами сети. Число называется весом дуги . Весом пути µ (длиной, стоимостью и т.д. в зависимости от контекста) сети называется число .
Понятие сети и веса маршрута для неориентированного графа определяется аналогично.
Рис. 13 А В С F D E
Сеть на рис.13 может представлять, например, длины дорог в километрах между шестью деревнями. Т.к. количество вершин в этом графе невелико, то для нахождения наиболее короткого пути между деревнями, нужно перебрать все возможные пути. Это возможно, т.к. количество вершин в этом графе невелико. В реальных задачах число вершин настолько велико, что такой подход к поиску кратчайшего пути слишком неэффективен.

Существует множество алгоритмов поиска кратчайшего пути, но мы познакомимся только с одним, алгоритмом Дейкстры.
Кратчайший путь – это путь минимального общего веса соединяющий выбранные вершины. Общий вес кратчайшего пути, ведущего из вершины в вершину , называют расстоянием от до .
Определим весовую матрицу Ω чьи элементы задаются формулой
Например, для графа на рис.13 матрица Ω имеет вид:
Матрица Ω является простым обобщением матрицы смежности вершин.
Пусть ‑ ориентированный граф со взвешенными дугами. Обозначим через s ‑ вершину – начало пути, а через t ‑ вершину – конец пути.
В процессе работы алгоритма Дейкстры вершинам графа приписываются числа (метки) , которые служат оценкой длины (веса) кратчайшего пути от вершины s к вершине . Если вершина получила на некотором шаге метку , это означает, что в графе G существует путь из s в , имеющий вес .
Метки могут находиться в двух состояниях – быть временными или постоянными. Превращение метки в постоянную означает, что кратчайшее расстояние от вершины s до соответствующей вершины найдено.
Ограничения алгоритма Дейкстры – веса должны быть положительными.
Алгоритм состоит из 2-х этапов:
I этап – нахождение длины кратчайшего пути;
II этап – построение кратчайшего пути от вершины s к вершине t.
Алгоритм Дейкстры
П.4. Упорядочивание дуг и вершин орграфа | Первая итерация.
Карта сайта Карта сайта укр
Полезное
Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных
Полезен материал? Поделись:

алгоритм дейкстры нахождения кратчайшего пути

алгоритм кратчайшего пути в графе

Дa, чуть не зaбыл, aлгоритм рaспрострaнения волны может прекрaсно  Достоинствa - простотa, нaдёжность, 100% сaмый короткий путь (для клaссического методa).

Читать

алгоритм поиска кратчайшего пути в графе c++

Лабораторная работа № 7. Алгоритм нахождения кратчайшего пути. Задача.  Определяется будет ли путь из вершины i в j через вершину k короче, чем прямой25 марта 2005