Код основан на книге "Грокаем Алгоритмы" Адитьи Бхаргавы
Алгоритм Дейкстры - это алгоритм поиска кратчайшего расстояния между узлами в графах. Данный алгоритм работает только с направленными ациклическими графами, которые нередко обозначаются сокращением DAG (Directed Acyclic Graph). Также алгоритм не работает с графами, которые имеют рёбра с отрицательными весами.
Алгоритм Дейкстры состоит из четырёх шагов:
- Найти узел с наименьшей стоимостью (то есть узел, до которого можно добраться за минимальное время).
- Проверить, существует ли более дешевый путь к соседям этого узла, и если существует, обновить их стоимости.
- Повторять, пока это не будет сделано для всех узлов графа.
- Вычислить итоговый путь
В файле input.txt описывается граф, в котором мы ищем кратчайшее расстояние между узлами книга и пианино.
После окончания работы программы выводится расстояние, вычесленное между узлами, и весь путь по узлам от начального до конечного.
В файле input.txt сначала через пробел указываются названия двух узлов:
- начального - книга
- конечного - пианино
Дальше в нескольких строках указывается веса ребер между соседними узлами. Например:
бас-гитара пианино 20
Причём количество строк указывать не нужно. Пусть строк будет столько, сколько нужно для описания графа.