KTH SOSTORKTION

Question

Кто-нибудь знает, как я могу написать алгоритм программирования (код C ++ был бы отличным), который находит кратчайший путь KTH для данного набора узлов и краев на циклическом графике?

Например, кратчайший путь (который может быть найден Дейкстрой или Беллманом Фордом) считается 1 -й кратчайшим путем. Теперь 2 -й самый короткий путь - самый короткий, который идет после 1 -го кратчайшего пути. Теперь я хочу, чтобы алгоритм нашел самый короткий путь KTH. Вам дается количество узлов, краев и набора краев, как следующее:

Количество узлов: 5
Количество краев: 6
края:
0 1
0 2
1 2
2 3
3 1
1 4
Узел источника: 0
Узел назначения: 4

«Обратите внимание, что этот график содержит цикл», спасибо.

Answer 1

Использовать Однородный поиск затрат алгоритм. Где Википедия говорит «решение возврата», не уходи и return но добавьте результат в какой -то список, пока этот список не содержит k пути А k«Элемент списка (считать 1) будет k«Самый короткий путь.

Не держите набор «закрытый»/«исследован», иначе этот алгоритм не будет работать должным образом.