MIN_PATH

Поиск кратчайшего пути в графе между двумя заданными вершинами

• Есть файл каждая строка которого имеет формат: вершина:расстояние:вершина.
• Вершины - это вершины графа, расстояние - это расстояние между данными вершинами.
• Требуется написать программу, которая будет на вход получать данный файл и номера двух вершин, а на выходе выдавать минимальное расстояние между вершинами и распечатывать маршрут между данными вершинами.

Сборка и запуск:

Установка зависимостей для сборки на Ubuntu 16.04:

•  sudo apt install git build-essential cmake  libboost-all-dev libboost-filesystem1.58.0 libboost-program-options1.58.0
  

Сборка проекта

Скачать исходный код проекта:

•  git clone https://github.com/boa85/min_path.git
  

Перейти в каталог с исходным кодом:

•  cd ${project_source_dir}
  

Создание дирректории для работы cmake и переход в неё:

•  mkdir cmake-build-debug &&  cd cmake-build-debug/
  

Запуск cmake для генерации Makefile:

•  cmake ..
  

Сборка проекта:

•  make
  

Запуск

Показать справку

•  ./min_path --help
  

Найти кратчайший путь в графе между заданными вершинами и его длину

•  ./min_path -m minpath -f graph.txt  -i 1 -o 13
  

Сгененрировать случайный граф заданной плотности (используется модель Эрдеша-Реньи)

•  ./min_path -m generate -f graph.txt  -c 13 -p 33