Пример, иллюстрирующий работу алгоритма Дейкстры

В данной задаче показана работа алгоритма Дейкстры на примере, изображенном на рисунке.

Задача.

Найти кратчайший путь от узла 1 к узлу 5 для сети следующего вида:

Представим данную сеть в следующем виде:

Узел s здесь является источником, t — стоком, а числа , приписан­ные дугам, соответствуют их длине или стоимости.

Работа алгоритма начинается с того, что источнику 5 при­писывается постоянная пометка , а узлам , t - временные пометки . Таким образом, и . Поскольку значение является минимальным среди всех временных пометок, узлу 1 приписывается постоянная пометка .

Узлы 2 и 3 непосредственно связаны с узлом 1, последним из постоянно помеченных узлов. Отметим, что и . Поэтому узлам 2 и 3 приписываются новые временные пометки и соответственно. Поскольку , узлу 2 приписывается постоянная пометка = .

Узлы 3 и 6 непосредственно связаны с узлом 2. Кроме того, и . Поэтому узлам 3 и 6 приписываются новые временные пометки и соответственно. Поскольку , узел 6 становится помеченным постоянно, т. е. = .

На данном шаге временными являются пометки и . Последним узлом, которому была приписана постоянная пометка, является узел 6. Он непосредственно связан только с узлом 4. Отметим, что . Следовательно, узлу 4 приписывается новая временная помет­ка . Поскольку , узлу 3 приписывается постоянная пометка = . Аналогично проведем дальнейшие вычисления. Алгоритм заканчивает работу, когда узлу t приписывается постоянная пометка. Промежуточные результаты, полученные при решении данной задачи, приводят­ся в таблице.

Таблица

Дата добавления: 2014-01-07