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

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

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






Дерево кратчайших путей – это ориентированное дерево с корнем в вершине 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; просмотров: 4870. Нарушение авторских прав; Мы поможем в написании вашей работы!



Кардиналистский и ординалистский подходы Кардиналистский (количественный подход) к анализу полезности основан на представлении о возможности измерения различных благ в условных единицах полезности...

Обзор компонентов Multisim Компоненты – это основа любой схемы, это все элементы, из которых она состоит. Multisim оперирует с двумя категориями...

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

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

ТЕРМОДИНАМИКА БИОЛОГИЧЕСКИХ СИСТЕМ. 1. Особенности термодинамического метода изучения биологических систем. Основные понятия термодинамики. Термодинамикой называется раздел физики...

Травматическая окклюзия и ее клинические признаки При пародонтите и парадонтозе резистентность тканей пародонта падает...

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

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

ЛЕЧЕБНО-ПРОФИЛАКТИЧЕСКОЙ ПОМОЩИ НАСЕЛЕНИЮ В УСЛОВИЯХ ОМС 001. Основными путями развития поликлинической помощи взрослому населению в новых экономических условиях являются все...

МЕТОДИКА ИЗУЧЕНИЯ МОРФЕМНОГО СОСТАВА СЛОВА В НАЧАЛЬНЫХ КЛАССАХ В практике речевого общения широко известен следующий факт: как взрослые...

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