Кратчайшие пути

Кратчайшие пути

В этой лекции рассматриваются связные графы с неотрицательными весами ребер. Вес пути в графе определяется как сумма весов ребер этого пути. Кратчайшим путем между двумя вершинами называется путь наименьшего веса, соединяющий эти вершины. Рассмотрим задачу отыскания кратчайших путей от заданной вершины $$a$$ до всех остальных вершин графа. Возможно, более естественной постановкой задачи кажется поиск кратчайшего пути между двумя заданными вершинами. Однако в настоящее время не известно никакого способа решения этой задачи, существенно лучшего, чем поиск кратчайших путей от начальной вершины до всех остальных.

Геодезическое дерево

Пусть $$a$$ - вершина связного графа $$G$$ с заданной на множестве ребер весовой функцией $$w$$ с неотрицательными значениями. Каркас $$T$$ графа $$G$$ с корнем $$a$$ называется геодезическим деревом, если для любой вершины $$x$$ путь между вершинами $$x$$ и $$a$$ в дереве $$T$$ является кратчайшим путем между этими вершинами в графе $$G$$. Это обобщает понятие геодезического дерева, введенное в лекции 4 и соответствующее случаю, когда все веса равны 1. Докажем сначала, что геодезическое дерево всегда существует.

Обозначим через $$\delta (x)$$ вес кратчайшего пути между вершинами $$x$$ и $$a$$ в графе $$G$$. Дерево $$F$$ с корнем $$a$$ назовем частичным геодезическим деревом, (ЧГД), если существует такое геодезическое дерево $$T_{0}$$ с корнем $$a$$, что $$F$$ является подграфом дерева $$T_{0}$$. Иначе говоря, ЧГД - это корневое дерево, которое можно достроить до геодезического дерева с тем же корнем.

Пусть $$V$$ - множество всех вершин графа $$G$$. Для множества $$A\subseteq V$$ через $$\overline{A}$$ обозначаем дополнение $$A$$ до $$V$$.

Эта теорема показывает, что геодезическое дерево можно построить с помощью следующего алгоритма.

Алгоритм 1. Построение геодезического дерева для вершины $$a$$.

Этот алгоритм очень похож на алгоритм Прима для построения оптимального каркаса. Единственное отличие между ними состоит в правиле выбора ребра, присоединяемого к строящемуся дереву на очередном шаге. В алгоритме Прима выбирается ребро наименьшего веса, а в алгоритме для построения геодезического дерева - ребро с минимальным значением величины $$\delta (x)+w(x,y)$$. Ясно, что и оценка трудоемкости нового алгоритма будет такая же, как и для алгоритма Прима, то есть $$O(n^{3})$$. Подобно алгоритму Прима, этот алгоритм можно рационализировать, понизив тем самым оценку трудоемкости до $$O(n^{2})$$. Усовершенствованный алгоритм поиска кратчайших путей известен как алгоритм Дейкстры.

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

Допустим, на некотором шаге описанного выше алгоритма построено дерево с множеством вершин $$A$$, а для каждой вершины $$y\in \overline{A}$$ известна вершина $$x_{0} =F(y)$$, на которой достигается наименьшее значение величины $$\Delta(y)=\min\{\delta (x)+w(x,y)\}$$, где минимум берется по всем вершинам $$x\in A$$. Тогда на этом шаге следует выбрать вершину $$y\in \overline{A}$$ с наименьшим значением величины $$\Delta (y)$$ и присоединить к дереву ребро $$(F(y),y)$$. После этого для каждой вершины $$z$$, еще не принадлежащей к дереву, значения $$\Delta (z)$$ и $$F(z)$$ уточняются следующим образом: если $$\Delta (y)+w(y,z)< \Delta (z)$$, то следует положить $$F(z)=y$$, $$\Delta (z)=\Delta (y)+w(y,z)$$. Вершина $$F(y)$$ может рассматриваться как предполагаемый отец вершины $$y$$ в геодезическом дереве (если все множество $$\overline{A}$$ состояло бы из одной вершины $$y$$, то $$F(y)$$ была бы ее истинным отцом). Величина $$\Delta(y)$$ представляет собой оценку кратчайшего пути из $$a$$ в $$y$$, она равна весу кратчайшего из путей, проходящих только через вершины множества $$A$$. После того, как вершина $$y$$ присоединяется к дереву, значения $$F(y)$$ и $$\Delta(y)$$ больше не изменяются, $$F(y)$$ является отцом вершины $$y$$ в геодезическом дереве, а $$\Delta(y)=\delta (y)$$. В целом алгоритм можно представить следующим образом:

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