|
Алгоритмы\Алгоритм Дейкстры
Кратчайшие пути. Алгоритм Дейкстры
Дан орграф G=(V,E), всем дугам которого присвоен неотрицательный вес (хранится в двумерном массиве C, C[i,j] - вес дуги из i в j, C[i,j]=∞, если такой дуги нет), а также вершина v (источник). Наша задача - вычислить кратчайшие расстояния из источника до всех вершин (массив D; D[i] - кратчайший путь из v в i).
В ходе выполнения этого алгоритма формируется множество вершин S, для которых кратчайшие пути от источника уже известны, и на каждом шаге к S добавляется очередная вершина u, у которой среди еще неиспользованных вершин минимальное расстояние от источника.
После этого для каждой вершины i, не принадлежащей S, проверяется является ли путь из v в i короче, чем путь из v в u + C[u,i], если нет, то оценка кратчайшего расстояния изменяется на меньшую:
D[i]:=min(D[i],D[u]+C[u,i])
Затем выбирается новая вершина u и действия повторяются до тех пор, пока все вершины будут принадлежать множеству S. Массив D в этом случае будет содержать искомые расстояния.
Заметим, что вышеописанный алгоритм неприменим к орграфам с отрицательными весами дуг. Например, для графа на рисунке кратчайшее расстояние из 1 в 2 равно 0 (но не 1!).
Скачать исходник (Pascal)
© JlC, 2005
|
