Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

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

Читайте также:
  1. RSVP алгоритммен тарату жүйесіне QoS-көрсеткішінің табу әдістемесі
  2. Алгоритм
  3. Алгоритм 1. Сила Мистического Сознания.
  4. Алгоритм 2. Состояние ДИВО (Динамической Воли).
  5. Алгоритм 3. Состояние Имагинатора.
  6. Алгоритм 4. Кристаллизация Я.
  7. Алгоритм введения и изменения заряда точки привязки

Результатом алгоритма поиска кратчайшего пути является последовательность ребер, соединяющая заданные две вершины и имеющая наименьшую длину среди всех таких последовательностей.

Жадный алгоритм построения минимального остовного дерева непригоден для поиска кратчайшего пути между двумя вершинами, поскольку на каждом проходе он учитывает длину лишь одного ребра.

Если же изменить его так, чтобы при выборе ребра, ведущего в кайму, он выбирал ребро, являющееся частью кратчайшего в целом пути из начальной вершины, то мы получим требуемый результат. Точнее говоря, вот измененный алгоритм:

Шаг 1. Выбрать начальную вершину

Шаг 2. Создать начальную кайму из вершин, соединенных с начальной

Шаг 3. Вершина назначения не достигнута?

Если нет, то переход на Шаг 4.

Иначе – переход на Шаг 9

Шаг 4. Выбрать вершину каймы с кратчайшим расстоянием до начальной

Шаг 5. Добавить эту вершину и ведущее в нее ребро к дереву

Шаг 6. Изменить кайму путем добавления к ней вершин, соединенных с вновь добавленной

Шаг 7. Для всякой вершины каймы выполнить: приписать к ней ребро, соединяющее ее с деревом и завершающее кратчайший путь к начальной вершине

Шаг 8. Переход на Шаг 3

Шаг 9. Конец

Проиллюстрируем алгоритм на примере графа, приведенного на Рис. 3.6. Будем искать кратчайший путь от вершины A к вершине G.

Рис. 3.15. Начальная вершина

 

 

Рис. 3.16. Добавление второй и третьей вершин

Рис. 3.17. Добавление четвертой и пятой вершин

Рис. 3.18. Заключительные шаги алгоритма Дейкстры

 


Дата добавления: 2015-10-13; просмотров: 140 | Нарушение авторских прав


Читайте в этой же книге: Основные определения | Математическое представление графов | Алгоритм Дейкстры-Прима |
<== предыдущая страница | следующая страница ==>
Алгоритм Крускала| Повний граф

mybiblioteka.su - 2015-2024 год. (0.006 сек.)