Contar todos los caminos posibles entre dos vértices

Cuenta el número total de vías o caminos que existen entre dos vértices en un grafo dirigido. Estos caminos no contienen un ciclo, la razón bastante simple es que un ciclo contiene un número infinito de caminos y, por lo tanto, crean un problema. 

Ejemplos: 

For the following Graph:

  
Input: Count paths between A and E
Output : Total paths between A and E are 4
Explanation: The 4 paths between A and E are:
                      A -> E
                      A -> B -> E
                      A -> C -> E
                      A -> B -> D -> C -> E 

Input : Count paths between A and C
Output : Total paths between A and C are 2
Explanation: The 2 paths between A and C are:
                      A -> C
                      A -> B -> D -> C

Aproximación: 
el problema se puede resolver utilizando el retroceso , que dice tomar un camino y comenzar a caminar sobre él y verificar si nos lleva al vértice de destino, luego contar el camino y retroceder para tomar otro camino. Si la ruta no conduce al vértice de destino, descarte la ruta. 
Este tipo de recorrido de gráfico se llama Backtracking.
El retroceso del gráfico anterior se puede mostrar así: 
el vértice de color rojo es el vértice de origen y el vértice de color azul claro es el destino, el resto son caminos intermedios o descartados. 
 

Esto da cuatro caminos entre el origen (A) y el vértice de destino (E) .

¿Por qué esta solución no funcionará para un gráfico que contiene ciclos?  
El problema asociado con esto es que ahora si se agrega un borde más entre C y B, haría un ciclo (B -> D -> C -> B) . Y por lo tanto, después de cada ciclo a través del bucle, la longitud del camino aumentará y eso se considerará como un camino diferente, y habría infinitos caminos debido al ciclo. 
 

Algoritmo: 

1. Cree una función recursiva que tome el índice del Node de un gráfico y el índice de destino. Mantenga un conteo de variables estáticas o globales para almacenar el conteo. Mantenga un registro de los Nodes visitados utilizando una array visitada y, al regresar, marque el Node actual para que no se visite y descubra otras rutas.
2. Si los Nodes actuales son el destino, aumente el recuento.
3. De lo contrario, para todos los Nodes adyacentes, es decir, los Nodes que son accesibles desde el Node actual, llame a la función recursiva con el índice del Node adyacente y el destino.
4. Imprime el conteo.

Implementación:  

/*
 * C++ program to count all paths from a source to a
 * destination.
 * https://www.geeksforgeeks.org/count-possible-paths-two-vertices/
 * Note that the original example has been refactored.
 */
#include <cassert>
#include <iostream>
#include <list>
#include <vector>
using namespace std;
 
/*
 * A directed graph using adjacency list representation;
 * every vertex holds a list of all neighbouring vertices
 * that can be reached from it.
 */
class Graph {
public:
    // Construct the graph given the number of vertices...
    Graph(int vertices);
    // Specify an edge between two vertices
    void add_edge(int src, int dst);
    // Call the recursive helper function to count all the
    // paths
    int count_paths(int src, int dst, int vertices);
 
private:
    int m_vertices;
    list<int>* m_neighbours;
    void path_counter(int src, int dst, int& path_count,
                      vector<bool>& visited);
};
 
Graph::Graph(int vertices)
{
    m_vertices = vertices; // unused!!
    /* An array of linked lists - each element corresponds
    to a vertex and will hold a list of neighbours...*/
    m_neighbours = new list<int>[vertices];
}
 
void Graph::add_edge(int src, int dst)
{
    m_neighbours[src].push_back(dst);
}
 
int Graph::count_paths(int src, int dst, int vertices)
{
    int path_count = 0;
    vector<bool> visited(vertices, false);
    path_counter(src, dst, path_count, visited);
    return path_count;
}
 
/*
 * A recursive function that counts all paths from src to
 * dst. Keep track of the count in the parameter.
 */
void Graph::path_counter(int src, int dst, int& path_count,
                         vector<bool>& visited)
{
    // If we've reached the destination, then increment
    // count...
    visited[src] = true;
    if (src == dst) {
        path_count++;
    }
    // ...otherwise recurse into all neighbours...
    else {
        for (auto neighbour : m_neighbours[src]) {
            if (!visited[neighbour])
                path_counter(neighbour, dst, path_count,
                             visited);
        }
    }
  visited[src] = false;
}
 
// Tests...
int main()
{
    // Create a graph given in the above diagram - see link
    Graph g(5);
    g.add_edge(0, 1);
    g.add_edge(0, 2);
    g.add_edge(0, 4);
    g.add_edge(1, 3);
    g.add_edge(1, 4);
    g.add_edge(2, 3);
    g.add_edge(2, 1);
    g.add_edge(3, 2);
    // Validate it...
    cout << g.count_paths(0, 4, 5);
 
    return 0;
}

// Java program to count all paths from a source
// to a destination.
import java.util.Arrays;
import java.util.Iterator;
import java.util.LinkedList;
 
// This class represents a directed graph using
// adjacency list representation
 
class Graph {
 
    // No. of vertices
    private int V;
 
    // Array of lists for
    // Adjacency List
    // Representation
    private LinkedList<Integer> adj[];
 
    @SuppressWarnings("unchecked") Graph(int v)
    {
        V = v;
        adj = new LinkedList[v];
        for (int i = 0; i < v; ++i)
            adj[i] = new LinkedList<>();
    }
 
    // Method to add an edge into the graph
    void addEdge(int v, int w)
    {
 
        // Add w to v's list.
        adj[v].add(w);
    }
 
    // A recursive method to count
    // all paths from 'u' to 'd'.
    int countPathsUtil(int u, int d, int pathCount)
    {
 
        // If current vertex is same as
        // destination, then increment count
        if (u == d) {
            pathCount++;
        }
 
        // Recur for all the vertices
        // adjacent to this vertex
        else {
            Iterator<Integer> i = adj[u].listIterator();
            while (i.hasNext()) {
                int n = i.next();
                pathCount = countPathsUtil(n, d, pathCount);
            }
        }
        return pathCount;
    }
 
    // Returns count of
    // paths from 's' to 'd'
    int countPaths(int s, int d)
    {
 
        // Call the recursive method
        // to count all paths
        int pathCount = 0;
        pathCount = countPathsUtil(s, d, pathCount);
        return pathCount;
    }
 
    // Driver Code
    public static void main(String args[])
    {
        Graph g = new Graph(5);
        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(0, 3);
        g.addEdge(1, 3);
        g.addEdge(2, 3);
        g.addEdge(1, 4);
        g.addEdge(2, 4);
 
        int s = 0, d = 3;
        System.out.println(g.countPaths(s, d));
    }
}
 
// This code is contributed by shubhamjd.

# Python 3 program to count all paths
# from a source to a destination.
 
# A directed graph using adjacency
# list representation
 
 
class Graph:
 
    def __init__(self, V):
        self.V = V
        self.adj = [[] for i in range(V)]
 
    def addEdge(self, u, v):
 
        # Add v to u’s list.
        self.adj[u].append(v)
 
    # Returns count of paths from 's' to 'd'
    def countPaths(self, s, d):
 
        # Mark all the vertices
        # as not visited
        visited = [False] * self.V
 
        # Call the recursive helper
        # function to print all paths
        pathCount = [0]
        self.countPathsUtil(s, d, visited, pathCount)
        return pathCount[0]
 
    # A recursive function to print all paths
    # from 'u' to 'd'. visited[] keeps track
    # of vertices in current path. path[]
    # stores actual vertices and path_index
    # is current index in path[]
    def countPathsUtil(self, u, d,
                       visited, pathCount):
        visited[u] = True
 
        # If current vertex is same as
        # destination, then increment count
        if (u == d):
            pathCount[0] += 1
 
        # If current vertex is not destination
        else:
 
            # Recur for all the vertices
            # adjacent to current vertex
            i = 0
            while i < len(self.adj[u]):
                if (not visited[self.adj[u][i]]):
                    self.countPathsUtil(self.adj[u][i], d,
                                        visited, pathCount)
                i += 1
 
        visited[u] = False
 
 
# Driver Code
if __name__ == '__main__':
 
    # Create a graph given in the
    # above diagram
    g = Graph(4)
    g.addEdge(0, 1)
    g.addEdge(0, 2)
    g.addEdge(0, 3)
    g.addEdge(2, 0)
    g.addEdge(2, 1)
    g.addEdge(1, 3)
 
    s = 2
    d = 3
    print(g.countPaths(s, d))
 
# This code is contributed by PranchalK

// C# program to count all paths from a source
// to a destination.
using System;
using System.Collections.Generic;
 
// This class represents a directed graph using
// adjacency list representation
public class Graph {
 
    // No. of vertices
    int V;
 
    // Array of lists for
    // Adjacency List
    // Representation
    private List<int>[] adj;
 
    Graph(int v)
    {
        V = v;
        adj = new List<int>[ v ];
        for (int i = 0; i < v; ++i)
            adj[i] = new List<int>();
    }
 
    // Method to add an edge into the graph
    void addEdge(int v, int w)
    {
 
        // Add w to v's list.
        adj[v].Add(w);
    }
 
    // A recursive method to count
    // all paths from 'u' to 'd'.
    int countPathsUtil(int u, int d, int pathCount)
    {
 
        // If current vertex is same as
        // destination, then increment count
        if (u == d) {
            pathCount++;
        }
 
        // Recur for all the vertices
        // adjacent to this vertex
        else {
            foreach(int i in adj[u])
            {
                int n = i;
                pathCount = countPathsUtil(n, d, pathCount);
            }
        }
        return pathCount;
    }
 
    // Returns count of
    // paths from 's' to 'd'
    int countPaths(int s, int d)
    {
 
        // Call the recursive method
        // to count all paths
        int pathCount = 0;
        pathCount = countPathsUtil(s, d, pathCount);
        return pathCount;
    }
 
    // Driver Code
    public static void Main(String[] args)
    {
        Graph g = new Graph(5);
        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(0, 3);
        g.addEdge(1, 3);
        g.addEdge(2, 3);
        g.addEdge(1, 4);
        g.addEdge(2, 4);
 
        int s = 0, d = 3;
        Console.WriteLine(g.countPaths(s, d));
    }
}
 
// This code is contributed by Rajput-Ji

<script>
 
// JavaScript program to count all paths from a source
// to a destination.
 
// No. of vertices
let  V;
 
// Array of lists for
    // Adjacency List
    // Representation
let adj;
 
function Graph(v)
{
    V = v;
        adj = new Array(v);
        for (let i = 0; i < v; ++i)
            adj[i] = [];
}
 
// Method to add an edge into the graph
function addEdge(v,w)
{
    // Add w to v's list.
        adj[v].push(w);
}
 
// A recursive method to count
    // all paths from 'u' to 'd'.
function countPathsUtil(u,d,pathCount)
{
    // If current vertex is same as
        // destination, then increment count
        if (u == d) {
            pathCount++;
        }
  
        // Recur for all the vertices
        // adjacent to this vertex
        else {
             
            for(let i=0;i<adj[u].length;i++) {
                let n = adj[u][i];
                pathCount = countPathsUtil(n, d, pathCount);
            }
        }
        return pathCount;
}
 
// Returns count of
    // paths from 's' to 'd'
function countPaths(s,d)
{
    // Call the recursive method
        // to count all paths
        let pathCount = 0;
        pathCount = countPathsUtil(s, d,
                                   pathCount);
        return pathCount;
}
 
 // Driver Code
Graph(5);
addEdge(0, 1);
addEdge(0, 2);
addEdge(0, 3);
addEdge(1, 3);
addEdge(2, 3);
addEdge(1, 4);
addEdge(2, 4);
 
let s = 0, d = 3;
document.write(countPaths(s, d));
 
 
// This code is contributed by avanitrachhadiya2155
 
</script>

3

Análisis de Complejidad: 

• Complejidad temporal: O(N!). Si el gráfico está completo, ¡puede haber alrededor de N! llamadas recursivas, por lo que la Complejidad de tiempo es O(N!)
• Complejidad espacial: O(1). Ya que no se requiere espacio adicional.