Я пытаюсь написать алгоритм перебора, чтобы найти кратчайший путь от s до t. График является взвешенным, а также имеет отрицательные взвешенные ребра. Не нужно думать о негативных циклах. По сути, выход, если есть.
Я написал алгоритм Беллмана-Форда для решения этой проблемы. Это работает очень хорошо. (В случае комментариев «используйте лучшие алгоритмы») Однако, как второй шаг, мне нужно реализовать алгоритм грубой силы. Я попытался написать его поверх Breadth First Search Alg., Однако, как я уже говорил, есть отрицательные стороны. поэтому в некоторых случаях мне нужно вернуться к некоторым узлам.
Грубая сила Alg. для графов с неотрицательными ребрами:
Distance(s, t):
for each path p from s to t:
compute w(p)
return p encountered with smallest w(p)