На странице представлен фрагмент

Реши любую задачу с помощью нейросети.

Этот алгоритм  отличается от алгоритма Флойда последовательностью выполнения действий. Перенумеруем все вершины графа от 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).
   

Купить уже готовую работу

Модель Штакемберга
Контрольная работа, Экономика
Выполнил: capperfoot
100
Логика (Вариант 2, Саратовский ГУ)
Контрольная работа, Логика
Выполнил: mic94
150

Так же вы можете купить уже выполненные похожие работы. Для удобства покупки работы размещены на независимой бирже. Подробнее об условиях покупки тут.

 
4.74
Mirasue
Работаю в сфере контрольных работ больше 6-ти лет. Есть своя команда по выполнению контрольных работ