Пусть дан невзвешенный граф. В нем требуется найти длины кратчайших путей от некоторой заданной вершины до всех остальных.
Заведем массив B, в котором будем хранить найденные длины путей (B[i] - длина пути от начальной вершины до вершины i). Если мы эту длину пока не знаем, будет хранить, например, -1.
Вначале мы не знаем длины этих путей. Заполним массив B значением -1.
На самом деле, одно расстояние мы знаем - это расстояние до исходной вершины. Оно равно 0. Запишем это в массив B.
Далее будем повторять следующий шаг. На очередном, K-ом шаге мы найдем все вершины, до которых расстояние K (и запишем это в массив B). Как это сделать?
Просматриваем все вершины. Как только нашли вершину, до которой расстояние K-1 (пусть это вершина с номером J), проделываем следующее. Смотрим всех соседей этой вершины (например, перебирая все вершины и проверяя, что они соседи c J), если до вершины номер J расстояние K-1, а до некоторого ее соседа расстояние нам еще не известно, то записываем, что расстояние до этого соседа равно K. Заметьте, что на очередном шаге вершин, до которых расстояние K-1, может быть несколько - описанные действия нужно повторить для каждой из них.
Описанный шаг нужно повторить N-1 раз, т.к. в худшем случае в графе может быть путь длиной N-1, а пути длиной N не может быть никогда.
Таким образом, описанный алгоритм можно реализовать примерно так:
Заполняем массив B значением -1
B[начальная вершина]:=0;
K - номер шага - пробегает значения от 1 до N-1, и для каждого K выполняем следующие действия:
Перебираем все вершины (пусть J - номер просматриваемой вершины), для каждой из них
если B[J]=K-1, делаем следующее
Опять перебираем все вершины (пусть теперь I - номер вершины)
если вершины J и I соединены и B[I]=-1, то B[I]:=K