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

Question

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

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

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

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

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

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

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

Answer 1

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

Как примечание стороны, помните, что Dijkstra не работает, когда у вас есть ребра с отрицательными значениями.

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