Algorithm for finding paths in the graph

The task

Find all possible paths between two vertices in the graph not intersecting by:
a) browning
b) tops.

Input

The input data is the adjacency matrix compiled according to this rule: C [i, j] = 1, if the graph has an edge (Ai, Aj) and C [i, j] = 0 otherwise.

Solution [up]

To build all the possible paths between two vertices, we use the in-depth search, which will be modified.

To search for a route that does not intersect at the vertices, it is necessary to memorize the traversed vertices and not make a second pass through them. The search for the current path is considered completed when the finish point is reached or the impossibility of adding another edge to the route. In any case, after completing the construction of the current route, we go back 1 step back and try to build another route.

To search for a route that does not intersect along edges, it is necessary to create an array-indicator of the use of each edge. If the edge has not been used, then the label for it is true, otherwise - false. During the route search, before we go to the top, we check if the current edge was used. If not, we add it to the route and recursively call the search for the next vertex. When reaching the "dead end" of the finish vertex, we take a step back, considering the last edge in the route uncropped.

Formal description

  Way ()
 1. Create an adjacency matrix for the graph.
 2. Read the numbers of the starting and finishing vertices of the graph.
 3. Initialize usage labels.
 4. Add a start point to the path.
 5. Find all routes that do not intersect along the edges (pp.5.1-5.5):
    5.1.  If the search is not called from the starting vertex, then consider the last 
         edge of the route passed.
    5.2.  Find the vertex incident to the given.
    5.3.  If the edge that leads to the incident vertex was not 
         used, then add a vertex to the path, then take it 
         current and go to 5.1.
    5.4.  If the finish is reached, then output the path.
    5.5.  Consider the last edge of the route failed.
 6. Find all routes that do not intersect at the vertices (pp.6.1-6.5):
    6.1.  Assign the step number to the current vertex.
    6.2.  Find the vertex incident to the given.
    6.3.  If the incident vertex was not used, then consider it 
         the current one, remember the previous vertex and go to p.6.1.
    6.4.  If the finish is reached, then output the path.
    6.5.  Consider the last peak of the route not passed.