Я пытаюсь сделать оптимизированную версию алгоритма Bellman Ford для запуска в худшем случае. Под оптимизированной версией я подразумеваю, что после расслабления 1 раунда ребер и при отсутствии дальнейших обновлений на кратчайшем расстоянии он завершается.
Например, простой связный взвешенный ориентированный граф с 7 вершинами, такой, что работает Оптимизированный Беллман-ФордАлгоритм из исходной вершины 0 использует как минимум 5 раундов для получения правильных кратчайших путей.
График не может содержать отрицательный цикл веса. то есть все исходящие ребра из вершины 0 обрабатываются, затем ребра из вершины 1 и т. д.
Я знаю, что это связано с циклами. Но я не очень уверен в том, что стратегия построения графика отвечает требованиям.