В моем учебнике по теории вычислений есть пример для объяснения алгоритмов с полиномиальным временем:
PATH = {[G, s, t] | G - ориентированный граф, имеющий ориентированный путь от s к t}.
Алгоритм M с полиномиальным временем для PATH работает следующим образом. M = «На входе [G, s, t], где G - ориентированный граф с узлами s и t:
- Отметьте узел s.
- Повторяйте следующее, пока не перестанут отмечаться дополнительные узлы:
- Просканируйте все ребра G. Если ребро (a, b) идет от отмеченного узла a к немаркированному узлу b, отметьте узел b.
- Если отмечен t, примите. В противном случае откажитесь ».
Затем они объясняют, как алгоритм работает за полиномиальное время:
Очевидно, что этапы 1 и 4 выполняются только один раз. Этап 3 выполняется не более m раз, потому что каждый раз, кроме последнего, он отмечает дополнительный узел в G. Таким образом, общее количество используемых этапов не превышает 1+ 1 + m, что дает многочлен размером G.
* m - количество узлов в графе
Мой вопрос в том, что этап 3 не будет выполняться не более m-1 раз вместо m раз, поскольку первый узел отмечен на этапе 1?
Спасибо!
