path_delivery-Z3tA

Это шаблонны проект для выполнения ДЗ

Запуск Сборки и тестов через терминал

Задача: Поиск кратчайшего пути между городами (Алгоритм Дейкстры)

Цель задания

Реализовать алгоритм Дейкстры для поиска кратчайшего пути в графе городов, соединённых дорогами с определённой стоимостью проезда.
Используемые структуры данных:

• std::priority_queue
  для эффективного выбора следующей вершины.
• Контейнеры STL для представления графа (например,
  std::unordered_map
  ).

Описание задачи

Представьте, что у вас есть карта городов, где:

• Каждый город — это вершина графа.
• Дороги между городами — это рёбра графа с положительной стоимостью (весом) проезда.

Требуется:
Написать программу, которая для двух заданных городов находит путь с минимальной суммарной стоимостью и возвращает последовательность городов на этом пути.

Входные данные

Граф задаётся программно через добавление рёбер. Пример использования класса:

Требования к реализации

1. Класс

   Graph
   :
   • Метод
     add_edge(from, to, cost)
     добавляет дорогу между городами
     from
     и
     to
     с указанной стоимостью.
   • Метод
     find_shortest_path(start, end)
     возвращает вектор городов в порядке следования от
     start
     до
     end
     .
   • Если пути не существует, метод возвращает пустой вектор.

2. Алгоритм Дейкстры:

   • Использовать
     std::priority_queue
     для оптимизации выбора следующей вершины.
   • Учитывать, что стоимость дорог всегда положительна.

3. Обработка ошибок:

   • Если города
     start
     или
     end
     отсутствуют в графе, выбросить исключение (например,
     std::invalid_argument
     ).

Примеры

Пример 1

Пример 2

Пример 3 (Нет пути)

Примечания

1. Граф ориентированный?
   Нет, дороги считаются двусторонними (неориентированный граф). Если добавлено ребро

   A -> B
   , подразумевается, что движение возможно и в обратную сторону (
   B -> A
   ).

2. Советы по реализации:

   • Для хранения расстояний используйте словарь (
     std::unordered_map<std::string, int>
     ).
   • Для отслеживания предыдущих вершин на пути используйте ещё один словарь.
   • Приоритетная очередь должна хранить пары
     (текущая_стоимость, город)
     .

Как тестировать своё решение

1. Простые случаи:

   • Путь из города в самого себя.
   • Граф из двух городов с одной дорогой.

2. Сложные случаи:

   • Циклические маршруты.
   • Несколько возможных путей с разной стоимостью.

3. Краевые случаи:

   • Город без дорог.
   • Запрос пути между несвязанными городами.

Шаблон кода