Разбор добавил Джафар Исхоков

Пусть w_i,j - длина дуги из вершины i в вершину j или бесконечность, если такой дуги нет.

Пусть A_n,m - длина кратчайшего пути из начальной вершины в вершину

m, проходящего не более чем по n ребрам. Пусть k - предыдущая вершина в этом

пути. Тогда A_n,m=A_n-1,k + w_k,m. Значит A_n,m =

min(A_n-1,m, min{1<=i<=N}(A_n-1,i+w_i,m)) (*).

Значения A_0,i равны бесконечности для всех i, отличных от s, A_0,s=0.

Будем считать A_i,j в порядке неуменьшения i, а при равных i -

в порядке увеличения j. Тогда для вычисления i-й строки матрицы A нам необходимо

знать только i-1-ую ее строку. Ответом на нашу задачу является

N-я строка, значит, на каждом шаге можно хранить только предыдущую строку матрицы.

При такой реализации алгоритм будет выполнять порядка N³ операций.

Заметим, что при вычислении следующей строки матрицы по предыдущей каждую дугу графа

мы рассмотрели ровно 1 раз. Воспользуемся этим, чтобы немного ускорить наш алгоритм. Пусть у нас

известна n-1 строка матрицы A. Скопируем ее в n-ую строку. Далее рассмотрим все

дуги нашего графа (x,y) и изменим A_n,y согласно формуле: A_n,y =

min(A_n,y,A_n-1,x+w_x,y) (**). Теперь у нас посчитана n-я строка матрицы A.

При такой реализации алгоритм выполнит порядка NM действий.

6 4
1 2 10
2 3 10
1 3 100
4 5 -10

0 10 20 30000 30000 30000