Опишем алгоритм нахождения такого пути при условии, что длины всех дуг неотрицательны. Этот алгоритм был предложен и опубликован Э. Дейкстрой (Е. W. Dijkstra), поэтому и носит его имя.
Алгоритм поиска кратчайшего пути в этом случае несколько напоминает алгоритм обхода графа в ширину и состоит в следующем. Будем рассматривать два множества: множество вершин, для которых уже известен кратчайший путь до них из начальной вершины (passed), и множество еще не исследованных вершин (notPassed).
В начале работы первое множество будет пустым, а второе будет содержать все вершины графа. На каждом шаге работы алгоритма из второго множества в первое переводится одна вершина — та, расстояние до которой от исходной вершины минимально. Эту вершину будем называть пограничной (border).
Для определения пограничной вершины во время работы алгоритма постоянно корректируется массив расстояний dist, в котором для каждой вершины хранится расстояние до нее от исходной вершины, если оно известно. В начале работы алгоритма расстояние известно только для одной вершины — начальной. Конечно, это расстояние равно нулю, так что эта вершина и будет выбрана первой в качестве пограничной. В дальнейшем массив будет корректироваться за счет просмотра вершин-кандидатов, в которые ведут дуги из очередной пограничной вершины в еще не просмотренные вершины.
Сам путь из начальной вершины в конечную будет сохраняться с помощью массива меток backs. Алгоритм заканчивает работу, как только в качестве пограничной будет выбрана конечная вершина или, если окажется, что очередная пограничная вершина вообще не связана с начальной (находится на бесконечно большом расстоянии от нее). Это расстояние задается в программе константой infinity.
Реализация этого алгоритма приведена в листинге в виде метода getDijkstraPath класса ListGraph. В качестве аргументов методу передаются номера начальной и конечной вершин на кратчайшем пути, а также переменная, которая будет содержать вектор номеров промежуточных вершин на пути из начальной вершины в конечную. Результатом работы метода будет суммарная длина кратчайшего пути.
Чтобы задать нагрузку на дуги, не изменяя представления графа, введем специальный абстрактный тип данных Graphweight, представляющий объекты, задающие нагрузку на дуги графа. Главным методом соответствующего класса будет функция arcLength, которая по заданным номерам вершин определяет длину дуги, соединяющей эти вершины. Значение функции будем считать неопределенным, если заданные вершины не соединены никакой дугой или вообще не задают номеров вершин графа. Чтобы задать конкретную нагрузку на граф, необходимо определить реализацию абстрактного типа данных GraphWeight.
Листинг : Алгоритм определения кратчайшего пути Э. Дейкстры с учетом длин дуг
double ListGraph: :getDijkstraPath (int beg, int end,
const GraphWeight & weights, vector<int> & path) const
{
path.clear();
// Множество непросмотренных вершин:
Set notPassed(0, vertexCount()-1);
notPassed.addScale(0, vertexCount()-1);
// Массив обратных меток
int *backs = new int[vertexCount()];
// Массив минимальных расстояний. В начале работы все расстояния
// бесконечно большие, кроме расстояния до исходной вершины
double *dist = new double[vertexCount()];
for (int i = 0; i < vertexCount(); i++)
dist[i] = INFINITY;
dist[beg] = 0;
// Цикл поиска и обработки пограничной вершины
while(!notPassed.empty())
{
// Поиск пограничной вершины: просматриваем массив dist
// в поисках вершины с минимальным расстоянием от beg
int border = -1;
double minDist = INFINITY;
Iterator<int> *check = notPassed.iterator();
while(check->hasMoreElements()) {
int next = **check;
if (dist[next] < minDist) { minDist = dist[border = next];
}
++*check;
}
delete check;
// Если пограничная вершина не найдена, то пути нет
if (border == -1) return INFINITY;
// Если пограничная вершина совпала с конечной,
// то переходим к формированию результата
if (border == end) break;
// Обработка вершин, смежных с пограничной
notPassed -= border;
Iterator<int> *nextToBorder = graph[border].iterator();
while (nextToBorder->hasMoreElements())
{
int v = **nextToBorder;
if (notPassed.has(v) && dist[v] >
dist[border] + weights.arcLength(border, v)) {
backs[v] = border;
dist[v] = dist[border] + weights.arcLength(border, v);
}
++*nextToBorder;
}
delete nextToBorder;
}
// Формирование результирующего вектора
int current = end;
while(current != beg) {
path.insert(path.begin(), current);
current = backs[current];
}
path.insert(path.begin(), beg);
return dist[end];
}