Какой алгоритм для решения «проблемы кратчайшего пути» я должен использовать?

Question

Итак, я занимался исследованием проблемы Стратегия игры ICPC 2014 (стр. 7).

Это состоит из настольной игры с n ящиками, каждый из которых имеет уникальный набор путей, который идет к другому ящику на доске (может иметь путь, который идет сам по себе). Я думаю, что граф был бы хорошим представлением игры, более определенным направленным графом

графическое представление случая с n = 2

Я нашел 2 возможных алгоритма, которые должны решить проблему:

1.- видео YouTube , где говорится, что я должен использовать поиск в ширину

2.- Блог , комментирующий решение некоторых проблем того года ICPC. Автор говорит, что DP (динамическое программирование) можно использовать. На странице Википедии объясняется алгоритм, называемый Алгоритм Дейкстры , который используется для "проблемы кратчайшего пути", как говорится на странице.

Является ли один из этих алгоритмов лучшим решением проблемы? у одного из них лучшая производительность или что-то в этом роде?

Answer 1

Вы используете поиск в ширину (кратко BFS ), когда ребра графа не имеют веса (как в вашем случае), и алгоритм Дейкстры для взвешенного графа.

В качестве примечания помните, что Дейкстра не работает, если у вас есть ребра с отрицательными значениями.

Если подумать о сложности , этот вопрос может быть в ваших интересах: Зачем использовать алгоритм Дейкстры, если поиск в ширину (BFS) может сделать то же самое быстрее?