If I had 16 destinations,

I have to do

But I can't predict how many destinations I have in advance

for (const auto& it = nodes.begin(); it != nodes.end(); ++it)
{
     for (const auto& it2 = std::next(it); it2 != nodes.end(); ++it2)
     {
          ... 16 inner loops
     }
}

What is a cleaner way to archieve this?

Thanks

Jack

What do you mean by “destination”? Are you simply looking for a path between every pair of vertices in your graph?

Your example code doesn't clarify your question much either – you iterate over all unordered pairs of vertices, and then what? What would those 16 inner loops do?

Did you consider cycles in your path?

I think I know what he is asking. Let's say I want to list all subsets of size 3 of the numbers in {0, 1, ..., 9}. I could do this:

  for (int i1 = 0; i1 < 10; ++i1) {
    for (int i2 = i1 + 1; i2 < 10; ++i2) {
      for (int i3 = i2 + 1; i3 < 10; ++i3) {
        // Do something
      }
    }
  }

However, this is kind of ugly and you cannot easily make it work for subsets of size k. The solution is using a recursive function. I believe the name for this technique is "backtracking". It's a little bit involved, but it's very powerful.

void build_subsets(int *subset, int k, int already_built, int first_index) {
  if (already_built == k) {
    // Do something
  }
  else {
    for (int i = first_index; i < 10; ++i) {
      subset[already_built] = i;
      build_subsets(subset, k, already_built + 1, i + 1);
    }
  }
}

EDIT: In case it's not entirely clear how you get this started, here's a complete program:

#include <iostream>

void build_subsets(int *subset, int k, int already_built, int first_index) {
  if (already_built == k) {
    for (int i = 0; i < k; ++i)
      std::cout << subset[i] << ' ';
    std::cout << '\n';
  }
  else {
    for (int i = first_index; i < 10; ++i) {
      subset[already_built] = i;
      build_subsets(subset, k, already_built + 1, i + 1);
    }
  }
}

int main() {
  int subset[3];
  build_subsets(subset, 3, 0, 0);
}

Generating all possible combinations of route in a graph? ... But I can't predict how many destinations I have in advance ...

As above, there are several ways to interpret the question.

It looks like a question about pathfinding to me. If you are looking to find a path along a bunch of nodes, there are a few common algorithms.

For finding the shortest path between two points there is Djikstra's two point shortest path algorithm. (Google it). Unfortunately the algorithm takes a long time and a lot of space, so there is a way to guide it to faster results. By adding a heuristic -- such as the physical distance on a map -- it becomes the A-Star or A* algorithm, which is extremely common in games. A* can potentially give a less than optimal path, but it is usually good enough and the speedup is worth the rare exception.

For finding the shortest paths between all points on a map, there are algorithms to compute all the paths and store them, but the space required is usually enormous. Every pair can potentially have a length of the full set of nodes. The number of permutations I believe uses the nPr function and each path could be the full set of points in the worst case (such as a circular ring where every node must move in a single direction around a ring). So the set of all pairs for 16 nodes is up to 240 * 16 = 3840 entries. A 10x10 grid would have 9900 pairs and up to 990000 elements for the full set. A map of 500x500 cells would completely overflow my calculator and could require many terabyts or even petabytes or exabytes to store the full map in a worst case scenario.

Games usually just calculate the shortest paths as needed at runtime.

For finding the shortest paths between all points on a map, there are algorithms to compute all the paths and store them, but the space required is usually enormous. Every pair can potentially have a length of the full set of nodes. The number of permutations I believe uses the nPr function and each path could be the full set of points in the worst case (such as a circular ring where every node must move in a single direction around a ring). So the set of all pairs for 16 nodes is up to 240 * 16 = 3840 entries. A 10x10 grid would have 9900 pairs and up to 990000 elements for the full set. A map of 500x500 cells would completely overflow my calculator and could require many terabyts or even petabytes or exabytes to store the full map in a worst case scenario.

Computing all shortest paths in a graph with N nodes can be done in O(N^3) time with O(N^2) memory. See https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm

The result is stored as a single matrix indicating the total cost for the path between any two nodes. Reconstructing the paths from this information is very easy.

For finding the shortest path between two points there is Djikstra's two point shortest path algorithm. (Google it). Unfortunately the algorithm takes a long time and a lot of space, so there is a way to guide it to faster results. By adding a heuristic -- such as the physical distance on a map -- it becomes the A-Star or A* algorithm, which is extremely common in games. A* can potentially give a less than optimal path, but it is usually good enough and the speedup is worth the rare exception.

I believe that, given a proper heuristic (distance to destination, for instance), A-star is guaranteed to return an optimal result. (See the "Admissibililty" section of the wikipedia article https://en.wikipedia.org/wiki/A*_search_algorithm) I think this is actually the common case for games, so you'll get an optimal result. Have I missed something?

Geoff