Initialize-Single-Source;

Relax;

for(i=0;i<n;i++)
	{
	if (d[v] > (d[u] + ω[u, v]))
		{
		return false;
		}
	else 
		{
		return true;
		}
	}

Опишем алгоритм по шагам:

Шаг 0. Занумеруем все вершины из G=(A,B), так что A = {1, 2, ... p} и при этом номер «1» имеет именно та вершина, из которой будут найдены кратчайшие пути во все остальные вершины. Построим, далее матрицу

M = (m_ij ), i,j = 1, 2, ... p, положив

Шаг 1. Около первой строки матрицы M, слева от матрицы, поставим числовую пометку «0» и такую же пометку проставим над первым столбцом матрицы. Затем просмотрим помеченную строку слева направо и всякий раз, встречая клетку с числом, прибавим это число к пометке строки и сумму проставим над столбцом, в котором эта клетка находится. Затем отразим пометки столбцов относительно главной диагонали. Возникнут помеченные строки. С каждой из помеченных строк проделаем то же самое: просмотрим помеченную строку слева направо и всякий раз, встречая клетку с числом, прибавим это число к пометке строки и сумму поставим в качестве пометки над столбцом, в котором эта клетка стоит. При этом будем соблюдать принцип: «имеющуюся пометку не менять». Затем пометки столбцов отразим относительно главной диагонали и с помеченными строками вновь проделаем то же самое. И так далее, пока не окажутся помеченными все строки и все столбцы.

Шаг 2. Просмотрим строки таблицы в порядке возрастания их номеров. В каждой строке просматриваются клетки слева направо и всякий раз, когда встречается число, оно складывается с пометкой строки и сумма сравнивается с пометкой столбца, в котором найденное число расположено. Если сумма оказалась меньше, чем пометка столбца, то эта пометка столбца заменяется на упомянутую сумму. Если же сумма оказалась больше или равной пометке, то ничего не меняется. После такого просмотра всех строк новые пометки столбцов отражаются относительно главной диагонали и вся процедура повторяется. И так до тех пор пока не прекратятся какие бы то ни было изменения в пометках.

Шаг 3. Теперь по пометкам можно построить кратчайшие пути из первой вершины во все остальные. Фиксируем произвольную вершину k (k = 2,3,...p) и опишем кратчайший путь из первой вершины в вершину k. Во-первых, длина этого кратчайшего пути равна пометке λ _k , стоящей над столбцом номер k. Во-вторых, предпоследняя вершина в кратчайшем пути из первой вершины в вершину k находится так: в столбце номер k отыскиваем число, сумма которого с пометкой строки, в которой оно расположено, равна λ _k. Пусть номер строки, в которой найденное число оказалось, равен l. Тогда предпоследней вершиной в кратчайшем пути из 1 в k будет вершина l. Вершину, которая предшествует вершине l, надо отыскивать как предпоследнюю в кратчайшем пути из 1 в l и так далее.

Приведем пример. Пусть исходный взвешенный граф дает следующую матрицу M:

Начнем расставлять пометки:

Проведем уменьшение пометок:

Укажем кратчайшие пути:

1→2: длина 10; путь (от конца к началу) 2←1;

1→3: длина 13; путь (от конца к началу) 3←1;

1→4: длина 30; путь (от конца к началу) 4← 3←1;

1→5: длина 23; путь (от конца к началу) 5←3←1;

1→6: длина 34; путь (от конца к началу) 6←7←2←1;

1→7: длина 21; путь (от конца к началу) 7←2←1;

1→8: длина 38; путь (от конца к началу) 8←5←3←1.