Главная|Решения онлайн |Теория | Основные формулы и обозначения |Обратная связь |


Алгоритм Данцига

Этот алгоритм  отличается от алгоритма Флойда последовательностью выполнения действий. Перенумеруем все вершины графа от 1 до n целыми числами и обозначим через di,jm длину пройденного пути из i в j где в качестве промежуточных использованы первые m вершин графа. Матрица Dm длин кратчайших путей имеет здесь размерность m*m.


1. Каждая вычисленная матрица Dm содержит на одну строку и столбец больше чем ее предшественница. Элементы матрицы не входящие в последнюю строку или столбец вычисляются так же, как и в алгоритме Флойда.

di,jm=min{ di,mm-1+ dm,jm-1; di,jm-1(1)

2. Кратчайший путь из вершины m в j, в котором допускаются первые m промежуточных вершин, должен иметь в своей первой части дугу из вершины m в некоторую вершину k, a во второй – кратчайший путь из вершины k в j .

dm,jm=min{d0m,k+ dm-1k,j} k=1…m-1 (2)

3. Кратчайший путь из вершины i в m, в котором допускается первых m промежуточных вершин. Имеет своей первой частью кратчайший путь из вершины i в некоторую промежуточную вершину k. А во второй – кратчайшую дугу из k в m.

di,mm=min{dm-1i,k+ d0k,m} k=1…m-1 (3)

4. диагональный элемент матрицы равен 0.

Алгоритм Данцига.

  1. Перенумеровать  вершины графа, определить матрицу D0 размером n*n  где n число вершин графа. Каждый элемент этой матрицы есть длина кратчайшей дуги от одной вершины до другой.
  2. Для каждого m принимающего значения 1,2,3…N определить матрицу Dm по формулам (2) – для строки m, (3) – для столбца m, (1) – для всех остальных элементов, кроме диагонального (di,im=0).


R336709263964 - WebMoney 41001419134483 - Яндекс Деньги
WebMoneyПонравился сайт? Окажите помощь в развитиияндекс