dabich
@dabich
Web Developer

Задача расчета расстояния путей между городами с использование графов в C++?

Есть задача, расчет расстояния путей между городами и задав два города рассчитать короткий путь. Я понимаю что нужно построить графы и с помощью алгоритмов Флойд - Уоршела или Дейкстра рассчитать короткий путь. Но вот проблема. Каким образом это можно отобразить на C++. Имеется ввиду какие данные будут использоваться, каким образом будет представлена эта карта дорог. Может у кого-то есть идеи. Очень помогут.
  • Вопрос задан
  • 7368 просмотров
Решения вопроса 1
Flaker
@Flaker
Самым простым вариантом будет использование алгоритма Флойда-Уоршалла для поиска расстояний от каждой до каждой вершины. Асимптотическая сложность n^3, поэтому, использовать в реальных проектах не стоит, зато реализация самого алгоритма элементарная (по сути, полный перебор).

#include <iostream>

#define INF 9000000
#define MatrixLen 5

/* Алгоритм Флойда — Уоршелла.*/

/* Исходная матрица расстояний */
int matrix[MatrixLen][MatrixLen] =
{
	{0, 5, 2, INF, INF},
	{5, 0, INF, 7, INF},
	{2, INF, 0, 2, 8},
	{INF, 7, 2, 0, 1},
	{INF, INF, 8, 1, 0}
};

	/* Поиск расстояния минимального пути от каждой до каждой вершины */
	for (size_t k(0); k < MatrixLen; ++k)
		for (size_t i(0); i < MatrixLen; ++i)
			for (size_t j(0); j < MatrixLen; ++j)
				if (matrix[i][k] < INF && matrix[k][j] < INF)
					if (matrix[i][k] + matrix[k][j] < matrix[i][j])
					{
						matrix[i][j] = matrix[i][k] + matrix[k][j];
						parents[i][j] = k;
					}


	int from = 0;
	int to = 4;

        /* Теперь минимальное расстояние от любой до любой будет matrix[ОТКУДА][КУДА] */

	std::cout << "Path length from " << from << " to " << to << " is " << matrix[from][to] << std::endl;
Ответ написан
Комментировать
Пригласить эксперта
Ответы на вопрос 4
@Confl1kt
списками хранить надо
vector<vector<int>> - для единичных ребер
vector<vector<pair<int,int>>> - для не единичных ребер

заполнение данными:
for(int i =0; i < n; i++){
   for(int j=0; j < m; j++){
      v[i].push_back(make_pair(j,weight));
   }
}

где i - текущая вершина, n - Кол-во вершин, j - текущее ребро i-ой вершины, m - кол-во ребер i-ой вершины, weight - длина\вес ребра

соответственно в будующем можем получить все исходящие ребра из i вершины
v[i][j].first - куда, v[i][j].second - за сколько
Ответ написан
Комментировать
Rsa97
@Rsa97
Для правильного вопроса надо знать половину ответа
Самое простое - двумерный массив w[N][N], где w[i][j] - стоимость перехода из узла i в узел j или -1 если такого пути нет. Если узлов много, а связность низкая, то надо уже копать в сторону разреженных массивов.
Ответ написан
Комментировать
Матрица смежности чаще всего используется. Еще можно матрицу инцидентности, но смысла обычно нет. Если матрица получается разреженной (много нулевых элементов), может иметь смысл воспользоваться какой-нибудь схемой упаковки. Но это, если матрица большая и имеет смысл думать о памяти.
Ответ написан
Комментировать
afiskon
@afiskon
В алгоритмах типа поиска в глубину и A* вам нужно текущее состояние (координата на карте) и для заданного состояния список соседних состояний. Можно использовать для этого например map. Кстати, посмотрите повнимательнее на алгоритм A*, он просто идеально для вашей задачи подходит.
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы