El National Institute of Standards and Technology (NIST) online Dictionary of Algorithms and Data Structures enumera este problema como "all simple paths" y recomienda una búsqueda en profundidad. CLRS suministra los algoritmos relevantes.

Una técnica inteligente usando redes de Petri se encuentra aquí

Aquí está el pseudocódigo que se me ocurrió. Este no es un dialecto de pseudocódigo en particular, pero debe ser lo suficientemente simple de seguir.

Cualquiera quiere separar esto.

• [p] es una lista de vértices que representan la ruta actual.

• [x] es una lista de rutas donde cumplen los criterios

• [s] es el vértice de origen

• [d] es el vértice de destino

• [c] es el vértice actual (argumento al PathFind rutina)

Supongamos que hay una manera eficiente de buscar los vértices adyacentes (línea 6).

     1 PathList [p]
     2 ListOfPathLists [x]
     3 Vertex [s], [d]

     4 PathFind ( Vertex [c] )
     5     Add [c] to tail end of list [p]
     6     For each Vertex [v] adjacent to [c]
     7         If [v] is equal to [d] then
     8             Save list [p] in [x]
     9         Else If [v] is not in list [p]
    10             PathFind([v])
    11     Next For
    12     Remove tail from [p]
    13 Return

Dado que la implementación DFS no recursiva existente dada en esta respuesta parece estar rota, permítanme proporcionar una que realmente funcione.

He escrito esto en Python, porque lo encuentro bastante legible y ordenado por detalles de implementación (y porque tiene la útil palabra clave yield para implementar generadores ), pero debería ser bastante fácil de portar a otros lenguajes.

# a generator function to find all simple paths between two nodes in a
# graph, represented as a dictionary that maps nodes to their neighbors
def find_simple_paths(graph, start, end):
    visited = set()
    visited.add(start)

    nodestack = list()
    indexstack = list()
    current = start
    i = 0

    while True:
        # get a list of the neighbors of the current node
        neighbors = graph[current]

        # find the next unvisited neighbor of this node, if any
        while i < len(neighbors) and neighbors[i] in visited: i += 1

        if i >= len(neighbors):
            # we've reached the last neighbor of this node, backtrack
            visited.remove(current)
            if len(nodestack) < 1: break  # can't backtrack, stop!
            current = nodestack.pop()
            i = indexstack.pop()
        elif neighbors[i] == end:
            # yay, we found the target node! let the caller process the path
            yield nodestack + [current, end]
            i += 1
        else:
            # push current node and index onto stacks, switch to neighbor
            nodestack.append(current)
            indexstack.append(i+1)
            visited.add(neighbors[i])
            current = neighbors[i]
            i = 0

Este código mantiene dos pilas paralelas: una que contiene nodos anteriores en la ruta actual, y uno que contiene el índice vecino actual para cada nodo en la pila de nodos (para que podamos reanudar la iteración a través de los vecinos de un nodo cuando lo sacamos de la pila). Podría haber utilizado igualmente una sola pila de pares (nodo, índice), pero pensé que el método de dos pilas sería más legible, y quizás más fácil de implementar para los usuarios de otros idiomas.

Este código también utiliza un conjunto separado visited, que siempre contiene el nodo actual y cualquier nodo en la pila, para permitirme comprobar eficientemente si un nodo ya es parte de la ruta actual. Si su lenguaje tiene una estructura de datos de" conjunto ordenado " que proporciona tanto operaciones push/pop eficientes similares a la pila como consultas de membresía eficientes, puede usar eso para la pila de nodos y deshacerse del conjunto visited separado.

Alternativamente, si está utilizando una clase / estructura mutable personalizada para sus nodos, puede almacenar una bandera booleana en cada nodo para indicar si se ha visitado como parte de la ruta de búsqueda actual. Por supuesto, este método no le permitirá ejecutar dos búsquedas en el mismo gráfico en paralelo, si por alguna razón desea hacer eso.

Aquí hay un código de prueba que demuestra cómo funciona la función dada anteriormente:

# test graph:
#     ,---B---.
#     A   |   D
#     `---C---'
graph = {
    "A": ("B", "C"),
    "B": ("A", "C", "D"),
    "C": ("A", "B", "D"),
    "D": ("B", "C"),
}

# find paths from A to D
for path in find_simple_paths(graph, "A", "D"): print " -> ".join(path)

Ejecutar este código en el gráfico de ejemplo dado produce la siguiente salida:

A -> B -> C -> D
A -> B -> D
A -> C -> B -> D
A -> C -> D

Tenga en cuenta que, mientras que este gráfico de ejemplo no está dirigido (es decir, todos sus bordes van en ambos sentidos), el el algoritmo también funciona para gráficos dirigidos arbitrarios. Por ejemplo, eliminar el borde C -> B (eliminando B de la lista vecina de C) produce la misma salida excepto para el tercer camino (A -> C -> B -> D), que ya no es posible.

Ps. Es fácil construir gráficos para los que los algoritmos de búsqueda simples como este (y los otros dados en este hilo) funcionan muy mal.

Por ejemplo, considere la tarea de encontrar todas las rutas de A a B en un gráfico donde el nodo inicial A tiene dos vecinos: el nodo de destino B (que no tiene otros vecinos que A) y un nodo C que es parte de una clique de n + 1 nodos, así:

graph = {
    "A": ("B", "C"),
    "B": ("A"),
    "C": ("A", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O"),
    "D": ("C", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O"),
    "E": ("C", "D", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O"),
    "F": ("C", "D", "E", "G", "H", "I", "J", "K", "L", "M", "N", "O"),
    "G": ("C", "D", "E", "F", "H", "I", "J", "K", "L", "M", "N", "O"),
    "H": ("C", "D", "E", "F", "G", "I", "J", "K", "L", "M", "N", "O"),
    "I": ("C", "D", "E", "F", "G", "H", "J", "K", "L", "M", "N", "O"),
    "J": ("C", "D", "E", "F", "G", "H", "I", "K", "L", "M", "N", "O"),
    "K": ("C", "D", "E", "F", "G", "H", "I", "J", "L", "M", "N", "O"),
    "L": ("C", "D", "E", "F", "G", "H", "I", "J", "K", "M", "N", "O"),
    "M": ("C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "N", "O"),
    "N": ("C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "O"),
    "O": ("C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N"),
}

Es fácil ver que el único camino entre A y B es el directo, pero un DFS ingenuo iniciado desde el nodo A perderá O(n!) tiempo inútilmente explorando caminos dentro de la camarilla, a pesar de que es obvio (para un humano) que ninguno de esos caminos puede conducir a B.

También se puede construir DAGs con propiedades similares, por ejemplo, haciendo que el nodo inicial A conecte el nodo de destino B y a otros dos nodos C₁ y C₂, ambos se conectan a los nodos D₁ y D₂, ambos se conectan a E₁ y E₂, y así sucesivamente. Para n capas de nodos dispuestos de esta manera, una búsqueda ingenua de todas las rutas de A a B terminará perdiendo O(2ⁿ) tiempo de examen todos los posibles callejones sin salida antes de rendirse.

Por supuesto, agregar una arista al nodo de destino B desde uno de los nodos de la camarilla (que no sea C), o desde la última capa del DAG, crearía un número exponencialmente grande de posibles rutas de A a B, y un algoritmo de búsqueda puramente local realmente no puede decir de antemano si encontrará dicha arista o no. Por lo tanto, en cierto sentido, la pobre sensibilidad de salida de tales búsquedas ingenuas se debe a su falta de conocimiento de la estructura global del gráfico.

Mientras que hay varios métodos de preprocesamiento (como la eliminación iterativa de nodos hoja, la búsqueda de separadores de vértices de un solo nodo, etc.) que podría ser utilizado para evitar algunos de estos" callejones sin salida de tiempo exponencial", no conozco ningún truco de preprocesamiento general que pueda eliminarlos en todos los casos. Una solución general sería comprobar en cada paso de la búsqueda si el nodo de destino sigue siendo accesible (utilizando un sub-búsqueda), y retroceder temprano si no lo es - pero por desgracia, eso ralentizaría significativamente la búsqueda (en el peor de los casos, proporcionalmente al tamaño del gráfico) para muchos gráficos que no contienen tales callejones sin salida patológicos.

Aquí hay una versión recursiva lógicamente mejor en comparación con el segundo piso.

public class Search {

private static final String START = "B";
private static final String END = "E";

public static void main(String[] args) {
    // this graph is directional
    Graph graph = new Graph();
    graph.addEdge("A", "B");
    graph.addEdge("A", "C");
    graph.addEdge("B", "A");
    graph.addEdge("B", "D");
    graph.addEdge("B", "E"); // this is the only one-way connection
    graph.addEdge("B", "F");
    graph.addEdge("C", "A");
    graph.addEdge("C", "E");
    graph.addEdge("C", "F");
    graph.addEdge("D", "B");
    graph.addEdge("E", "C");
    graph.addEdge("E", "F");
    graph.addEdge("F", "B");
    graph.addEdge("F", "C");
    graph.addEdge("F", "E");
    List<ArrayList<String>> paths = new ArrayList<ArrayList<String>>();
    String currentNode = START;
    List<String> visited = new ArrayList<String>();
    visited.add(START);
    new Search().findAllPaths(graph, seen, paths, currentNode);
    for(ArrayList<String> path : paths){
        for (String node : path) {
            System.out.print(node);
            System.out.print(" ");
        }
        System.out.println();
    }   
}

private void findAllPaths(Graph graph, List<String> visited, List<ArrayList<String>> paths, String currentNode) {        
    if (currentNode.equals(END)) { 
        paths.add(new ArrayList(Arrays.asList(visited.toArray())));
        return;
    }
    else {
        LinkedList<String> nodes = graph.adjacentNodes(currentNode);    
        for (String node : nodes) {
            if (visited.contains(node)) {
                continue;
            } 
            List<String> temp = new ArrayList<String>();
            temp.addAll(visited);
            temp.add(node);          
            findAllPaths(graph, temp, paths, node);
        }
    }
}
}

Salida del programa

B A C E 

B A C F E 

B E

B F C E

B F E 

Solución en código C. Se basa en DFS que utiliza memoria mínima.

#include <stdio.h>
#include <stdbool.h>

#define maxN    20  

struct  nodeLink
{

    char node1;
    char node2;

};

struct  stack
{   
    int sp;
    char    node[maxN];
};   

void    initStk(stk)
struct  stack   *stk;
{
    int i;
    for (i = 0; i < maxN; i++)
        stk->node[i] = ' ';
    stk->sp = -1;   
}

void    pushIn(stk, node)
struct  stack   *stk;
char    node;
{

    stk->sp++;
    stk->node[stk->sp] = node;

}    

void    popOutAll(stk)
struct  stack   *stk;
{

    char    node;
    int i, stkN = stk->sp;

    for (i = 0; i <= stkN; i++)
    {
        node = stk->node[i];
        if (i == 0)
            printf("src node : %c", node);
        else if (i == stkN)
            printf(" => %c : dst node.\n", node);
        else
            printf(" => %c ", node);
    }

}


/* Test whether the node already exists in the stack    */
bool    InStack(stk, InterN)
struct  stack   *stk;
char    InterN;
{

    int i, stkN = stk->sp;  /* 0-based  */
    bool    rtn = false;    

    for (i = 0; i <= stkN; i++)
    {
        if (stk->node[i] == InterN)
        {
            rtn = true;
            break;
        }
    }

    return     rtn;

}

char    otherNode(targetNode, lnkNode)
char    targetNode;
struct  nodeLink    *lnkNode;
{

    return  (lnkNode->node1 == targetNode) ? lnkNode->node2 : lnkNode->node1;

}

int entries = 8;
struct  nodeLink    topo[maxN]    =       
    {
        {'b', 'a'}, 
        {'b', 'e'}, 
        {'b', 'd'}, 
        {'f', 'b'}, 
        {'a', 'c'},
        {'c', 'f'}, 
        {'c', 'e'},
        {'f', 'e'},               
    };

char    srcNode = 'b', dstN = 'e';      

int reachTime;  

void    InterNode(interN, stk)
char    interN;
struct  stack   *stk;
{

    char    otherInterN;
    int i, numInterN = 0;
    static  int entryTime   =   0;

    entryTime++;

    for (i = 0; i < entries; i++)
    {

        if (topo[i].node1 != interN  && topo[i].node2 != interN) 
        {
            continue;   
        }

        otherInterN = otherNode(interN, &topo[i]);

        numInterN++;

        if (otherInterN == stk->node[stk->sp - 1])
        {
            continue;   
        }

        /*  Loop avoidance: abandon the route   */
        if (InStack(stk, otherInterN) == true)
        {
            continue;   
        }

        pushIn(stk, otherInterN);

        if (otherInterN == dstN)
        {
            popOutAll(stk);
            reachTime++;
            stk->sp --;   /*    back trace one node  */
            continue;
        }
        else
            InterNode(otherInterN, stk);

    }

        stk->sp --;

}


int    main()

{

    struct  stack   stk;

    initStk(&stk);
    pushIn(&stk, srcNode);  

    reachTime = 0;
    InterNode(srcNode, &stk);

    printf("\nNumber of all possible and unique routes = %d\n", reachTime);

}

He resuelto un problema similar a este recientemente, en lugar de todas las soluciones que solo estaba interesado en el más corto.

Utilicé una búsqueda iterativa de 'amplitud primero' que usó una cola de estado' cada uno de los cuales contenía un registro que contenía un punto actual en el gráfico y el camino tomado para llegar allí.

Comienza con un solo registro en la cola, que tiene el nodo de inicio y una ruta vacía.

Cada iteración a través del código quita el elemento del encabezado de la lista, y comprueba si es una solución (el nodo al que se llega es el que se desea, si lo es, hemos terminado), de lo contrario, construye un nuevo elemento de cola con los nodos conectándose al nodo actual, y rutas modificadas que se basan en la ruta del nodo anterior, con el nuevo salto adjunto al final.

Ahora, podría usar algo similar, pero cuando encuentre una solución, en lugar de detenerse, agregue esa solución a su 'lista encontrada' y continúe.

Es necesario realizar un seguimiento de un visitado lista de nodos, para que nunca retrocedas sobre ti mismo, de lo contrario tendrás un bucle infinito.

Si quieres un poco más de pseudocódigo, publica un comentario o algo, y te lo explicaré.

Creo que debería describir su verdadero problema detrás de esto. Digo esto porque pides algo eficiente en el tiempo, ¡sin embargo, la respuesta al problema parece crecer exponencialmente!

Por lo tanto, no esperaría un algoritmo mejor que algo exponencial.

Haría retroceder y pasar por todo el gráfico. Para evitar ciclos, guarde todos los nodos visitados en el camino. Cuando regreses, desmarca el nodo.

Usando recursión:

static bool[] visited;//all false
Stack<int> currentway; initialize empty

function findnodes(int nextnode)
{
if (nextnode==destnode)
{
  print currentway 
  return;
}
visited[nextnode]=true;
Push nextnode to the end of currentway.
for each node n accesible from nextnode:
  findnodes(n);
visited[nextnode]=false; 
pop from currenteay
}

O es que mal?

Editar: Oh, y me olvidé: Debe eliminar las llamadas recursivas utilizando esa pila de nodos

El principio básico es que no necesita preocuparse por los gráficos.Este es un problema estándar conocido como problema de conectividad dinámica. Existen los siguientes tipos de métodos desde los que puede lograr que los nodos estén conectados o no:

1. Búsqueda rápida
2. Unión rápida
3. Algoritmo mejorado (Combinación de ambos)

Aquí está El Código C Que he probado con complejidad de tiempo mínimo O (log * n) Que significa para 65536 lista de bordes, requiere 4 búsqueda y para 2^65536, requiere 5 búsqueda. Estoy compartiendo mi implementación del algoritmo: Curso de Algoritmo de la universidad de Princeton

CONSEJO: Puede encontrar la solución Java desde el enlace compartido anteriormente con las explicaciones adecuadas.

/* Checking Connection Between Two Edges */

#include<stdio.h>
#include<stdlib.h>
#define MAX 100

/*
  Data structure used

vertex[] - used to Store The vertices
size - No. of vertices
sz[] - size of child's
*/

/*Function Declaration */
void initalize(int *vertex, int *sz, int size);
int root(int *vertex, int i);
void add(int *vertex, int *sz, int p, int q);
int connected(int *vertex, int p, int q);

int main() //Main Function
{ 
char filename[50], ch, ch1[MAX];
int temp = 0, *vertex, first = 0, node1, node2, size = 0, *sz;
FILE *fp;


printf("Enter the filename - "); //Accept File Name
scanf("%s", filename);
fp = fopen(filename, "r");
if (fp == NULL)
{
    printf("File does not exist");
    exit(1);
}
while (1)
{
    if (first == 0) //getting no. of vertices
    {
        ch = getc(fp);
        if (temp == 0)
        {
            fseek(fp, -1, 1);
            fscanf(fp, "%s", &ch1);
            fseek(fp, 1, 1);
            temp = 1;
        }
        if (isdigit(ch))
        {
            size = atoi(ch1);
            vertex = (int*) malloc(size * sizeof(int));     //dynamically allocate size  
            sz = (int*) malloc(size * sizeof(int));
            initalize(vertex, sz, size);        //initialization of vertex[] and sz[]
        }
        if (ch == '\n')
        {
            first = 1;
            temp = 0;
        }
    }
    else
    {
        ch = fgetc(fp);
        if (isdigit(ch))
            temp = temp * 10 + (ch - 48);   //calculating value from ch
        else
        {
            /* Validating the file  */

            if (ch != ',' && ch != '\n' && ch != EOF)
            {
                printf("\n\nUnkwown Character Detected.. Exiting..!");

                exit(1);
            }
            if (ch == ',')
                node1 = temp;
            else
            {
                node2 = temp;
                printf("\n\n%d\t%d", node1, node2);
                if (node1 > node2)
                {
                    temp = node1;
                    node1 = node2;
                    node2 = temp;
                }

                /* Adding the input nodes */

                if (!connected(vertex, node1, node2))
                    add(vertex, sz, node1, node2);
            }
            temp = 0;
        }

        if (ch == EOF)
        {
            fclose(fp);
            break;
        }
    }
}

do
{
    printf("\n\n==== check if connected ===");
    printf("\nEnter First Vertex:");
    scanf("%d", &node1);
    printf("\nEnter Second Vertex:");
    scanf("%d", &node2);

    /* Validating The Input */

    if( node1 > size || node2 > size )
    {
        printf("\n\n Invalid Node Value..");
        break;
    }

    /* Checking the connectivity of nodes */

    if (connected(vertex, node1, node2))
        printf("Vertex %d and %d are Connected..!", node1, node2);
    else
        printf("Vertex %d and %d are Not Connected..!", node1, node2);


    printf("\n 0/1:  ");

    scanf("%d", &temp);

} while (temp != 0);

free((void*) vertex);
free((void*) sz);


return 0;
}

void initalize(int *vertex, int *sz, int size) //Initialization of graph
{
int i;
for (i = 0; i < size; i++)
{
    vertex[i] = i;
    sz[i] = 0;
}
}
int root(int *vertex, int i)    //obtaining the root
{
while (i != vertex[i])
{
    vertex[i] = vertex[vertex[i]];
    i = vertex[i];
}
return i;
}

/* Time Complexity for Add --> logn */
void add(int *vertex, int *sz, int p, int q) //Adding of node
{
int i, j;
i = root(vertex, p);
j = root(vertex, q);

/* Adding small subtree in large subtree  */

if (sz[i] < sz[j])
{
    vertex[i] = j;
    sz[j] += sz[i];
}
else
{
    vertex[j] = i;
    sz[i] += sz[j];
}

}

/* Time Complexity for Search -->lg* n */

int connected(int *vertex, int p, int q) //Checking of  connectivity of nodes
{
/* Checking if root is same  */

if (root(vertex, p) == root(vertex, q))
    return 1;

return 0;
}

Esto puede ser tarde, pero aquí está la misma versión en C# del algoritmo DFS en Java de Casey para recorrer todas las rutas entre dos nodos utilizando una pila. La legibilidad es mejor con recursivo como siempre.

    void DepthFirstIterative(T start, T endNode)
    {
        var visited = new LinkedList<T>();
        var stack = new Stack<T>();

        stack.Push(start);

        while (stack.Count != 0)
        {
            var current = stack.Pop();

            if (visited.Contains(current))
                continue;

            visited.AddLast(current);

            var neighbours = AdjacentNodes(current);

            foreach (var neighbour in neighbours)
            {
                if (visited.Contains(neighbour))
                    continue;

                if (neighbour.Equals(endNode))
                {
                    visited.AddLast(neighbour);
                    printPath(visited));
                    visited.RemoveLast();
                    break;
                }
            }

            bool isPushed = false;
            foreach (var neighbour in neighbours.Reverse())
            {
                if (neighbour.Equals(endNode) || visited.Contains(neighbour) || stack.Contains(neighbour))
                {
                    continue;
                }

                isPushed = true;
                stack.Push(neighbour);
            }

            if (!isPushed)
                visited.RemoveLast();
        }
    }

This is a sample graph to test:

    // Sample graph. Numbers are edge ids
    //       1     3       
    //    A --- B --- C ----
    //    |     |  2       |
    //    | 4   ----- D    |
    //    ------------------

Find_paths [s, t, d, k]

Esta pregunta es antigua y ya ha sido respondida. Sin embargo, ninguno muestra tal vez un algoritmo más flexible para lograr lo mismo. Así que tiraré mi sombrero al ring.

Personalmente encuentro útil un algoritmo de la forma find_paths[s, t, d, k], donde:

• s es el nodo inicial
• t es el nodo de destino
• d es la profundidad máxima a buscar
• k es el número de rutas a encontrar

Usando su programación la forma de infinito del lenguaje para d y k te dará todos los caminos§.

§ obviamente, si está utilizando un gráfico dirigido y desea que todas las rutas no dirigidas entre s y t tendrá que ejecutar esto en ambos sentidos:

find_paths[s, t, d, k] <join> find_paths[t, s, d, k]

Función auxiliar

Personalmente me gusta la recursión, aunque puede ser difícil algunas veces, de todos modos primero vamos a definir nuestra función helper:

def find_paths_recursion(graph, current, goal, current_depth, max_depth, num_paths, current_path, paths_found)
  current_path.append(current)

  if current_depth > max_depth:
    return

  if current == goal:
    if len(paths_found) <= number_of_paths_to_find:
      paths_found.append(copy(current_path))

    current_path.pop()
    return

  else:
    for successor in graph[current]:
    self.find_paths_recursion(graph, successor, goal, current_depth + 1, max_depth, num_paths, current_path, paths_found)

  current_path.pop()

Función principal

Con eso fuera del camino, el núcleo la función es trivial:

def find_paths[s, t, d, k]:
  paths_found = [] # PASSING THIS BY REFERENCE  
  find_paths_recursion(s, t, 0, d, k, [], paths_found)

Primero, notemos algunas cosas: {[16]]}

• el pseudo-código anterior es una mezcla de lenguajes-pero muy parecido a python (ya que yo estaba codificando en él). Un copy-paste estricto no funcionará.
• [] es una lista no inicializada, reemplace esto con el equivalente para su lenguaje de programación de elección
• paths_found se pasa por referencia. Está claro que la función de recursión no devuelve nada. Manejar esto apropiadamente.
• aquí graph está asumiendo alguna forma de estructura hashed. Hay una gran cantidad de formas de implementar un gráfico. De cualquier manera, graph[vertex] obtiene una lista de vértices adyacentes en un gráfico dirigido - ajuste en consecuencia.
• esto supone que ha pre-procesado para eliminar "hebillas" (auto-bucles), ciclos y multi-aristas

Aquí está un pensamiento de la parte superior de mi cabeza:

1. Encuentra una conexión. (La búsqueda en profundidad es probablemente un buen algoritmo para esto, ya que la longitud de la ruta no importa.)
2. Deshabilita el último segmento.
3. Intente encontrar otra conexión desde el último nodo antes de la conexión previamente desactivada.
4. Goto 2 hasta que no haya más conexiones.

Por lo que puedo decir las soluciones dadas por Ryan Fox (58343, Christian (58444), y a ti mismo (58461) son casi lo mejor que se puede. No creo que el recorrido por la anchura primero ayude en este caso, ya que no obtendrá todos los caminos. Por ejemplo, con los bordes (A,B), (A,C), (B,C), (B,D) y (C,D) obtendrá caminos ABD y ACD, pero no ABCD.

Encontré una manera de enumerar todos los caminos incluyendo los infinitos que contienen bucles.

Http://blog.vjeux.com/2009/project/project-shortest-path.html

Encontrar Rutas y Ciclos Atómicos

Definition

Lo que queremos hacer es encontrar todos los caminos posibles que van desde el punto A al punto B. Como hay ciclos involucrados, no puedes simplemente ir y enumerarlos todos. En su lugar, usted tendrá que encontrar la ruta atómica que no bucle y lo más pequeño posible ciclos (no quieres que tu ciclo se repita).

La primera definición que tomé de un camino atómico es un camino que no pasa por el mismo nodo dos veces. Sin embargo, descubrí que no estaba tomando todas las posibilidades. Después de un poco de reflexión, me di cuenta de que los nodos no son importantes, sin embargo los bordes son! Así que un camino atómico es un camino que no pasa por el mismo borde dos veces.

Esta definición es útil, también funciona para ciclos: un ciclo atómico del punto A es un camino atómico que va desde el punto A y termina en el punto A.

Aplicación

Atomic Paths A -> B

Para obtener toda la ruta a partir del punto A, vamos a atravesar el gráfico recursivamente desde el punto A. Mientras pasamos por un hijo, vamos a hacer un enlace hijo -> padre para conocer todos los bordes que ya hemos cruzado. Antes de ir a ese hijo, debemos recorrer esa lista enlazada y asegurarnos de que el borde especificado no haya sido ya recorrido.

Cuando al llegar al punto de destino, podemos almacenar el camino que encontramos.

Freeing the list

Se produce un problema cuando se desea liberar la lista vinculada. Es básicamente un árbol encadenado en el orden inverso. Una solución sería vincular dos veces esa lista y cuando se hayan encontrado todas las rutas atómicas, liberar el árbol desde el punto de partida.

Pero una solución inteligente es usar un conteo de referencia (inspirado en la Recolección de Basura). Cada vez que agrega un enlace a un padre, agrega uno a su recuento de referencias. Entonces, cuando llegas al final de un camino, vas hacia atrás y libre mientras el recuento de referencia es igual a 1. Si es más alto, solo quita uno y detente.

Atomic Cycle A

Buscar el ciclo atómico de A es lo mismo que buscar el camino atómico de A a A. Sin embargo, hay varias optimizaciones que podemos hacer. En primer lugar, cuando llegamos al punto de destino, queremos guardar el camino solo si la suma del costo de los bordes es negativa: solo queremos pasar por ciclos absorbentes.

Como usted tiene visto anteriormente, todo el gráfico está siendo atravesado cuando se busca un camino atómico. En su lugar, podemos limitar el área de búsqueda al componente fuertemente conectado que contiene A. Encontrar estos componentes requiere una simple travesía del gráfico con el algoritmo de Tarjan.

Combinando Trayectorias Atómicas y Ciclos

En este punto, tenemos todos los caminos atómicos que van de A a B y todos los ciclos atómicos de cada nodo, que nos quedan para organizar todo para obtener el camino más corto. A partir de ahora vamos a estudiar cómo encontrar la mejor combinación de ciclos atómicos en una trayectoria atómica.

Como hábilmente descrito por algunos de los otros carteles, el problema en pocas palabras es el de usar un algoritmo de búsqueda en profundidad para buscar recursivamente en el gráfico todas las combinaciones de rutas entre los nodos finales que se comunican.

El algoritmo en sí comienza con el nodo de inicio que se le da, examina todos sus enlaces salientes y progresa expandiendo el primer nodo hijo del árbol de búsqueda que aparece, buscando progresivamente más y más profundo hasta que se encuentre un nodo de destino, o hasta que se encuentra con un nodo que no tiene hijos.

La búsqueda retrocede, volviendo al nodo más reciente que aún no ha terminado de explorar.

Yo blogueé sobre este mismo tema hace poco, publicando un ejemplo de implementación de C++ en el proceso.

Añadiendo a la respuesta de Casey Watson, aquí hay otra implementación de Java,. Inicialización del nodo visitado con el nodo de inicio.

private void getPaths(Graph graph, LinkedList<String> visitedNodes) {
                LinkedList<String> adjacent = graph.getAdjacent(visitedNodes.getLast());
                for(String node : adjacent){
                    if(visitedNodes.contains(node)){
                        continue;
                    }
                    if(node.equals(END)){
                        visitedNodes.add(node);
                        printPath(visitedNodes);
                        visitedNodes.removeLast();
                    }
                    visitedNodes.add(node);
                    getPaths(graph, visitedNodes);
                    visitedNodes.removeLast();  
                }
            }