У меня есть следующая функция BFS из Cormen.
Определение пути кратчайшего пути (s, v) от s до v как минимального числа ребер в любом пути от вершины s до вершины vили если нет пути от s до v. Путь длины пути (s, v) от s до v называется кратчайшим путем от s до v.
Ниже приводится лемма
Пусть G = (V, E) - ориентированный или неориентированный граф, и пусть s принадлежит V - произвольная вершина.Тогда для любого ребра (u, v) E,
path (s, v) <= path (s, u) + 1. </p>
Мой вопрос: почему мы имеемиметь <= в вышеприведенной формуле, я учил "=" - это нормально, кто-нибудь может сказать мне один сценарий, почему нам требуется <=? </strong>
Ниже приведен алгоритм BFS
Leema 2:
Пусть G = (V, E) - ориентированный или неориентированный граф, и предположим, что BFS запускается на G из заданной исходной вершины s, принадлежащей V. Тогда по окончании каждая вершина v принадлежитV, значение d [v], вычисленное BFS, удовлетворяет условию d [v]> = path (s, v).
Доказательство:
Мы используем индукцию по числу раз, когда вершинапомещается в очередь Q. Наша индуктивная гипотеза состоит в том, что d [v]> = путь (s, v) для всех v принадлежит V.
Основой индукции является ситуация сразу после помещения s вQ в строке 8 BFS.
Здесь действует индуктивная гипотеза, потому что d [s] = 0 = путь (s, s) и d [v] = путь (s, v) для всех v принадлежитV - {s}.
Мой вопрос: что делает aut?Что значит «Мы используем индукцию по числу раз, когда вершина помещается в очередь Q»?и как это связано с индуктивной гипотезой?
Спасибо!
BFS(G,s)
1 for each vertex u V[G] - {s}
2 do color[u] WHITE
3 d[u]
4 [u] NIL
5 color[s] GRAY
6 d[s] 0
7 [s] NIL
8 Q {s}
9 while Q
10 do u head[Q]
11 for each v Adj[u]
12 do if color[v] = WHITE
13 then color[v] GRAY
14 d[v] d[u] + 1
15 [v] u
16 ENQUEUE(Q,v)
17 DEQUEUE(Q)
18 color[u] BLACK