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

Question

[Andrew Dabich]

Есть задача, расчет расстояния путей между городами и задав два города рассчитать короткий путь. Я понимаю что нужно построить графы и с помощью алгоритмов Флойд - Уоршела или Дейкстра рассчитать короткий путь. Но вот проблема. Каким образом это можно отобразить на C++. Имеется ввиду какие данные будут использоваться, каким образом будет представлена эта карта дорог. Может у кого-то есть идеи. Очень помогут.

Answer 1

[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;

Answer 2

[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 - за сколько

Answer 3

[Rsa97]

Самое простое - двумерный массив w[N][N], где w[i][j] - стоимость перехода из узла i в узел j или -1 если такого пути нет. Если узлов много, а связность низкая, то надо уже копать в сторону разреженных массивов.

Answer 4

[Владлен Грачев]

Матрица смежности чаще всего используется. Еще можно матрицу инцидентности, но смысла обычно нет. Если матрица получается разреженной (много нулевых элементов), может иметь смысл воспользоваться какой-нибудь схемой упаковки. Но это, если матрица большая и имеет смысл думать о памяти.

Answer 5

[afiskon]

В алгоритмах типа поиска в глубину и A* вам нужно текущее состояние (координата на карте) и для заданного состояния список соседних состояний. Можно использовать для этого например map. Кстати, посмотрите повнимательнее на алгоритм A*, он просто идеально для вашей задачи подходит.