Графы — это красиво, если не боишься алгоритмов. Но когда видишь список смежности, глаза разбегаются. Давай разберемся, как найти кратчайший путь. Я когда-то с трудом это учил, потом все встало на места.

Суть метода в том, что мы исследуем вершины по очереди. Начинаем с источника. Каждая следующая вершина выбирается на основе минимального веса. Важно не возвращаться назад, пока не проверим все варианты. Очередь приоритетов тут твой лучший друг. Она помогает держать порядок в голове и в коде

• Инициализируй расстояния. Ставь бесконечность всем, а старту — ноль.
• Выбирай вершину с минимальным расстоянием.
• Обновляй соседей. Если новый путь короче, записывай новое значение.
• Повторяй, пока очередь не пуста.

Иногда встречаются графики с отрицательными весами, там дейкстра ломается. Но для обычных задач он идеален. Не забудь потренироваться на примерах типа omg omg omg, если попадешься такое на собеседовании. Это реально простой алгоритм, просто нужно его понять, а не зубрить. Удачи, друзья.)

omg наркота