Студопедия Главная Случайная страница Обратная связь

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

Построение дерева кратчайших путей





Дерево кратчайших путей – это ориентированное дерево с корнем в вершине S. Все пути в этом дереве – кратчайшие для данного графа.

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

Построим дерево кратчайших путей для нашего примера.

Сначала включаем в дерево корень – вершину 1. Затем в дерево включается дуга (1,6). Следующей была упорядочена вершина 9, длина кратчайшего пути до которой равна 3. Первый раз число 3 появилось в третьей строке, которая заполнялась при . Следовательно, вершина 6 – предпоследняя вершина кратчайшего пути до вершины 9. Включаем в дерево дугу (6,9) длины 1.

Затем была упорядочена вершина 2 с длиной кратчайшего пути, равной 4. Это число первый раз появилось в третьей строке, которая заполнялась при . Следовательно, кратчайший путь во вторую вершину проходит по дуге (6,2). Включаем в дерево дугу (6,2) длины 2.

Далее была упорядочена вершина 12, . Первый раз число 4 появляется в четвертой строке, которая заполнялась при . В дерево включается дуга (9,12) длины 1. Полное дерево кратчайших путей показано на рис. 5.

Алгоритм Дейкстры может ошибаться, если в графе есть дуги отрицательной длины. Так, отыскивая кратчайшие пути от вершины s =1 для графа на рис. 6, алгоритм сначала упорядочит вершину 3, затем вершину 2 и закончит работу. При этом этот кратчайший путь до вершины 3, с точки зрения алгоритма Дейкстры, - это дуга (1,3) длины 3.

На самом деле, кратчайший путь до вершины 3 состоит из дуг (1,2) и (2,3), длина этого пути равна 5+(-3)=2.

Из-за наличия дуги (2,3) отрицательной длины –3 оказались нарушенными следующие базовые принципы:

· ближайшая к s вершина лежит от нее на расстоянии двух дуг, а не одной;

· промежуточная вершина кратчайшего пути 1-2-3 (вершина 2) лежит дальше от вершины 1 (на расстоянии 5), чем конечная вершина пути 3.

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

 

 

 







Дата добавления: 2015-06-12; просмотров: 5197. Нарушение авторских прав; Мы поможем в написании вашей работы!




Композиция из абстрактных геометрических фигур Данная композиция состоит из линий, штриховки, абстрактных геометрических форм...


Важнейшие способы обработки и анализа рядов динамики Не во всех случаях эмпирические данные рядов динамики позволяют определить тенденцию изменения явления во времени...


ТЕОРЕТИЧЕСКАЯ МЕХАНИКА Статика является частью теоретической механики, изучающей условия, при ко­торых тело находится под действием заданной системы сил...


Теория усилителей. Схема Основная масса современных аналоговых и аналого-цифровых электронных устройств выполняется на специализированных микросхемах...

Тема: Составление цепи питания Цель: расширить знания о биотических факторах среды. Оборудование:гербарные растения...

В эволюции растений и животных. Цель: выявить ароморфозы и идиоадаптации у растений Цель: выявить ароморфозы и идиоадаптации у растений. Оборудование: гербарные растения, чучела хордовых (рыб, земноводных, птиц, пресмыкающихся, млекопитающих), коллекции насекомых, влажные препараты паразитических червей, мох, хвощ, папоротник...

Типовые примеры и методы их решения. Пример 2.5.1. На вклад начисляются сложные проценты: а) ежегодно; б) ежеквартально; в) ежемесячно Пример 2.5.1. На вклад начисляются сложные проценты: а) ежегодно; б) ежеквартально; в) ежемесячно. Какова должна быть годовая номинальная процентная ставка...

Значення творчості Г.Сковороди для розвитку української культури Важливий внесок в історію всієї духовної культури українського народу та її барокової літературно-філософської традиції зробив, зокрема, Григорій Савич Сковорода (1722—1794 pp...

Постинъекционные осложнения, оказать необходимую помощь пациенту I.ОСЛОЖНЕНИЕ: Инфильтрат (уплотнение). II.ПРИЗНАКИ ОСЛОЖНЕНИЯ: Уплотнение...

Приготовление дезинфицирующего рабочего раствора хлорамина Задача: рассчитать необходимое количество порошка хлорамина для приготовления 5-ти литров 3% раствора...

Studopedia.info - Студопедия - 2014-2025 год . (0.008 сек.) русская версия | украинская версия