algorithm - 路径从 '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 被标记，接受。否则，拒绝。”

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

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

*m是图中的节点数

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

谢谢!

Answer 1

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