Урок 18: поиск кратчайшего пути методом Дейкстры и лабиринты
Предлагается реализовать алгоритм поиска кратчайших путей в графе методом Дейкстры (если что - можно найти много статей про этот алгоритм в интернете).
Граф представляем ввиде:
1) Вершины пронумерованы от \(0\) до \(N-1\) (где \(N\) - число вершин), для каждой вершины будем хранить:
-
Расстояние от точки старта до нее по кратчайшему найденному на данный момент пути. Т.е. мы пытаемся найти кратчайшие пути из стартовой точки до каждой другой точки. Изначально эти расстояния - бесконечность для всех вершин кроме самой стартовой.
-
Пометку обработали ли мы уже эту вершину, иначе говоря проверили ли все исходящие из этой вершины пути для того чтобы попытаться найти какие-то новые кратчайшие пути до каких-то вершин.
-
На равне с кратчайшим расстояним самого быстрого пути нам хотелось бы знать сам путь. Для этого достаточно в каждой вершине хранить ссылку на предыдущую вершину с кратчайшего пути, т.е. достаточно помнить последний шаг - тогда отшагнув по нему назад - можно будет спросить еще один предыдущий шаг у этой предыдущей вершины.
2) Ребра хранятся списками смежности:
-
Каждое ребро знает откуда и куда идет и знает свою длинну (т.е. насколько длинный маршрут надо преодолеть чтобы переместиться по этому ребру).
-
У каждой вершины есть вектор в котором хранятся все ребра которые исходят из этой вершины.
-
Получается список смежности - это вектор размера \(N\) в котором каждый элемент - векторов ребер (список ребер исходящих из вершины). Ведь вершины пронумерованы от \(0\) до \(N-1\). Т.е.
std::vector<std::vector<Edge>> edges(nvertices);
Алгоритм Дейкстры
1) Создали список смежности (т.к. записали для каждой вершины список ее ребер, обратите внимание что граф неориентированный, т.е. ребра симметричные).
2) Создали вектор в котором у каждой вершины хранится длина кратчайшего пути от старта до нее. Изначально все значения равны константе бесконечности INF
: const int INF = std::numeric_limits<int>::max();
(самое большое значение int
). Значение кратчайшего расстояния для начальной вершины выставляем в 0.
3) Создали вектор в котором у каждой вершины хранится флажок распространяли ли мы пути от нее, т.е. обработана ли уже вершины. Изначально никакя вершина не обработана.
4) Создали вектор указывающий для каждой вершины куда (в какую вершину) надо отшагнуть назад чтобы прошагать задом наперед кратчайший путь. Изначально пути неизвестны, а в таком случае давайте укажем несуществующую точку - \(-1\).
5) Пока прогресс не прекратится:
5.1) Ищем из вершин которые еще не обработаны (из которых еще не продолжили пути) - самую близкую к началу (и достижимую), выбрали ее - теперь это Избранная Вершина.
5.2) Если такой нет (т.е. все вершины обработаны или все необработанные вершины недостижимы) - прогресс прекратился - break;
5.3) Смотрим куда ведет каждое ребро исходящее из Избранной Вершины, если мы можем продлив путь нашей Избранной Вершины улучшить текущий ответ для соседней вершины (т.е. куда ведет очередное ребро) - делаем это (обновив ее кратчайшее расстояние и указав что шаг назад из нее надо делать в Избранную Вершину).
5.4) Помечаем Избранную Вершину обработанной (т.е. что она уже нанесла все добро своим соседям что могла).
6) Проверяем какой ответ лежит в вершине до которой мы хотели найти путь.
7) Если там лежит не бесконечность - то можем восстановить этот путь прошагав назад по ссылкам на предыдующую вершину на кратчайшем пути. Просто шагаем пока не дойдем до начальной вершины, ведь из начальной вершины предыдущий шаг будет \(-1\).
Задание 1: Дейкстра
Реализуйте метод Дейкстры описанный выше.
Чтобы проверить корректность:
1) Запустите на всех четырех тестах из папки data/mazesText/N.in
(просто Ctrl+C -> Ctrl+V -> Enter
в консоль после запуска приложения) - результат должен совпасть с N.out
2) Зарегистрируйтесь и отправьте свое решение на CodeForces - да, мы ищем Избранную Вершину очень медленно и не эффективно, но нас это устраивает, поэтому Превышено ограничение времени на тесте 31
- считайте успешным выполнением.
Задание 2: Лабиринт
Теперь давайте сделаем из этого что-нибудь классное, например найдем кратчайший путь в лабиринте:
1) Теперь граф надо придумать самим - давайте для начала придумаем как пронумеровать вершины графа - давайте нумеровать пиксель в строчке \(j\) и колонке \(i\) как \(j*w+i\), где \(w\) - ширина картинки.
2) Надо придумать какие у нас ребра - давайте соединять пиксели соседние друг с другом (т.е. у каждого пикселя кроме тех что на краю - четыре соседа).
3) А какие пропускные способности у ребер? Давайте они будут равны тому насколько яркий пиксель. Тогда в темных пикселях мы разрешаем двигаться дешево, а в белых - дорого (ведь это стенки).
4) Добавьте отрисовку кратчайшего пути:
5) Но как сделать так чтобы логика “какая пропускная способность у ребра” не зависела черно-белый или бело-черный у нас лабиринт? Чтобы работало даже если тропинка покрашена в синий цвет?
6) НЕ ЗАБУДЬТЕ протестировать все лабиринты (второй и третий - отличаются, пятый - не обязательный) и сохранить на диск результирующие картинки чтобы я мог легко и быстро на них посмотреть.
Мелочи
1) Не забудьте компилировать с оптимизациями (а не в Debug) - см. Как ускорить программу
2) НЕ ЗАБУДЬТЕ протестировать все лабиринты (второй и третий - отличаются, пятый - не обязательный) и сохранить на диск результирующие картинки чтобы я мог легко и быстро на них посмотреть.