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

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

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

Читайте также  Метод искусственного базиса (Симплекс метод) - Пример 2

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{dm,k+ dm-1k,j} k=1…m-1 (2)

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

Читайте также  Алгоритм Литтла - Пример 1

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

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

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

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