The task of calculating the distance of paths between cities using graphs in C ++?

Question

C++ / C#

There is a task, calculating the distance of paths between cities and by asking two cities to calculate the shortest path. I understand that you need to build graphs and use the Floyd-Warschel or Dijkstra algorithms to calculate a short path. But here's the problem. How can this be displayed in C++. It means what data will be used, how this road map will be presented. Maybe someone has ideas. Will help a lot.

Answer 1

The simplest option would be to use the Floyd-Warshall algorithm to find the distances from each to each vertex. The asymptotic complexity n ^ 3, therefore, should not be used in real projects, but the implementation of the algorithm itself is elementary (in fact, a complete enumeration).

#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

it is necessary to store lists
vector<vector<int>>- for single edges
vector<vector<pair<int,int>>>- for non-single edges
filling with data:

for(int i =0; i < n; i++){
   for(int j=0; j < m; j++){
      v[i].push_back(make_pair(j,weight));
   }
}

where i is the current vertex, n is the number of vertices, j is the current edge of the i-th vertex, m is the number of edges of the i-th vertex, weight is the length\weight of the edge
, respectively, in the future we can get all outgoing edges from the i-th vertex
v[i][j].first- where, v[i][j].second- for how much

Answer 3

The simplest is a two-dimensional array w[N][N], where w[i][j] is the cost of going from node i to node j or -1 if there is no such path. If there are many nodes, and the connectivity is low, then you need to dig towards sparse arrays.

Answer 4

The adjacency matrix is ​​the most commonly used. You can also use the incidence matrix, but it usually doesn't make sense. If the matrix turns out to be sparse (many zero elements), it may make sense to use some kind of packing scheme. But this is if the matrix is ​​large and it makes sense to think about memory.

Answer 5

In algorithms like DFS and A*, you need the current state (map coordinate) and, for a given state, a list of neighboring states. You can use for this for example map. By the way, take a closer look at the A* algorithm , it's just perfect for your task.