Нахождение кратчайших путей в графе

Содержание

 

Введение. 3

Алгоритмы на графах. 6

1. Основные понятия. 6

2. Способы задания графа. 8

3. Нахождение кратчайших путей в графе. 9

Алгоритм Дейкстры.. 10

Схема алгоритма Дейкстры.. 11

4. Нахождение остовного дерева минимального веса. 12

Алгоритм Прима-Краскала. 14

5. Алгоритм Прима-Краскала. Решение задач. 16

Заключение. 21

Литература. 24

Приложение. 25

1. Листинг программы: 25

2. Блок-схема алгоритма. 26

Введение

Теория графов – это область дискретной математики, особенностью которой является геометрический подход к изучению объектов. Теория графов находится сейчас в самом расцвете. Обычно её относят к топологии (во многих случаях рассматриваются лишь топологические свойства графов), однако она пересекается со многими разделами теории множеств, комбинаторной математики, алгебры, геометрии, теории матриц, теории игр, математической логики и многих других математических дисциплин. Основной объект теории графов-граф и его обобщения. Первые задачи теории графов были связаны с решением математических развлекательных задач и головоломок. Одним из первых результатов в теории графов явился критерий существования обхода всех ребер графа без повторений, полученный Л. Эйлером при решении задачи о Кенигсбергских мостах. Существует еще один вид задач, связанных с путешествиями вдоль графов. Речь идёт о задачах, в которых требуется отыскать путь, проходящий через все вершины, причем не более одного раза через каждую. Цикл, проходящий через каждую вершину один и только один раз, носит название гамильтоновой линии. К сожалению, пока еще не найден общий критерий, с помощью которого можно было бы решить, является ли данный граф гамильтоновым, и если да, то найти на нём все гамильтоновы линии. Сформулированная в середине 19 в. проблема четырех красок также выглядит как развлекательная задача, однако попытки ее решения привели к появлению некоторых исследований графов, имеющих теоретическое и прикладное значение. Проблема четырех красок формулируется так: ”Можно ли область любой плоской карты раскрасить четырьмя цветами так, чтобы любые две соседние области были раскрашены в различные цвета?”. Гипотеза о том, что ответ утвердительный, была сформулирована в середине 19 в. В 1890 году было доказано более слабое утверждение, а именно, что любая плоская карта раскрашивается в пять цветов. Многочисленные попытки решения задачи оказали влияние на развитие ряда направлений теории графов. В 1976 году анонсировано положительное решение задачи с использованием ЭВМ. Другая старая топологическая задача, которая особенно долго не поддавалась решению и будоражила умы любителей головоломок, известна как “задача об электро-, газо- и водоснабжении”. В 1917 году Генри Э.Дьюдени дал ей такую формулировку. В каждый из трёх домов, изображенных на рисунке, необходимо провести газ, свет и воду. Свет вода газ Можно ли так проложить коммуникации, чтобы они, нигде не пересекаясь друг с другом, соединяли каждый дом с источниками электричества, газа и воды? Оказывается нельзя. В середине 19 в. появились работы, в которых при решении практических задач были получены результаты, относящиеся к теории графов. Так, например, Г. Кирхгоф при составлении полной системы уравнений для токов и напряжений в электрической схеме предложил по существу представлять такую схему графом и находить в этом графе остовные деревья, с помощью которых выделяются линейно независимые системы контуров. А. Кэли, исходя из задач подсчета числа изомеров предельных углеводородов, пришел к задачам перечисления и описания деревьев, обладающих заданными свойствами, и решил некоторые из них. В начале 20 в. графы стали использоваться для представления некоторых математических объектов и формальной постановки различных дискретных задач; при этом наряду с термином «граф» употреблялись и другие термины, например, карта, комплекс, диаграмма, сеть, лабиринт. После выхода в свет в 1936 году монографии Д. Кёнига термин «граф» стал более употребительным, чем другие. В этой работе были систематизированы известные к тому времени факты. В 1936 году вышла небольшая брошюра Ойстена Оре, содержащая блестящее элементарное введение в теорию графов. В 1962 году в Англии была издана книга французского математика Клода Бержа “Теория графов и её приложение”. Обе книги, безусловно, представляют интерес для любителей занимательной математики. Сотни известных головоломок, на первый взгляд не имеющих ничего общего друг с другом, легко решаются с помощью теории графов. В 20-30-х годах 20 в. появились первые результаты, относящиеся к изучению свойств связности, планарности, симметрии графов, которые привели к формированию ряда новых направлений в теории графов. Значительно расширились исследования по теории графов в конце 40-х – начале 50-х годов, прежде всего в силу развития кибернетики и вычислительной техники. Благодаря развитию вычислительной техники, изучению сложных кибернетических систем, интерес к теории графов возрос, а проблематика теории графов существенным образом обогатилась. Кроме того, использование ЭВМ позволило решать возникающие на практике конкретные задачи, связанные с большим объемом вычислений, прежде не поддававшиеся решению. Для ряда экстремальных задач теории графов были разработаны методы их решения, например, один из таких методов позволяет решать задачи о построении максимального потока через сеть.Для отдельных классов графов (деревья, плоские графы и т. д.), которые изучались и ранее, было показано, что решения некоторых задач для графов из этих классов находятся проще, чем для произвольных графов. В теории графов существуют специфические методы решения экстремальных задач. Один из них основан на теореме о максимальном потоке и минимальном разрезе, утверждающей, что максимальный поток, который можно пропустить через сеть из вершины U в вершину V, равен минимальной пропускной способности разрезов, разделяющих вершины U и V. Были построены различные эффективные алгоритмы нахождения максимального потока. Большое значение в теории графов имеют алгоритмические вопросы. Для конечных графов, т. е. для графов с конечным множеством вершин и ребер, как правило, проблема существования алгоритма решения задач, в том числе экстремальных, решается положительно. Решение многих задач, связанных с конечными графами, может быть выполнено с помощью полного перебора всех допустимых вариантов. Однако таким способом удается решить задачу только для графов с небольшим числом вершин и ребер. Поэтому существенное значение для теории графов имеет построение эффективных алгоритмов, находящих точное или приближенное решение. Для некоторых задач такие алгоритмы построены, например, для установления планарности графов, определения изоморфизма деревьев, нахождения максимального потока. Результаты и методы теории графов применяются при решении транспортных задач о перевозках, для нахождения оптимальных решений задачи о назначениях, для выделения «узких мест» при планировании и управлении разработок проектов, при составлении оптимальных маршрутов доставки грузов, а также при моделировании сложных технология, процессов, в построении различных дискретных устройств, в программировании и т. д. За последние десять – двадцать лет теория графов вступила в новый период интенсивных разработок. В этом процессе явно заметно влияние запросов новых областей: теории игр и программирования, теории передачи сообщений, электрических сетей и контактных цепей, а также проблем психологии и биологии.

Алгоритмы на графах

Основные понятия

Граф G (рис.1) задается множеством точек (вершин) х₁, х₂,..., х_n. (которое обозначается через Х) и множеством линий (ребер) а₁, а₂,...,а_m. (которое обозначается символом А), соединяющих между собой все или часть этих точек. Таким образом, граф G полностью задается (и обозначается) парой (Х, А).

Если ребра из множества А ориентированы, что обычно показывается стрелкой, то они называются дугами, и граф с такими ребрами называется ориентированным графом, (рис.2).

Например, если дорога имеет не двух-, а одностороннее движение то направление этого движения будет показано стрелкой.

Если ребра не имеют ориентации, то граф называется неориентированным (рис 3).

В ориентированном графе дуга обозначается упорядоченной парой, состоящей из начальной и конечной вершин (т.е. двумя концевыми вершинами дуги), ее направление предполагается заданным от первой вершины ко второй. Так, например, на рис. 2 обозначение (х₁ ,х₃) относится к дуге а₁.

Другое, употребляемое чаще описание ориентированного графа G состоит в задании множества вершин Х и соответствия Г, которое показывает, как между собой связаны вершины. Соответствие Г называется отображением множества Х в Х, а граф в этом случае обозначается парой G=(Х, Г). Так, например, для графа на рис. 2:

Г (х₁)={х₂, х₃}, т.е. вершины х₂ и х₃ являются конечными вершинами дуг, у которых начальной вершиной является вершина х₁.

На рис. 3: Г (х₁)={х₂, х₄, х₅}, (неориентированное ребро представляется как две противоположно направленные дуги, соединяющие те же самые вершины.)

Путем (или ориентированным маршрутом) ориентированного графа называется последовательность дуг, в которой конечная вершина всякой дуги, отличной от последней, является начальной вершиной следующей.

Так, на рис. 5 последовательности дуг

а₆, а₅, а₉, а₈, а₄. (1)

а₁, а₆, а₅, а₉. (2)

а₁, а₆, а₅, а₉, а₁₀, а₆, а₄. (3)

являются путями.

Ориентированной цепью (орцепью) называется такой путь, в котором каждая дуга используется не больше одного раза. Так, например приведенные выше пути (1) и (2) являются орцепями, а путь (3) не является таким, т.к. дуга а₆ в нем используется дважды.

Простой орцепью называется такой путь, в котором каждая вершина используется не более одного раза. Например, путь (2) является простой орцепью, а пути (1) и (3) – нет.

Маршрут есть неориентированный “двойник” пути, и это понятие рассматривается в тех случаях, когда можно пренебречь направленностью дуг в графе. Таким образом, маршрут есть последовательность ребер а₁, а₂,..., а_q, в которой каждое ребро а_q за исключением первого и последнего ребер, связано с ребрами а_i-1 и а_i+1 своими концевыми вершинами. Последовательности дуг:

а₂, а₄, а₈, а₁₀, (4)

а₂, а₇, а₈, а₄, а₃, (5)

а₁₀ , а₇ , а₄ , а₈ , а₇ , а₂. (6)

в графе, изображенном на рис. 5, являются маршрутами; две точки над символом дуги означают, что ее ориентацией пренебрегают, т.е. дуга рассматривается как неориентированное ребро. Также путь или маршрут можно изображать последовательностью вершин. Например, путь (1) будет выглядеть следующем образом: х₂, х₅, х₄, х₃, х₅, х₆.

Иногда дугам графа приписываются числа, называемые весом, стоимостью, или длиной этой дуги. В этом случае граф называется графом со взвешенными дугами. А если вес приписывается вершинам графа, то тогда получается граф со взвешенными вершинами. Если в графе веса приписаны и дугам и вершинам, то он называется просто взвешенным.

Связный граф без циклов называется деревом. Деревья особенно часто возникают на практике при изображении различных иерархий. Например, популярные генеалогические деревья. Пример – генеалогическое дерево. Эквивалентные определения дерева. 1. Связный граф называется деревом, если он не имеет циклов. 2. Содержит N-1 ребро и не имеет циклов. 3. Связный и содержит N-1 ребро. 4. Связный и удаление одного любого ребра делает его несвязным.5. Любая пара вершин соединяется единственной цепью. 6. Не имеет циклов и добавление одного ребра между любыми двумя вершинами приводит к появлению одного и только одного цикла.

2. Способы задания графа

1. Геометрический: 2. Матрицей смежности:

	A	В	C	D
A	0	1	1	0
B	1	0	1	0
C	1	1	0	1
D	0	0	1	0

Матрица смежности – квадратная матрица, размерности, равной количеству вершин. При этом а[ i, j ] – целое число, равное количеству рёбер, связывающих i-ю, j-ю вершину. Если в графе нет петель, то диагональные элементы равны 0. Если рёбра не повторяются, то все элементы 0 или 1. Если граф неориентированный, то матрица симметрична. 3. Матрица инцидентности:

	А	В	С	D
A	1	1	0	0
B	0	1	1	0
C	1	0	1	0
D	0	0	1	1

4. Явное задание графа как алгебраической системы: <{a,b,c,d},{u,v,w,x}; {(u,a),(u,b),(v,b),(v,c),(w,c),(w,a),(x,c), (x,d)}>. Так как к рассмотрению приняты только простые графы, граф проще определять как модель, носителем которой является множество вершин, а отношение – бинарное отношение смежности вершин. Тогда данный граф запишется как <{a,b,c,d }; {(a,b), (b,a),(b,c),(c,b),(a,c),( c,a),(c,d),(d,c)}>. В таком представлении ребру соответствуют две пары вершин (v₁,v₂) и ( v₂,v₁), инцидентных данному ребру. Чтобы задать такое представление, достаточно для каждого ребра указать двухэлементное множество вершин – его отождествляют с ребром. Для данного графа рёбра задаются множеством {{a,b},{b,c},{a,c},{c,d}} и граф можно записать как пару (V,E), где V – множество вершин, а E – множество рёбер. 5. Задание графа посредством списков. Например, списком пар вершин, соединенных ребрами (или дугами) или  списком списков для каждой вершины множества смежных с ней вершин.

 

Нахождение кратчайших путей в графе

Пусть дан граф G=(Х, Г), дугам которого приписаны веса (стоимости/длины), задаваемые матрицей С=[c_ij].

Задача о кратчайшем пути состоит в нахождении кратчайшего пути от заданной начальной вершины s x до заданной конечной вершины t x, при условии, что такой путь существует t R(s) (здесь R(s) ­ множество, достижимое из вершины s) и все циклы в графе имеют неотрицательный суммарный вес. Так как если в графе будет присутствовать цикл с отрицательным суммарным весом и х_i- некоторая его вершина, то, двигаясь от s к х_i, обходя этот цикл достаточно большое число раз и попадая, наконец в t, получится путь со сколь угодно малым ( ) весом. Таким образом, в этом случае кратчайшего пути не существует. Так что неориентированные дуги (ребра) графа G не могут иметь отрицательные веса.

Существуют задачи, являющиеся непосредственными обобщениями сформулированной выше задачи о кратчайшем пути.

1) Для заданной начальной вершины s найти кратчайшие пути между s и всеми другими вершинами х_i X.

2) Найти кратчайшие пути между всеми парами вершин.

Почти все методы, позволяющие решить задачу о кратчайшем (s-t)-пути, дают также (в процессе решения) и все кратчайшие пути от s к х_i. Таким образом, они позволяют решить задачу с небольшими дополнительными вычислительными затратами.

С другой стороны, задача №1 может быть решена либо n-кратным применением алгоритма задачи №2, причем на каждом шаге в качестве начальной вершины s берутся различные вершины, либо однократным применением специального алгоритма.

Наиболее распространенные методы их решения задач – это использование алгоритма Дейкстры (для нахождения кратчайшего пути между двумя вершинами), алгоритма Флойда (для нахождения кратчайших путей между всеми парами вершин) и алгоритма Йена (для нахождения k – кратчайших путей в графе).

Если требуется найти кратчайший путь во взвешенном графе, где pебpам приписаны вещественные числа – веса, и эти веса неотрицательны, можно использовать алгоритм Дейкстpы. При наличии ребер с отрицательным весом кратчайший путь может не существовать даже для связного графа. Кратчайший путь существует, только если в графе нет циклов отрицательного сyммаpного веса – по такому циклу можно кpyтиться сколько угодно, уменьшая длину до бесконечности. Для общего случая подходит алгоритм Флойда, который позволяет либо найти кратчайшие пути, либо обнаружить циклы отрицательной длины.

Упомянутые алгоритмы являются классическими и описаны в различных книгах по теории графов (напp. [1]). Существyет огромное количество дpyгих алгоритмов, более выгодных в каких-то случаях.

 

Алгоритм Дейкстры

Пусть необходимо лететь с одной пересадкой, причем сначала самолетом компании A, а затем – компании B. Сколько придется заплатить пассажиру, чтобы попасть из города i в город j?

Известно, что все цены неотрицательны. Найти наименьшую стоимость проезда 1  i для всех i=1..n за время O(n²).

В процессе работы алгоритма некоторые города будут выделенными (в начале – только город 1, в конце – все).

При этом:

1. для каждого выделенного города i хранится наименьшая стоимость пути 1  i; при этом известно, что минимум достигается на пути, проходящем только через выделенные города;

2. для каждого невыделенного города i хранится наименьшая стоимость пути 1  i, в котором в качестве промежуточных используются только выделенные города.

Множество выделенных городов расширяется на основании следующего замечания: если среди всех невыделенных городов взять тот, для которого хранимое число минимально, то это число является истинной наименьшей стоимостью. В самом деле, пусть есть более короткий путь. Рассмотрев первый невыделенный город на этом пути – уже до него путь длиннее. Существенно требование неотрицательности цен.

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

При самом бесхитростном способе хранения множества выделенных городов (в булевском векторе) добавление одного города к числу выделенных требует времени O(n).