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

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

В этой лекции рассматриваются связные графы с неотрицательными весами ребер. Вес пути в графе определяется как сумма весов ребер этого пути. Кратчайшим путем между двумя вершинами называется путь наименьшего веса, соединяющий эти вершины. Рассмотрим задачу отыскания кратчайших путей от заданной вершины \[ 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 \] .

1. cоздать дерево \[ T \] из одной вершины \[ a \]
2. \[ \delta (a):=0 \]
3. \[ A:=\{ a\} \]
4. while \[ A\ne V \] do
5. cреди ребер \[ (x,y) \] , где \[ x\in A \] , \[ y\in \overline{A} \] , найти ребро \[ (x_{0},y_{0}) \] c наименьшим значением величины \[ \delta (x)+w(x,y) \] ;
6. добавить к дереву \[ T \] вершину \[ y_{0} \] и ребро \[ (x_{0},y_{0}) \] ;
7. \[ \delta (y_{0} ):=\delta (x_{0} )+w(x_{0},y_{0}) \]

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