Программная реализация алгоритма Дейкстры

Автор: Пользователь скрыл имя, 10 Февраля 2013 в 18:55, реферат

Краткое описание

Ориентированный граф (сокращенно орграф) G = (V, E) состоит из множества вершин V и множества дуг E. Вершины также называют узлами, а дуги – ориентированными ребрами. Дуга представима в виде упорядоченной пары вершин (v, w), где вершина v называется началом, а w – концом дуги.
Кратчайший путь из u в v – это любой путь p из u в v, для которого w(p) = δ(u, v), где:
w(p) = сумма весов всех ребер пути p
δ(u, v) = min{w(p): по всем путям p из u в v}, если существует путь из u в v; ∞ - в противном случае

Оглавление

1. Алгоритм поиска кратчайшего пути в ориентированном графе 3
2. Алгоритм поиска эйлерова цикла 7
3. Алгоритм топологической сортировки 10
4. Задача (алгоритм Дейкстры) 12
Список использованных источников 18

Файлы: 1 файл

6354 - Логистика.doc

— 165.00 Кб (Скачать)

Второй шаг'. Шаг алгоритма повторяется. Снова находим «ближайшую» из непосещенных вершин. Это вершина 2 с меткой 7.

Снова пытаемся уменьшить  метки соседей выбранной вершины, пытаясь пройти в них через 2-ю. Соседями вершины 2 являются 1, 3, 4.

Первый (по порядку) сосед  вершины 2 — вершина 1. Но она уже  посещена, поэтому с 1-й вершиной ничего не делаем.

Следующий сосед вершины 2 — вершина 4/*3*/. Если идти в неё  через 2-ю, то длина такого пути будет = кратчайшее расстояние до 2 + расстояние между вершинами 2 и 4 = 7 + 15 = 22. Поскольку 22< , устанавливаем метку вершины 4 равной 22.

Ещё один сосед вершины 2 — вершина 3. Если идти в неё через 2, то длина такого пути будет = 7 + 10 = 17. Но текущая метка третьей вершины  равна 9<17, поэтому метка не меняется.

Все соседи вершины 2 просмотрены, замораживаем расстояние до неё и  помечаем ее как посещенную.

Третий шаг. Повторяем шаг алгоритма, выбрав вершину 3. После ее «обработки» получим такие результаты:

Дальнейшие  шаги. Повторяем шаг алгоритма для оставшихся вершин (Это будут по порядку 6, 4 и 5).

Завершение  выполнения алгоритма. Алгоритм заканчивает работу, когда вычеркнуты все вершины. Результат его работы виден на последнем рисунке: кратчайший путь от вершины 1 до 2-й составляет 7, до 3-й — 9, до 4-й — 20, до 5-й — 20, до 6-й — 11.

 

 

Список использованных источников

 

1. Алексеев В.Б. Введение в теорию сложности алгоритмов. М.: Изд. отдел ф-та ВМиК МГУ, 2002.

2. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979.

3. Кнут Д.Э. Искусство программирования для ЭВМ. Т. 3. Сортировка и поиск. М.: Мир, 1978.

4. Свами М., Тхуласираман К. Графы, сети и алгоритмы. М.: Мир, 1984.




Информация о работе Программная реализация алгоритма Дейкстры