Автор: Пользователь скрыл имя, 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
Второй шаг'. Шаг алгоритма повторяется. Снова находим «ближайшую» из непосещенных вершин. Это вершина 2 с меткой 7.
Снова пытаемся уменьшить
метки соседей выбранной
Первый (по порядку) сосед вершины 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.
Информация о работе Программная реализация алгоритма Дейкстры