Алгоритм Дейкстры
Теория графов как математический аппарат для решения задач. Характеристика теории графов. Критерий существования обхода всех ребер графа без повторений, полученный Л. Эйлером при решении задачи о Кенигсбергских мостах. Алгоритм на графах Дейкстры.
| Рубрика | Математика |
| Вид | контрольная работа |
| Язык | русский |
| Дата добавления | 11.03.2011 |
| Размер файла | 466,3 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
ТГТУ
Контрольная работа
по дисциплине "Математика Часть II"
Тема: "Алгоритм Дейкстры"
Содержание
- Введение
- Теория графов как математический аппарат для решения задач
- Алгоритм Дейкстры
- Список используемой литературы
Введение
Каждый человек ежедневно, не всегда осознавая это, решает проблему: как получить наибольший эффект, обладая ограниченными средствами. Наши средства и ресурсы всегда ограничены. Не трудно выиграть сражение, имея армию в 10 раз большую, чем у противника. Но такой избыток ресурсов бывает не всегда. Чтобы достичь наибольшего эффекта, имея ограниченные средства, надо составить план, или программу действий. Теория графов рассматривает широкий круг задач с единой математической моделью, она находится сейчас в самом расцвете. Обычно её относят к топологии (потому что во многих случаях рассматриваются лишь топологические свойства графов), однако она пересекается со многими разделами теории множеств, комбинаторной математики, алгебры, геометрии, теории матриц, теории игр, математической логики и многих других математических дисциплин.
Голландский ученый Эдсгер Вайб Дейкстра (1930-2002) внес большой вклад в развитие динамического программирования и теорию графов. Известность Дейкстре принесли его работы в области применения математической логики при разработке компьютерных программ. Рассказывать об этом человеке можно очень долго и много. Можно перечислять научные регалии, звания и степени, бесконечно повторять слова "неоценимый вклад" и "основоположник". Он являлся одним из главных разработчиков языка ALGOL. Также ему принадлежит идея применения "семафоров" для синхронизации процессов в многозадачных системах и алгоритм нахождения кратчайшего пути на ориентированном графе с неотрицательными весами рёбер, известный как Алгоритм Дейкстры. В 1972 году за свой вклад в развитие информационных технологий Дейкстра был удостоен премии Тьюринга, которую называют аналогом Нобелевской премии в области компьютеров.
Здесь сразу уместно будет привести несколько фрагментов из воспоминаний Дейкстры. Во-первых, алгоритм этот создавался не из простого любопытства, а для решения вполне конкретной задачи, а именно, - минимизации длины проводников на аналоге "материнской платы" нового разрабатываемого командой компьютера X1, так что лавровый венок создателя первой "утилиты всех времен и народов" класса CAD-CAE Дейкстре можно присваивать смело. А вот "во-вторых" лучше сказать словами самого Дейкстры: "На много лет и в широких кругах алгоритм поиска кратчайшего пути был основным источником моей славы, что мне всегда казалось странным - ведь он был создан даже без карандаша и бумаги, за чашкой кофе на солнечной террасе кафе в Амстердаме".
Теория графов как математический аппарат для решения задач
ТЕОРИЯ ГРАФОВ - это область дискретной математики, особенностью которой является геометрический подход к изучению объектов. [9] Основной объект теории графов-граф и его обобщения.
Первые задачи теории графов были связаны с решением математических развлекательных задач и головоломок (задача о Кенигсбергских мостах, задача о расстановке ферзей на шахматной доске, задачи о перевозках, задача о кругосветном путешествии и другие).
Одним из первых результатов в теории графов явился критерий существования обхода всех ребер графа без повторений, полученный Л. Эйлером при решении задачи о Кенигсбергских мостах. Вот пересказ отрывка из письма Эйлера от 13 марта 1736 году: ”Мне была предложена задача об острове, расположенном в городе Кенигсберге и окруженном рекой, через которую перекинуто 7 мостов.
Спрашивается, может ли кто-нибудь непрерывно обойти их, проходя только однажды через каждый мост. И тут же мне было сообщено, что никто еще до сих пор не смог это проделать, но никто и не доказал, что это невозможно.
Вопрос этот, хотя и банальный, показался мне, однако, достойным внимания тем, что для его решения недостаточны ни геометрия, ни алгебра, ни комбинаторное искусство. После долгих размышлений я нашел лёгкое правило, основанное на вполне убедительном доказательстве, с помощью которого можно во всех задачах такого рода тотчас же определить, может ли быть совершен такой обход через какое угодно число и как угодно расположенных мостов или не может“. Кенигсбергские мосты схематически можно изобразить так (рис.1):
Рис.1. Кенигсбергские мосты на карте, и в виде графа.
В середине 19 в. появились работы, в которых при решении практических задач были получены результаты, относящиеся к теории графов. Так, например, Г. Кирхгоф при составлении полной системы уравнений для токов и напряжений в электрической схеме предложил по существу представлять такую схему графом и находить в этом графе основные деревья, с помощью которых выделяются линейно независимые системы контуров. А. Кэли, исходя из задач подсчета числа изомеров предельных углеводородов, пришел к задачам перечисления и описания деревьев, обладающих заданными свойствами, и решил некоторые из них.
В 20 в. задачи, связанные с графами, начали возникать не только в физике, химии, электротехнике биологии, экономике, социологии и т.д., но и внутри математики, в таких разделах, как топология, алгебра, теория вероятностей, теория чисел. В начале 20 в. графы стали использоваться для представления некоторых математических объектов и формальной постановки различных дискретных задач; при этом наряду с термином "граф" употреблялись и другие термины, например, карта, комплекс, диаграмма, сеть, лабиринт. После выхода в свет в 1936 году монографии Д. Кёнига термин "граф" стал более употребительным, чем другие. В этой работе были систематизированы известные к тому времени факты. В 1936 году вышла небольшая брошюра Ойстена Оре, содержащая блестящее элементарное введение в теорию графов. В 1962 году в Англии была издана книга французского математика Клода Бержа “Теория графов и её приложение”. Обе книги, безусловно, представляют интерес для любителей занимательной математики. Сотни известных головоломок, на первый взгляд не имеющих ничего общего друг с другом, легко решаются с помощью теории графов.
В 20-30-х годах 20 в. появились первые результаты, относящиеся к изучению свойств связности, планарности, симметрии графов, которые привели к формированию ряда новых направлений в теории графов.
Значительно расширились исследования по теории графов в конце 40-х - начале 50-х годов, прежде всего в силу развития кибернетики и вычислительной техники. Благодаря развитию вычислительной техники, изучению сложных кибернетических систем, интерес к теории графов возрос, а проблематика теории графов существенным образом обогатилась. Кроме того, использование ЭВМ позволило решать возникающие на практике конкретные задачи, связанные с большим объемом вычислений, прежде не поддававшиеся решению. Для ряда экстремальных задач теории графов были разработаны методы их решения, например, один из таких методов позволяет решать задачи о построении максимального потока через сеть. Для отдельных классов графов (деревья, плоские графы и т.д.), которые изучались и ранее, было показано, что решения некоторых задач для графов из этих классов находятся проще, чем для произвольных графов (нахождение условий существования графов с заданными свойствами, установление изоморфизма графов и др.).
Характеризуя проблематику теории графов, можно отметить, что некоторые направления носят более комбинаторный характер, другие - более геометрический. К первым относятся, например, задачи о подсчете и перечислении графов с фиксированными свойствами, задачи о построении графов с заданными свойствами. Геометрический (топологический) характер носят многие циклы задач теории графов, например, графов обходы, графов укладки. Существуют направления, связанные с различными классификациями графов, например, по свойствам их разложения.
В теории графов существуют специфические методы решения экстремальных задач. Один из них основан на теореме о максимальном потоке и минимальном разрезе, утверждающей, что максимальный поток, который можно пропустить через сеть из вершины U в вершину V, равен минимальной пропускной способности разрезов, разделяющих вершины U и V. Были построены различные эффективные алгоритмы нахождения максимального потока.
Результаты и методы теории графов применяются при решении транспортных задач о перевозках, для нахождения оптимальных решений задачи о назначениях, для выделения "узких мест" при планировании и управлении разработок проектов, при составлении оптимальных маршрутов доставки грузов, а также при моделировании сложных технология, процессов, в построении различных дискретных устройств, в программировании и т.д.
Развитие теории графов в основном обязано большому числу всевозможных приложений. По-видимому, из всех математических объектов графы занимают одно из первых мест в качестве формальных моделей реальных систем.
Графы нашли применение практически во всех отраслях научных знаний: физике, биологии, химии, математике, истории, лингвистике, социальных науках, технике и т.п. Наибольшей популярностью теоретико-графовые модели используются при исследовании коммуникационных сетей, систем информатики, химических и генетических структур, электрических цепей и других систем сетевой структуры.
Алгоритм Дейкстры
Алгоримтм Демйкстры (Dijkstra's algorithm) - алгоритм на графах, изобретённый нидерландским ученым Э. Дейкстрой в 1959 году. Находит кратчайшее расстояние от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса. Алгоритм широко применяется в программировании и технологиях, например, его использует протокол OSPF для устранения кольцевых маршрутов. Известен также под названием "Сначала Кратчайший Путь" (Shortest Path First).
Алгоритм Дейкстры решает задачу о кратчайших путях из одной вершины для взвешенного ориентированного графа G = (V, E) с исходной вершиной s, в котором веса всех рёбер неотрицательны ( (u, v) ? 0 для всех (u, v) E). В случае, когда ребра графа не равны, целесообразно использовать этот алгоритм.
Формулировка задачи. Имеется граф. Некоторая его вершина обозначена как вершина 1. Необходимо найти минимальные пути от вершины 1 до каждой из вершин графа. Минимальным путём будем называть путь с минимальной суммой цен вдоль пути. Ценой назовем неотрицательное число являющееся весом ребра.
Идея алгоритма. Идея основывается на следующем очевидном утверждении: Пусть построен минимальный путь из вершины а в вершину B. И пусть вершина B связана с некоторым количеством вершин i. Обозначим через Ci - цену пути из вершины B в вершину i. Выберем из Ci минимальную величину. Тогда минимальное продолжение пути из точки B пойдёт через выбранную величину.
Это утверждение действительно не требует доказательства. И из него вытекает очень серьёзное следствие. Пусть есть множество вершин через которые уже проходят минимальные пути. Такое множество гарантированно есть, это вершина 1. Утверждение сформулированное выше даёт возможность добавлять к уже существующему множеству вершин (будем далее называть их выделенными) еще одну вершину, а так как в графе количество вершин конечно, то за конечное количество шагов все вершины графа окажутся выделенными, а это и будет решением.
Сущность алгоритма Дейкстры и заключается в процедуре добавления еще одной вершины к множеству выделенных. Эта процедура состоит из двух шагов:
1. Строим множество вершин инцидентных выделенным и находим среди их вершину с наименьшей ценой. Найденная вершина добавляется в множество выделенных.
2. Строим множество вершин инцидентных выделенным и определяем для них новые цены. Новая цена вершины это минимальная цена пути от множества выделенных вершин до данной вершины. Строится новая цена так:
a. Для невыделенной вершины во множестве выделенных определяется подмножество вершин инцидентных данной.
b. Для каждой вершины выделенной подмножества определяется цена пути до данной.
c. Определяется минимальная цена. Эта цена и становится ценой вершины.
Алгоритм работает с двумя типами цен: ценой ребра и ценой вершины. Цены ребер являются постоянной величиной. Цены же вершин постоянно пересчитываются. Смысл этих цен различен. Цена ребра это цена перехода из вершины в вершину соединённую этим ребром. А цена вершины это цена минимального пути. Ещё одно важное замечание касается пересчета предварительных цен. Фактически, есть смысл пересчитывать предварительные цены только для тех вершин которые связаны с вершиной добавленной во множество выделенных на последнем шаге, так как для других вершин нет причин изменения предварительной цены.
Известно, что все цены (например, прокладки пути или проезда) неотрицательны. Найти наименьшую стоимость пути 1->i для всех i=1. n за время O (n2).
В процессе работы алгоритма некоторые города будут выделенными (в начале - только город 1, в конце - все). При этом:
для каждого выделенного города i хранится наименьшая стоимость пути 1->i; при этом известно, что минимум достигается на пути, проходящем только через выделенные города;
для каждого невыделенного города i хранится наименьшая стоимость пути 1->i, в котором в качестве промежуточных используются только выделенные города.
Множество выделенных городов расширяется на основании следующего замечания: если среди всех невыделенных городов взять тот, для которого хранимое число минимально, то это число является истинной наименьшей стоимостью. В самом деле, пусть есть более короткий путь. Рассмотрим первый невыделенный город на этом пути - уже до него путь длиннее! (Здесь существенна неотрицательность цен.)
Добавив выбранный город к выделенным, мы должны скорректировать информацию, хранимую для невыделенных городов. При этом достаточно учесть лишь пути, в которых новый город является последним пунктом пересадки, а это легко сделать, так как минимальную стоимость пути в новый город мы уже знаем.
Другими словами, каждой вершине из V сопоставим метку - минимальное известное расстояние от этой вершины до a. Алгоритм работает пошагово - на каждом шаге он "посещает" одну вершину и пытается уменьшать метки. Работа алгоритма завершается, когда все вершины посещены.
Инициализация. Метка самой вершины a полагается равной 0, метки остальных вершин - бесконечности. Это отражает то, что расстояния от a до других вершин пока неизвестны. Все вершины графа помечаются как непосещенные.
Шаг алгоритма. Если все вершины посещены, алгоритм завершается. В противном случае из еще не посещенных вершин выбирается вершина u, имеющая минимальную метку. Мы рассматриваем всевозможные маршруты, в которых u является предпоследним пунктом. Вершины, соединенные с вершиной u ребрами, назовем соседями этой вершины. Для каждого соседа рассмотрим новую длину пути, равную сумме текущей метки u и длины ребра, соединяющего u с этим соседом. Если полученная длина меньше метки соседа, заменим метку этой длиной. Рассмотрев всех соседей, пометим вершину u как посещенную и повторим шаг.
Поскольку алгоритм Дейкстры всякий раз выбирает для обработки вершины с наименьшей оценкой кратчайшего пути, можно сказать, что он относится к жадным алгоритмам.
Опишем более подробно схему работы алгоритма Дейкстры.
Алгоритм использует три массива из N (= числу вершин сети) чисел каждый. Первый массив A содержит метки с двумя значения: 0 (вершина еще не рассмотрена) и 1 (вершина уже рассмотрена); второй массив B содержит расстояния - текущие кратчайшие рас - стояния от до соответствующей вершины; третий массив с содержит номера вершин - k-й элемент С [k] есть номер предпоследней вершины на текущем кратчайшем пути из Vi в Vk. Матрица расстояний D [i,k] задает длины дуге D [i,k]; если такой дуги нет, то D [i,k] присваивается большое число Б, равное "машинной бесконечности".
Теперь можно описать:
1. (инициализация). В цикле от 1 до N заполнить нулями массив A; заполнить числом i массив C; перенести i-ю строку матрицы D в массив B, A [i]: =1; C [i]: =0 (i - номер стартовой вершины)
2. (общий шаг). Hайти минимум среди неотмеченных (т.е. тех k, для которых A [k] =0); пусть минимум достигается на индексе j, т.е. B [j] <=B [k] Затем выполняются следующие операции: A [j]: =1; если B [k] >B [j] +D [j,k], то (B [k]: =B [j] +D [j,k]; C [k]: =j) (Условие означает, что путь Vi. Vk длиннее, чем путь Vi. Vj Vk). (Если все A [k] отмечены, то длина пути от Vi до Vk равна B [k]. Теперь надо) перечислить вершины, входящие в кратчайший путь).
3. (выдача ответа). (Путь от Vi до Vk выдается в обратном порядке следующей процедурой:)
1. z: =C [k];
2. Выдать z;
3. z: =C [z]. Если z = О, то конец, иначе перейти к 3.2.
Для выполнения алгоритма нужно N раз просмотреть массив B из N элементов, т.е. алгоритм Дейкстры имеет квадратичную сложность: O (n2).
Ниже приведена блок-схема алгоритма Дейкстры (см. рис.2).
Рис.2. Блок-схема алгоритма Дейкстры
В начале алгоритма расстояние для начальной вершины полагается равным нулю, а все остальные расстояния заполняются большим положительным числом (бомльшим максимального возможного пути в графе). Массив флагов заполняется нулями. Затем запускается основной цикл.
На каждом шаге цикла мы ищем вершину с минимальным расстоянием и флагом равным нулю. Затем мы устанавливаем в ней флаг в 1 и проверяем все соседние с ней вершины. Если в ней расстояние больше, чем сумма расстояния до текущей вершины и длины ребра, то уменьшаем его. Цикл завершается когда флаги всех вершин становятся равны 1.
Псевдокод алгоритма Дейкстры
Обозначения
V - множество вершин графа
E - множество ребер графа
w [ij] - вес (длина) ребра ij
a - вершина, расстояния от которой ищутся
U - множество посещенных вершин
d [u] - по окончании работы алгоритма равно длине кратчайшего пути из a до вершины u
p [u] - по окончании работы алгоритма содержит кратчайший путь из a в u
Псевдокод (язык описания алгоритма)
Присвоим
Для всех отличных от a
присвоим
Пока
Пусть - вершина с минимальным d [v]
Для всех таких, что
если d [u] > d [v] + w [vu] то
изменим
изменим
Доказательство корректности
Пусть l (v) - длина кратчайшего пути из вершины a в вершину v. Докажем по индукции, что в момент посещения любой вершины z, d (z) =l (z).
База. Первой посещается вершина a. В этот момент d (a) =l (a) =0.
алгоритм дейкстра граф эйлер
Шаг. Пускай мы выбрали для посещения вершину . Докажем, что в этот момент d (z) =l (z). Для начала отметим, что для любой вершины v, всегда выполняется (алгоритм не может найти путь короче, чем кратчайший из всех существующих). Пусть P - кратчайший путь из a в z, y - первая непосещённая вершина на P, x - предшествующая ей (следовательно, посещённая). Поскольку путь P кратчайший, его часть, ведущая из a через x в y, тоже кратчайшая, следовательно l (y) =l (x) +w (xy). По предположению индукции, в момент посещения вершины x выполнялось d (x) =l (x), следовательно, вершина y тогда получила метку не больше чем d (x) +w (xy) =l (x) +w (xy) =l (y). Следовательно, d (y) =l (y). С другой стороны, поскольку сейчас мы выбрали вершину z, её метка минимальна среди непосещённых, то есть . Комбинируя это с , имеем d (z) =l (z), что и требовалось доказать.
Поскольку алгоритм заканчивает работу, когда все вершины посещены, в этот момент d=l для всех вершин
Сложность работы алгоритма Дейкстры
Сложность алгоритма Дейкстры зависит от способа нахождения вершины v, а также способа хранения множества непосещенных вершин и способа обновления меток. Обозначим через n количество вершин, а через m - количество ребер в графе G.
В простейшем случае, когда для поиска вершины с минимальным d [v] просматривается все множество вершин, а для хранения величин d - массив, время работы алгоритма есть O (n2 + m). Основной цикл выполняется порядка n раз, в каждом из них на нахождение минимума тратится порядка n операций, плюс количество релаксаций (смен меток), которое не превосходит количества ребер в исходном графе.
Для разреженных графов (то есть таких, для которых m много меньше n2) непосещенные вершины можно хранить в двоичной куче, а в качестве ключа использовать значения d [i], тогда время извлечения вершины из U станет log n, при том, что время модификации d [i] возрастет до log n. Так как цикл выполняется порядка n раз, а количество релаксаций не больше m, скорость работы такой реализации O (n*log n + m*log n).
Если для хранения непосещенных вершин использовать фибоначчиеву кучу, для которой удаление происходит в среднем за O (log n), а уменьшение значения в среднем за O (1), то время работы алгоритма составит O (n*log n + m).
Решение задачи:
Условие задачи: Найти кратчайший путь от вершины 1 к вершине 6 следующего графа (рис.3):
Рис.3. Исходные данные
Решение: Каждой вершине графа сопоставим метку - минимальное известное расстояние от этой вершины до вершины 1. Метка самой вершины 1 полагается равной 0, метки остальных вершин - бесконечности. Это отражает то, что расстояния от вершины 1 до других вершин пока неизвестны. Все вершины графа помечаются как непосещённые.
Алгоритм работает пошагово - на каждом шаге он "посещает" одну вершину и пытается уменьшать метки.
На каждом шаге из ещё не посещённых вершин выбирается вершина u, имеющая минимальную метку. Мы рассматриваем всевозможные маршруты, в которых u является предпоследним пунктом.
Вершины, в которые ведут рёбра из u, назовем соседями этой вершины. Для каждого непосещённого соседа вершины u рассмотрим новую длину пути, равную сумме значений текущей метки u и длины ребра, соединяющего u с этим соседом. Если полученное значение длины меньше значения метки соседа, заменим значение метки полученным значением длины. Рассмотрев всех соседей, пометим вершину u как посещенную и повторим шаг алгоритма.
Шаг 1. (см. рис.4) Минимальную метку имеет вершина 1. Её соседями являются вершины 2 и 3.
Первый по очереди сосед вершины 1 - вершина 2, потому что длина пути до неё минимальна. Длина пути в неё через вершину 1 равна сумме кратчайшего расстояния до вершины 1, т. е значение её метки, и длины ребра, идущего из 1-ой в 2-ую, то есть 0 + 3 = 3. Это меньше текущей метки вершины 2, бесконечности, поэтому новая метка 2-й вершины равна 3.
Аналогичным образом получаем новую метку 3-й вершины, равную 4.
Все соседи вершины 1 проверены. Текущее минимальное расстояние до вершины 1 считается окончательным и пересмотру не подлежит (то, что это действительно так, впервые доказал Э. Дейкстра).
Вычеркнем её из графа, чтобы отметить, что эта вершина посещена.
Рис.4. Шаг 1.
Шаг 2. (см. рис.5) Ближайшей из непосещенных вершин является вершина 2 с меткой 3. Снова пытаемся уменьшить метки соседей выбранной вершины, пытаясь пройти в них через 2-ю вершину.
Соседями вершины 2 являются вершины 1 и 4. Вершина 1 уже посещена. Рассмотрим вершину 4. Если идти в неё через 2, то длина такого пути будет равна 3 + 5 = 8. Присваиваем ей метку 8.
Помечаем вершину 2 как посещенную.
Размещено на http://www.allbest.ru/
Рис.5. Шаг 2.
Шаг 3. (см. рис.6) Рассмотрим вершину 3. Ее соседями являются вершины 1, 4 и 5.
Вершина 1 уже посещена.
Следующий сосед вершины 3 - вершина 4, так имеет минимальную метку из непосещённых вершин. Если идти в неё через 3, то длина такого пути будет равна 4 + 2 = 6. Это значение меньше текущей метки, поэтому меняем метку четвертой вершины на 6.
Рассмотрим вершину 5. Если идти в неё через 3, то длина такого пути будет равна 4 + 3 = 7. Присваиваем ей метку 7. Пометим стрелкой путь от вершины 1 к вершине 4 наименьшей длины.
Помечаем вершину 3 как посещенную.
Рис.6. Шаг 3
Шаг 4. (см. рис.7) Рассмотрим вершину 4. Ее соседями являются вершины 2, 3, 5 и 6.
Вершины 2 и 3 уже посещены.
Рассмотрим вершину 5. Если идти в неё через 4, то длина такого пути будет равна 6 + 6 = 12. Но это значение больше текущей метки, поэтому метку вершины 5 не меняем. Пометим стрелкой путь от вершины 1 к вершине 5 наименьшей длины.
Рассмотрим вершину 6. Если идти в неё через 4, то длина такого пути будет равна 6 + 8 = 14. Присваиваем ей метку 14.
Помечаем вершину 4 как посещенную.
Рис.7. Шаг 4
Шаг 5. (см. рис.8) Рассмотрим вершину 5. Ее соседями являются вершины 3, 4 и 6.
Вершины 3 и 4 уже посещены.
Рассмотрим вершину 6. Если идти в неё через 5, то длина такого пути будет равна 7 + 9 = 16 < 14, значит, метку вершины 6 не меняем. Пометим стрелкой путь от вершины 1 к вершине 6 наименьшей длины.
Помечаем вершину 5 как посещенную.
Рис.8. Шаг 5.
У целевой вершины 6 не осталось непосещенных соседей. Алгоритм закончен.
Ответ: Кратчайший путь от вершины 1 к вершине 6: 1-3-4-6, его длина 14.
Список используемой литературы
1. Ананий В. Левитин Глава 9. Жадные методы: Алгоритм Дейкстры // Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Aigorithms. - М.: "Вильямс", 2006. - С.189-195.
2. Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ = Introduction to Algorithms. - 2-е изд. - М.: "Вильямс", 2006. - С.1296.
3. Кузнецов А.В., Сакович В.А., Холод Н.И. ”Высшая математика. Математическое программирование", Минск, Вышейшая школа, 2001г.
4. Красс М.С., Чупрынов Б.П. ”Основы математики и ее приложения в экономическом образовании”, Издательство “Дело”, Москва 2001г.
5. В.И. Ермаков “Общий курс высшей математики для экономистов”, Москва, Инфра-М, 2000г.
6. Белов Теория Графов, Москва, "Наука", 1968.
7. Нефедов В.Н., Осипова В.А. Курс дискретной математики. - М.: Издательство МАИ, 1992.
8. Оре О. Теория графов. - М.: Наука, 1980.
9. Исмагилов Р.С., Калинкин А.В. Материалы к практическим занятиям по курсу: Дискретная математика по теме: Алгоритмы на графах. - М.: МГТУ, 1995
10. Смольяков Э.Р. Введение в теорию графов. М.: МГТУ, 1992
11. Дейкстра Э. Дисциплина программирования = A discipline of programming. - 1-е изд. - М.: Мир, 1978. - С.275.
12. Дал У., Дейкстра Э., Хоор К. Структурное программирование = Structured Programming. - 1-е изд. - М.: Мир, 1975. - С.247.
13. E. W. Dijkstra. A note on two problems in connexion with graphs. // Numerische Mathematik. V.1 (1959), P.269-271
Размещено на Allbest.ru
Подобные документы
Описание заданного графа множествами вершин V и дуг X, списками смежности, матрицей инцидентности и смежности. Матрица весов соответствующего неориентированного графа. Определение дерева кратчайших путей по алгоритму Дейкстры. Поиск деревьев на графе.
курсовая работа [625,4 K], добавлен 30.09.2014Общее понятие, основные свойства и закономерности графов. Задача о Кенигсбергских мостах. Свойства отношения достижимости в графах. Связность и компонента связности графов. Соотношение между количеством вершин связного плоского графа, формула Эйлера.
презентация [150,3 K], добавлен 16.01.2015Основные понятия теории графов. Содержание метода Дейкстры нахождения расстояния от источника до всех остальных вершин в графе с неотрицательными весами дуг. Программная реализация исследуемого алгоритма. Построение матриц смежности и инцидентности.
курсовая работа [228,5 K], добавлен 30.01.2012История возникновения, основные понятия графа и их пояснение на примере. Графический или геометрический способ задания графов, понятие смежности и инцидентности. Элементы графа: висячая и изолированная вершины. Применение графов в повседневной жизни.
курсовая работа [636,2 K], добавлен 20.12.2015Основные понятия теории графов. Расстояния в графах, диаметр, радиус и центр. Применение графов в практической деятельности человека. Определение кратчайших маршрутов. Эйлеровы и гамильтоновы графы. Элементы теории графов на факультативных занятиях.
дипломная работа [145,5 K], добавлен 19.07.2011Общая характеристика графов с нестандартными достижимостями, их применение. Особенности задания, представления и разработки алгоритмов решения задач на таких графах. Описание нового класса динамических графов, программной реализации полученных алгоритмов.
реферат [220,4 K], добавлен 22.11.2010Основные понятия и свойства эйлеровых и гамильтоновых цепей и циклов в теории графов. Изучение алгоритма Дейкстры и Флойда для нахождения кратчайших путей в графе. Оценки для числа ребер с компонентами связанности. Головоломка "Кенигзберзьких мостов".
курсовая работа [2,4 M], добавлен 08.10.2014Основные понятия теории графов. Маршруты и связность. Задача о кёнигсбергских мостах. Эйлеровы графы. Оценка числа эйлеровых графов. Алгоритм построения эйлеровой цепи в данном эйлеровом графе. Практическое применение теории графов в науке.
курсовая работа [1006,8 K], добавлен 23.12.2007Спектральная теория графов. Теоремы теории матриц и их применение к исследованию спектров графов. Определение и спектр предфрактального фрактального графов с затравкой регулярной степени. Связи между спектральными и структурными свойствами графов.
дипломная работа [272,5 K], добавлен 05.06.2014Понятие и содержание теории графов. Правила построения сетевых графиков и требования к ним. Сетевое планирование в условиях неопределенности. Теория принятия решений, используемые алгоритмы и основные принципы. Пример применения алгоритма Дейкстры.
курсовая работа [1,0 M], добавлен 26.09.2013
