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

Выбор оптимального маршрута по алгоритму Дейкстры

Анализ исходных данных | Стратегия 1: Найм и увольнение. | Стратегия 2: Сверхурочные и частичная занятость. | Стратегия 3: Использование склада. | Оптимальная смесь стратегий. | Задачи для самостоятельного решения | Теоретические основы | Задачи для самостоятельного решения | Задача оптимального распределения капитальных вложений в предприятия | Задачи для самостоятельного решения |


Читайте также:
  1. I. ВЫБОР ТЕМЫ КУРСОВОЙ РАБОТЫ
  2. III. Выбор мощности силового трансформатора.
  3. III. Репрезентативность выборки
  4. III. Репрезентативность выборки 1 страница
  5. III. Репрезентативность выборки 2 страница
  6. III. Репрезентативность выборки 3 страница
  7. III. Репрезентативность выборки 4 страница

Алгоритм Дейкстры предназначен для нахождения кратчайшего пути между вершинами в неориентированном графе.

Идея алгоритма следующая: сначала выбирается путь до начальной вершины равным нулю, эта вершина заносится во множество уже выбранных, расстояние от которых до оставшихся невыбранных определено. На каждом этапе находится следующая невыбранная вершина, расстояние до которой наименьшее, и соединённая с какой-нибудь вершиной из множества выбранных (это расстояние будет равно расстоянию до уже выбранной вершины плюс длина ребра)[2, 3].

В качестве примера рассмотрим задачу нахождения кратчайшего пути от вершины A до вершины D для графа на Рис.6.

 

Рис.6. Взвешенный неориентированный граф.

На Рис.7 представлен фрагмент рабочего листа приложения MS Excel, на котором реализован алгоритм Дейкстры для сформулированной задачи.

Шаг 1-ый. Выбираем вершину A. Выбранная вершина напрямую связана с вершинами B и C. Расстояние до B равно 7, а до C – 10. Поэтому дополняем множество выбранных вершин вершиной B.

Шаг 2-ой. От выбранного множества A и B кратчайшее прямое расстояние до вершины F. Поэтому дополняем множество выбранных вершин вершиной F.

Шаг 3-ий. От выбранного множества A, B и F кратчайшее прямое расстояние до вершины E. Дополняем множество выбранных вершин вершиной E.

Шаг 4-ый. От выбранного множества A, B,F и E кратчайшее прямое расстояние до вершины H. Дополняем множество выбранных вершин вершиной H.

Шаг 5-ый. От выбранного множества A, B, F, E и H кратчайшее прямое расстояние до вершины G. Дополняем множество выбранных вершин вершиной G.

Шаг 6-ой. От выбранного множества A, B, F, E, H и G кратчайшее прямое расстояние до вершины I. Дополняем множество выбранных вершин вершиной I.

Рис.7. Поиск кратчайшего пути с помощью алгоритма Дейкстры.

 

Шаг 7-ой. От выбранного множества A, B, F, E, H, G и I кратчайшее прямое расстояние до вершины целевой вершины B. Процесс нахождения минимального расстояния завершён.

Выбор траектории осуществляется просмотром сформированной таблицы в обратном порядке и представлен наглядно на Рис.8.

Итак, минимальная длина пути от вершины A до вершины D составляет 44 условных единиц. Траектория кратчайшего пути (A, B, F,H, D).

 

Рис.8. Выбор оптимальной траектории.

 


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


<== предыдущая страница | следующая страница ==>
Выбор оптимального маршрута методом динамического программирования| Нахождение оптимальных маршрутов.

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