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