路径从 's' 到 't' 的有向图的多项式时间算法

Question

我的计算理论教科书有一个解释多项式时间算法的例子：

PATH = {[G,s,t]|G 是一个有向图，具有从 s 到 t 的有向路径}。

PATH 的多项式时间算法 M 的操作如下。 M = “在输入 [G,s,t] 上，其中 G 是具有节点 s 和 t 的有向图：

1. 在节点s上做一个标记。
2. 重复以下操作，直到没有其他节点被标记：
3. 扫描G的所有边，如果发现一条边(a,b)从标记节点a到未标记节点b，标记节点b。
4. 如果 t 被标记，接受。否则拒绝。”

然后他们继续解释算法如何 运行s 在多项式时间内：

显然，阶段 1 和阶段 4 只执行一次。阶段 3 运行s 最多 m 次，因为每次除了最后一次它都在 G 中标记一个额外的节点。因此，使用的阶段总数最多为 1+ 1+m，给出大小为的多项式G.

*m 是图中的节点数

我的问题是第 3 阶段不会 运行 最多 m-1 次而不是 m 次，因为第一个节点在阶段 1 中被标记？

谢谢！

Answer 1

它最多运行 m-1 次，它标记了除 s 之外的其他节点，然后运行 ​​1 次，没有找到要标记的其他节点。