процедуры \textsc{BFS} пропорционально размеру представления графа $G$ в виде списков смежных вершин.

Кратчайшие пути.

Как мы говорили, поиск в ширину находит расстояния от начальной вершины $s$ до каждой из достижимых вершин графа $G=(V,E)$. Под расстоянием мы понимаем \етрп{длину кратчайшего пути} (shortest-path distance): $\delta (s,v)$ определяется как минимальная длина пути, ведущего из $s$ в $v$. (Длина пути ---это число р\"~~а5бер в н\"~~а5м.) Если путей нет вообще, расстояние бесконечно. Пути длины $\delta (s,v)$ из $s$ в $v$ называются \етрЬ{кратчайшими путями}; их может быть несколько. (В главах 25 и 26 мы рассмотрим более общее понятие кратчайшего пути, учитывающее веса р\"~~а5бер: длина пути есть сумма весов. Сейчас все веса равны единице, так что длина есть число р\"~~а5бер.)

Докажем несколько свойств определ\"~~а5нного таким способом расстояния.

Лемма 23.1

Пусть $s$ --- произвольная вершина графа (ориентированного или

нет), a $(u,v)$ --- его ребро. Тогда $$ \delta (s,v)\le \delta

(s,u)+l.$$

Доказательство.

Если $и$ достижима за $к$ шагов из $s$, то и $v$ достижима не более чем за $к+1$ шагов (пройд\"~~а5м по ребру $(u,v)$), поэтому неравенство выполнено. Если же $и$ недостижима из $s$, то $\delta (s,u)=\infty$ и неравенство тривиально.

У, конец доказательства

У, далее текст переписан, и даже формулировки лемм изменены У, (с сохранением из общего числа для последующей нумерации У, - невозможно было оставлять такое длинное и запутанное У, рассуждение по такому простому поводу. . .

Лемма 23.2

Если $\delta($s$,$v$)>0$, то существует вершина $и$, до которой расстояние на единицу меньше ($\delta(s,v)=\delta(s,u)+l$) и для которой $v$ является смежной вершиной.

Доказательство. Рассмотрим кратчайший путь из $s$ в $v$. Он

будет иметь длину $\delta(s,v)$. Возьм\"~~а5м вершину $и$, лежащую на

этом пути непосредственно перед $v$. Нам надо убедиться, что до

не\"~~а5 расстояние на единицу меньше. В самом деле, у нас есть

ведущий в не\"~~а5 путь длины $\delta(s,v)-l$ (отбросим последнее

ребро), а более короткого пути быть не может по предыдущей

лемме.

У, конец доказательства

В условиях леммы для нахождения кратчайшего пути из $s$ в $v$ достаточно найти кратчайший путь из $s$ в $и$ и добавить к нему ребро $(u,v)$.

\medskip

Теперь мы можем доказать, что поиск в ширину правильно вычисляет длины кратчайших путей.

Работа процедуры \textsc{BFS} делится на начальный этап (строки 1-8) и повторения цикла в строках 9-18. Нас будет интересовать состояние переменных после нескольких таких повторений.

Лемма 23.3

Для всякого целого неотрицательного $к$ существует момент после нескольких повторений тела цикла (строки 10-18), когда выполнены следующие утверждения:

\begin{itemize} \item

вершины, для которых расстояние от начальной меньше $к$ --- ч\"~~а5рные,

равно $к$ --- серые, больше $к$ --- белые;

\item

в очереди $Q$ находятся серые вершины и только они; \item

в массиве $d$ хранятся правильные значения расстояния от начальной вершины для ч\"~~а5рных и серых вершин, и бесконечные значения для белых; \item

если $v$ --- серая или ч\"~~а5рная вершина, то

$\delta(s,\pi(v))=\delta(s,v)-l$ и в графе есть ребро $(v,\pi [v])$; для белых вершин значение $\pi$ есть \textsc{nil}. \end{itemize}

Доказательство. Индукция по $к$.

После выполнения строк 1-8 все пункты леммы выполнены для $к=0$: на расстоянии $к$ находится единственная вершина (начальная), она серая, остальные белые, серая вершина лежит в очереди, для белых вершин $d$ бесконечно и $\pi$ равно \textsc{nil}, а для серой вершины значения $d$ и $\pi$ правильны.

Пусть теперь для некоторого $к$ утверждение леммы выполнено, и после нескольких итераций цикла вс\"~~а5 так, как написано в лемме. Что будет происходить после этого? Из очереди будут забираться лежащие в ней вершины, которые мы будем называть \textit{npocMaTpHBaeMHMn}. Для смежных с ними белых вершин будут выполняться строки 13-16; в строке 16 они добавляются в конец очереди, и потому мы будем называть их \етрп{добавляемыми}. В какой-то момент очереди будут изъяты все находившиеся там изначально вершины, то есть все вершины, находящиеся на расстоянии $к$, и останутся только вновь добавленные. (Обратите внимание, что здесь существенно используется

правило работы очереди: первым приш\"~~а5л --- первым уш\"~~а5л.)

В этот момент мы мысленно прерв\"~~а5м выполнение процедуры и убедимся, что выполнены все условия леммы для на единицу большего значения $к$.

Просматриваемые вершины --- это вершины, которые были в очереди;

по предположению они находятся на расстоянии $к$.

Добавляемые вершины находятся на расстоянии $к+1$. В самом деле, они являются смежными с просматриваемыми вершинами, находящимися на расстоянии $к$, и потому по лемме 23.1 расстояние будет не больше $к+1$. С другой стороны, добавляются только белые вершины, и потому по предположению индукции расстояние до них больше $к$.

Будут добавлены все вершины, находящиеся на расстоянии $к+1$. В самом деле, если вершина $v$ находится на расстоянии $к+1$, то по лемме 23.2 существует вершина $и$ на расстоянии $к$, для которой она смежная. Вершина $и$ должна быть среди просматриваемых, и во время е\"~~а5 обработки вершина $v$ будет добавлена. Надо только иметь в виду, что вершин $и$ может быть

несколько --- но это не мешает делу, так как во время просмотра

первой из них вершина $v$ будет добавлена (после чего она будет серой и условие в строке 12 будет ложно, так что второй раз е\"~~а5