Навигация
2 ТЕОРЕТИЧЕСКАЯ ЧАСТЬ
2.1 Сведения о графах
Граф G (рис.2.1.1) задается множеством точек (вершин) х1, х2,..., хn. (которое обозначается через Х) и множеством линий (ребер) а1, а2,...,аm. (которое обозначается символом А), соединяющих между собой все или часть этих точек. Таким образом, граф G полностью задается (и обозначается) парой (Х, А). Если ребра из множества А ориентированы, что обычно показывается стрелкой, то они называются дугами, и граф с такими ребрами называется ориентированным графом.
|
|
Например, если дорога имеет не двух-, а одностороннее движение то направление этого движения будет показано стрелкой.
Если ребра не имеют ориентации, то граф называется неориентированным, (двухстороннее движение).
В ориентированном графе дуга обозначается упорядоченной парой, состоящей из начальной и конечной вершин, ее направление предполагается заданным от первой вершины ко второй.
Путем (или ориентированным маршрутом) ориентированного графа называется последовательность дуг, в которой конечная вершина всякой дуги, отличной от последней, является начальной вершиной следующей.
Так, на рис. 2.1.2 путями являются последовательности дуг:
а6, а5, а9, а8, а4. (1)
а1, а6, а5, а9. (2)
а1, а6, а5, а9, а10, а6, а4. (3)
Ориентированной цепью (орцепью) называется такой путь, в котором каждая дуга используется не больше одного раза.
Простой орцепью называется такой путь, в котором каждая вершина используется не более одного раза. Например, путь (2).
Маршрут есть неориентированный “двойник” пути, и это понятие рассматривается в тех случаях, когда можно пренебречь направленностью дуг в графе. Таким образом, маршрут есть последовательность ребер ä1, ä2,..., äq, в которой каждое ребро аi, за исключением первого и последнего ребер, связано с ребрами аi-1 и аi+1 своими концевыми вершинами. Последовательности дуг:
ä2, ä4, ä8, ä10, (4)
ä2, ä7, ä8, ä4, ä3, (5)
ä10 , ä7 , ä4 , ä8 , ä7 , ä2. (6)
в графе, изображенном на рис. 2.1.2, являются маршрутами; две точки над символом дуги означают, что ее ориентацией пренебрегают, т.е. дуга рассматривается как неориентированное ребро. Также путь или маршрут можно изображать последовательностью вершин. Например, путь (1) будет выглядеть следующем образом: х2, х5, х4, х3, х5, х6. Иногда дугам графа приписываются числа, называемые весом, стоимостью, или длиной этой дуги. В этом случае граф называется графом с взвешенными дугами. А если вес приписывается вершинам графа, то тогда получается граф с взвешенными вершинами. Если в графе веса приписаны и дугам и вершинам, то он называется просто взвешенным. При рассмотрении пути µ представленного последовательностью дуг (ä1, ä2,..., äq), за его вес принимается число l(µ), равное сумме весов всех дуг, входящих в µ, т.е.
2.2 Алгоритм Дейкстры
Алгоритм Дейкстры строит кратчайшие пути, ведущие из исходной вершины графа к остальным вершинам этого графа (если таковые имеются).
В процессе работы алгоритма последовательно помечаются рассмотренные вершины графа. Причем вершина, помеченная последней (на данный момент) расположена ближе к исходной вершине, чем все непомеченные, но дальше, чем все помеченные.
Сначала помечается исходная вершина; следующей, очевидно, будет помечена вершина, ближайшая к исходной, и смежная с ней.
Пусть на каком-то шаге уже помечено несколько вершин. Известны кратчайшие пути, ведущие из исходной вершины к помеченным. Для каждой из непомеченных вершин проделаем следующее:
1. Рассмотрим все дуги, ведущие из помеченных вершин в одну непомеченную. Каждая такая дуга является последней дугой на пути из исходной вершины в эту непомеченную.
2. Выберем из этих путей кратчайший. А затем выберем среди них самый короткий ко всем непомеченным вершинам, и пометим вершину, к которой он ведет.
Алгоритм завершится, когда будут помечены все достижимые вершины.
В результате работы алгоритма Дейкстры строится Дерево кратчайших путей.
Похожие работы
... подход к разработке эффективного алгоритма для решения любой задачи – изучить ее сущность. Довольно часто задачу можно сформулировать на языке теории множеств, относящейся к фундаментальным разделам математики. В этом случае алгоритм ее решения можно изложить в терминах основных операций над множествами. К таким задачам относятся и задачи информационного поиска, в которых решаются проблемы, ...
... образом. Пусть G=(V,E) in «D. Тогда множество вершин F(G) in «G совпадает с V, а множество дуг F(G) определяется применением следующих операций на E: a) удаляются все петли из Е; б) (v,w) заменяются на [v,w] для всех (v,w) in E. Тогда F(G) является графом, СВЯЗАННЫМ с орграфом G. Для орграфов понятие связности является более содержательным, чем для графов. Различают три важных типа связности ...
... же порты ввода-вывода или линии запроса прерывания. С такими проблемами, как конфликты различных частей аппаратуры, приходится иметь дело в основном именно операционным системам. Наконец, в-восьмых, при разработке операционных систем часто учитывается необходимость совместимости с предыдущей версией операционной системы. Система может иметь множество ограничений на длину слов, имена файлов и т. ...
0 комментариев