Алгоритм Боржа для перебора простых путей на графе

Question

[Rzhepish]

В рамках работы над курсачом нужно узнать, что это есть. Поисковики хором предлагают искать «Бержа» вместо «Боржа».
В книге К.Бержа «Теория графов и ее применения» непосредственно этот вопрос не затрагивается. Возможно, следует искать в более поздних публикациях.
Может кто-то подскажет, где можно найти подробное описание алгоритма?

Answer 1

[atomicus]

Не слышал о таком алгоритме. И для описанной задачи он вряд ли существует. Дело в том, что перебор всех простых путей (в которых ни одна вершина не встречается дважды) между любыми двумя вершинами в графе общего вида является NP-полной задачей. Кроме метода грубой силы решения пока не найдено.

Comments

[Rzhepish]

Да, сегодня уточнил. Брутфорс с небольшими оптимизациями. Спасибо большое за ответ.

Answer 2

[Nostr]

Можно посмотреть тут, если подойдет www.e-maxx.ru/algo/
Но не факт, что там есть именно тот алгоритм, который вы ищете