Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

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






Пошук найкоротшої відстані між вершинами графа (алгоритм Дейкстри).






Алгоритмзнаходить найкоротші шляхи від деякої вершини до всіх інших вершин графа за умови невід’ємності ваг його ребер.

Крок 1. Вершині , від якої шукаються найкоротші шляхи, приписати постійну позначку . Всім іншим вершинам приписати тимчасові позначки .

Крок 2. Для всіх ребер , інцидентних вершині , та таких, що мають тимчасову позначку, змінити позначки у відповідності з формулою , де — вага ребра .

Крок 3. Знайти вершину з мінімальною тимчасовою позначкою. Позначити таку позначку як постійну. Позначити ребро, що з’єднує цю вершину з її прообразом, стрілкою. Прийняти цю вершину у якості та перейти до кроку 2.

Алгоритм повторюють доти, доки всі вершини графа не отримають постійні позначки. По закінченні роботи алгоритму позначка деякої вершини дає довжину найкоротшого шляху, від цієї вершини до початкової, а сам шлях можна відновити за допомогою ребер зі стрілками.

 


Поделиться с друзьями:

mylektsii.su - Мои Лекции - 2015-2024 год. (0.007 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал