Нахождение кратчайшего пути на графе с ребрами единичной длины

Общее правило для нахождения кратчайшего пути в графе состоит в том, чтобы каждой вершине x_i приписать индекс λ_i, равный длине кратчайшего пути из данной вершины в конечную. Приписывание индексов вершинам в случае графа с ребрами единичной длины производится в следующем порядке:

1) конечной вершине приписывается индекс 0;

2) всем вершинам, из которых идет ребро в конечную вершину, приписывается индекс 1

3) всем вершинам, еще не имеющим индексов, из которых идет ребро в вершину с индексом λ_i, приписывается индекс λ_i+1. Этот процесс продолжается до тех пор, пока не будет помечена начальная вершина. По окончании разметки индекс у начальной вершины будет равен длине кратчайшего пути. Сам кратчайший путь найдем, если будем двигаться из начальной вершины в направлении убывания индексов.