CodinGame | Алгоритм Дейкстры: реализация и пример использования | C++

Приветствую! Большинство программистов сталкиваются с проблемой поиска кратчайшего пути. Конечно, #pathfinding алгоритмов довольно много. В этой заметке я приведу реализацию и пример применения классического алгоритма Дейкстры для графа с неотрицательными весами. На сайте CodinGame довольно много интересных соревнований для программистов. В одном из таких (A Code of Ice & Fire) необходимо написать бота, который сможет грамотно контролировать территорию, ресурсы и юниты.

Я не буду вдаваться в подробности: работа бота, игровая экономика и другие аспекты останутся за кадром.

Алгоритм Дейкстры пригодился для поиска кратчайшего пути между двумя клетками территории. Идея заключалась в том, что вершинами графа выступили клетки территории, а весами на рёбрах между ними — цены найма подходящих юнитов. Это позволило постоянно отслеживать кратчайший путь до вражеской крепости. При наличии нужного количества денег, от ближайшей клетки до базы оппонента сразу же создавалась победоносная цепочка из юнитов.

Основная проблема: нужно как-то преобразовать исходные данные в матрицу смежности. Но это уже кто во что горазд! Алгоритм Дейкстры на С++:

Консоль:

Послесловие:

Порешать задачи по программированию можно на CodinGame. -- © Bezukh Vladimir, 2019