How can you find all the paths for passing from one vertex of the graph to another if the graph is oriented and an array of vertices is given through which it is impossible to pass? Vertices (initial, final and which cannot be passed) are set from the keyboard, adjacency matrix is ​​generated randomly. All matrix elements are stored in a multidimensional array. More interested in not even the implementation, but the very idea of ​​the search, because most of all the theory on finding the shortest path, and not all in general.

  • What are the limitations on the graph? Search in depth completely solves this problem. (for the final time). - pavel
  • @pavel, in the future there will be peaks that cannot be visited, and in this case at least start by looking for all possible options - NTP
  • write the final task. Because not to visit the top is much easier than to search for all the ways. - pavel
  • @pavel, changed - NTP

1 answer 1

Normal backtrack algorithm (view with return). Forbidden vertices, put, say, a false flag in a Boolean array. Then, when visiting another not yet traversed vertex, check this flag and ignore the vertex if false (i.e., go to the next not yet traversed neighbor from the vertex from where you came, etc.).