Algoritmo de gráfico para localizar todas as conexões entre dois vértices arbitrários

Eu estou tentando determinar o melhor algoritmo eficiente de tempo para realizar a tarefa descrita abaixo.

Eu tenho um conjunto de registros. Para este conjunto de registros, tenho dados de conexão que indicam como os pares de registros desse conjunto se conectam uns aos outros. Isso basicamente representa um grafo não direcionado, com os registros sendo os vértices e os dados de conexão nas arestas.

Todos os registros no conjunto têm informações de conexão (ou seja, nenhum registro órfão está presente; cada registro no conjunto se conecta a um ou mais outros registros no conjunto).

Eu quero escolher quaisquer dois registros do conjunto e ser capaz de mostrar todos os caminhos simples entre os registros escolhidos. Por “caminhos simples” quero dizer os caminhos que não têm registros repetidos no caminho (ou seja, apenas caminhos finitos).

Nota: Os dois registros escolhidos serão sempre diferentes (isto é, o vértice inicial e final nunca será o mesmo; nenhum ciclo).

Por exemplo:

     Se eu tiver os seguintes registros:
         A, B, C, D, E

     e o seguinte representa as conexões: 
         (A, B), (A, C), (B, A), (B, D), (B, E), (B, F), (C, A), (C, E),
         (C, F), (D, B), (E, C), (E, F), (F, B), (F, C), (F, E)

         [onde (A, B) significa que o registro A se conecta ao registro B]

Se eu escolhi B como meu registro inicial e E como meu registro final, eu gostaria de encontrar todos os caminhos simples através das conexões de registro que conectariam o registro B ao registro E.

    Todos os caminhos que conectam B a E:
       B-> E
       B-> F-> E
       B-> F-> C-> E
       B-> A-> C-> E
       B-> A-> C-> F-> E

Este é um exemplo, na prática, posso ter conjuntos contendo centenas de milhares de registros.

Parece que isso pode ser feito com uma pesquisa em profundidade do gráfico. A pesquisa em profundidade encontrará todos os caminhos não cíclicos entre dois nós. Esse algoritmo deve ser muito rápido e dimensionar para grandes charts (a estrutura de dados do gráfico é esparsa, portanto, usa apenas a quantidade de memory necessária).

Notei que o gráfico que você especificou acima tem apenas uma borda que é direcional (B, E). Foi um erro de digitação ou é realmente um gráfico direcionado? Esta solução funciona independentemente. Desculpe eu não pude fazer isso em C, sou um pouco fraco nessa área. Espero que você seja capaz de traduzir esse código Java sem muita dificuldade.

Graph.java:

import java.util.HashMap; import java.util.LinkedHashSet; import java.util.LinkedList; import java.util.Map; import java.util.Set; public class Graph { private Map> map = new HashMap(); public void addEdge(String node1, String node2) { LinkedHashSet adjacent = map.get(node1); if(adjacent==null) { adjacent = new LinkedHashSet(); map.put(node1, adjacent); } adjacent.add(node2); } public void addTwoWayVertex(String node1, String node2) { addEdge(node1, node2); addEdge(node2, node1); } public boolean isConnected(String node1, String node2) { Set adjacent = map.get(node1); if(adjacent==null) { return false; } return adjacent.contains(node2); } public LinkedList adjacentNodes(String last) { LinkedHashSet adjacent = map.get(last); if(adjacent==null) { return new LinkedList(); } return new LinkedList(adjacent); } } 

Search.java:

 import java.util.LinkedList; 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"); LinkedList visited = new LinkedList(); visited.add(START); new Search().depthFirst(graph, visited); } private void depthFirst(Graph graph, LinkedList visited) { LinkedList nodes = graph.adjacentNodes(visited.getLast()); // examine adjacent nodes for (String node : nodes) { if (visited.contains(node)) { continue; } if (node.equals(END)) { visited.add(node); printPath(visited); visited.removeLast(); break; } } for (String node : nodes) { if (visited.contains(node) || node.equals(END)) { continue; } visited.addLast(node); depthFirst(graph, visited); visited.removeLast(); } } private void printPath(LinkedList visited) { for (String node : visited) { System.out.print(node); System.out.print(" "); } System.out.println(); } } 

Saída do Programa:

 BEBACEBACFEBFEBFCE 

O Dicionário de Algoritmos e Estruturas de Dados do Instituto Nacional de Padrões e Tecnologia (NIST) lista esse problema como ” todos os caminhos simples” e recomenda uma pesquisa em profundidade . O CLRS fornece os algoritmos relevantes.

Uma técnica inteligente usando Redes de Petri é encontrada aqui

Aqui está o pseudocódigo que eu criei. Este não é um dialeto específico de pseudocódigo, mas deve ser simples o suficiente para ser seguido.

Alguém quer separar isso.

  • [p] é uma lista de vértices que representam o caminho atual.

  • [x] é uma lista de caminhos onde atendem aos critérios

  • [s] é o vértice da fonte

  • [d] é o vértice de destino

  • [c] é o vértice atual (argumento para a rotina PathFind)

Suponha que haja uma maneira eficiente de procurar os vértices adjacentes (linha 6).

      1 PathList [p]
      2 ListOfPathLists [x]
      3 vértice [s], [d]

      4 PathFind (vértice [c])
      5 Adicionar [c] ao final da lista [p]
      6 Para cada vértice [v] adjacente a [c]
      7 Se [v] é igual a [d], então
      8 Salvar lista [p] em [x]
      9 Else If [v] não está na lista [p]
     10 PathFind ([v])
     11 Next Para
     12 Retire a cauda de [p]
     13 retorno

Como a implementação DFS não recursiva existente fornecida nesta resposta parece estar quebrada, deixe-me fornecer uma que realmente funcione.

Eu escrevi isso em Python, porque eu acho muito legível e organizado por detalhes de implementação (e porque ele tem a palavra-chave yield útil para implementar geradores ), mas deve ser bastante fácil de portar para outras linguagens.

 # 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 mantém duas pilhas paralelas: uma contendo os nós anteriores no caminho atual, e uma contendo o índice vizinho atual para cada nó na pilha do nó (para que possamos retomar a iteração através dos vizinhos de um nó quando o colocamos de volta a pilha). Eu poderia ter usado igualmente uma única pilha de pares (nó, índice), mas imaginei que o método de duas pilhas seria mais legível e talvez mais fácil de implementar para usuários de outras linguagens.

Esse código também usa um conjunto visited separado, que sempre contém o nó atual e quaisquer nós na pilha, para permitir que eu verifique com eficiência se um nó já faz parte do caminho atual. Se o seu idioma tiver uma estrutura de dados de "conjunto ordenado" que forneça operações push / pop eficientes semelhantes a uma pilha e consultas de participação eficientes, você poderá usá-lo para a pilha de nós e se livrar do conjunto visited separado.

Como alternativa, se você estiver usando uma class / estrutura mutável personalizada para seus nós, poderá armazenar apenas um sinalizador booleano em cada nó para indicar se ele foi visitado como parte do caminho de pesquisa atual. É claro que este método não permite que você execute duas pesquisas no mesmo gráfico em paralelo, caso queira, por algum motivo, fazer isso.

Aqui está um código de teste demonstrando como a function dada acima funciona:

 # 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) 

A execução deste código no gráfico de exemplo fornecido produz a seguinte saída:

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

Note que, enquanto este grafo de exemplo é undirected (ou seja, todas as suas arestas vão nos dois sentidos), o algoritmo também funciona para charts direcionados arbitrários. Por exemplo, remover a borda C -> B (removendo B da lista vizinha de C ) produz a mesma saída, exceto pelo terceiro caminho ( A -> C -> B -> D ), que não é mais possível.


Ps. É fácil construir charts para os quais algoritmos de pesquisa simples como este (e os outros dados neste thread) têm um desempenho muito baixo.

Por exemplo, considere a tarefa de localizar todos os caminhos de A a B em um grafo não direcionado onde o nó inicial A tem dois vizinhos: o nó de destino B (que não possui outros vizinhos além de A) e um nó C que faz parte de um clique de n nós +1, como este:

 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"), } 

É fácil ver que o único caminho entre A e B é o direto, mas um DFS ingênuo iniciado a partir do nó A desperdiçará O ( n !) Tempo explorando inutilmente os caminhos dentro do grupo, mesmo que seja óbvio (para um humano) nenhum desses caminhos pode levar a B.

Também é possível construir DAGs com propriedades semelhantes, por exemplo, tendo o nó inicial A conectando o nó de destino B e dois outros nós, C 1 e C 2 , os quais se conectam aos nós D 1 e D 2 , ambos conectados a E 1 e E 2 e assim por diante. Para n camadas de nodos organizados desta forma, uma busca ingênua por todos os caminhos de A a B acabará perdendo tempo O (2 n ) examinando todos os possíveis becos sem saída antes de desistir.

Obviamente, adicionar uma borda ao nó de destino B de um dos nós no clique (diferente de C) ou da última camada do DAG criaria um número exponencialmente grande de caminhos possíveis de A para B, e um O algoritmo de busca puramente local não pode dizer antecipadamente se encontrará tal vantagem ou não. Assim, de certo modo, a fraca sensibilidade de saída de tais pesquisas ingênuas se deve à falta de conhecimento da estrutura global do gráfico.

Embora existam vários methods de pré-processamento (como a eliminação iterativa de nós de folhas, a pesquisa de separadores de vértices de nó único, etc.) que poderiam ser usados ​​para evitar alguns desses "deadlines de tempo exponencial", não conheço nenhum general truque de pré-processamento que poderia eliminá-los em todos os casos. Uma solução geral seria verificar, em cada etapa da pesquisa, se o nó de destino ainda está acessível (usando uma sub-pesquisa), e recuar mais cedo, se não estiver - mas, infelizmente, isso diminuiria significativamente a pesquisa (na pior das hipóteses). , proporcionalmente ao tamanho do gráfico) para muitos charts que não contêm tais becos sem saída patológicos.

Aqui está uma versão recursiva logicamente mais atraente em comparação com o segundo andar.

 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> paths = new ArrayList>(); String currentNode = START; List visited = new ArrayList(); visited.add(START); new Search().findAllPaths(graph, seen, paths, currentNode); for(ArrayList path : paths){ for (String node : path) { System.out.print(node); System.out.print(" "); } System.out.println(); } } private void findAllPaths(Graph graph, List visited, List> paths, String currentNode) { if (currentNode.equals(END)) { paths.add(new ArrayList(Arrays.asList(visited.toArray()))); return; } else { LinkedList nodes = graph.adjacentNodes(currentNode); for (String node : nodes) { if (visited.contains(node)) { continue; } List temp = new ArrayList(); temp.addAll(visited); temp.add(node); findAllPaths(graph, temp, paths, node); } } } } 

Saída do programa

 BACEBACFEBE BFCE BFE 

Solução no código C. É baseado no DFS, que usa memory mínima.

 #include  #include  #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); } 

Eu tenho resolvido um problema semelhante a isso recentemente, em vez de todas as soluções que eu estava interessado apenas no mais curto.

Usei uma pesquisa iterativa de ‘amplitude primeiro’ que usava uma fila de status ‘, cada qual contendo um registro contendo um ponto atual no gráfico e o caminho percorrido para chegar lá.

você começa com um único registro na fila, que tem o nó inicial e um caminho vazio.

Cada iteração através do código tira o item do topo da lista, e verifica se é uma solução (o nó que chega é o que você quer, se é, nós terminamos), senão, ele constrói um novo item de fila com os nós conectados ao nó atual e caminhos alterados que são baseados no caminho do nó anterior, com o novo salto anexado no final.

Agora, você poderia usar algo semelhante, mas quando você encontrar uma solução, em vez de parar, adicione essa solução à sua ‘lista encontrada’ e continue.

Você precisa manter o controle de uma lista de nós visitados, para que você nunca volte atrás de você, caso contrário, você terá um loop infinito.

Se você quiser um pouco mais de pseudocódigo, poste um comentário ou algo assim, e eu irei elaborar.

Eu acho que você deveria descrever seu verdadeiro problema por trás disso. Digo isso porque você pede algo eficiente em termos de tempo, mas a resposta ao problema parece crescer exponencialmente!

Portanto, eu não esperaria um algoritmo melhor do que algo exponencial.

Eu faria backtracking e percorrendo todo o gráfico. Para evitar ciclos, salve todos os nós visitados ao longo do caminho. Quando você voltar, desmarque o nó.

Usando recursion:

 static bool[] visited;//all false Stack 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 } 

Ou isso está errado?

edit: Ah, e eu esqueci: você deve eliminar as chamadas recursivas, utilizando essa pilha de nós

O princípio básico é que você não precisa se preocupar com charts. Esse é um problema padrão conhecido como problema de conectividade dinâmica. Existem os seguintes tipos de methods a partir dos quais você pode alcançar nós conectados ou não:

  1. Busca rápida
  2. União Rápida
  3. Algoritmo Aprimorado (Combinação de ambos)

Aqui está o código C que eu tentei com complexidade de tempo mínimo O (log * n) Isso significa que para 65536 lista de arestas, ele requer 4 pesquisa e para 2 ^ 65536, requer 5 pesquisa. Estou compartilhando minha implementação do algoritmo: Curso de Algoritmo da Universidade de Princeton

DICA: Você pode encontrar a solução Java a partir do link compartilhado acima com explicações apropriadas.

 /* Checking Connection Between Two Edges */ #include #include #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; } 

Isso pode ser tarde, mas aqui está a mesma versão C # do algoritmo DFS em Java de Casey para percorrer todos os caminhos entre dois nós usando uma pilha. A legibilidade é melhor com recursiva como sempre.

  void DepthFirstIterative(T start, T endNode) { var visited = new LinkedList(); var stack = new Stack(); 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(); } } 
 Este é um gráfico de amostra para testar:

     // Gráfico de amostra.  Os números são ids de borda
     // 1 3       
     // A --- B --- C ----
     // |  |  2 |
     // |  4 ----- D |
     // ------------------

caminhos_cadinhos [s, t, d, k]

Esta questão é antiga e já foi respondida. No entanto, nenhum mostra talvez um algoritmo mais flexível para realizar a mesma coisa. Então eu vou jogar meu chapéu no ringue.

Eu pessoalmente acho um algoritmo da forma find_paths[s, t, d, k] útil, onde:

  • s é o nó inicial
  • t é o nó de destino
  • d é a profundidade máxima para pesquisar
  • k é o número de caminhos para encontrar

Usando a forma de infinito da sua linguagem de programação para dek lhe dará todos os caminhos.

§ obviamente, se você estiver usando um grafo direcionado e quiser todos os caminhos não direcionados entre s e t você terá que rodar das duas formas:

 find_paths[s, t, d, k]  find_paths[t, s, d, k] 

Função auxiliar

Eu pessoalmente gosto de recursion, embora possa dificultar algumas vezes, de qualquer maneira primeiro vamos definir nossa function auxiliar:

 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() 

Função principal

Com isso fora do caminho, a function principal é trivial:

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

Primeiro, vamos notar uma coisa:

  • o pseudo-código acima é um mash-up de linguagens - mas mais fortemente parecido com python (já que eu estava apenas codificando nele). Um copy-paste estrito não funcionará.
  • [] é uma lista não inicializada, substitua isto pelo equivalente para a sua linguagem de programação preferida
  • paths_found é passado por referência . É claro que a function de recursion não retorna nada. Lide com isso apropriadamente.
  • aqui graph está assumindo alguma forma de estrutura hashed . Há uma infinidade de maneiras de implementar um gráfico. De qualquer forma, o graph[vertex] fornece uma lista de vértices adjacentes em um gráfico direcionado - ajuste de acordo.
  • Isso pressupõe que você tenha pré-processado para remover "fivelas" (auto-loops), ciclos e multi-arestas

Aqui está um pensamento fora do topo da minha cabeça:

  1. Encontre uma conexão. (A pesquisa em profundidade é provavelmente um bom algoritmo para isso, já que o comprimento do caminho não importa.)
  2. Desativar o último segmento.
  3. Tente encontrar outra conexão do último nó antes da conexão desativada anteriormente.
  4. Ir até 2 até que não haja mais conexões.

Tanto quanto eu posso dizer as soluções dadas por Ryan Fox ( 58343 , Christian ( 58444 ), e você mesmo ( 58461 ) são quase tão boas quanto são. Eu não acredito que a travessia em amplitude primeiro ajude neste caso, como você não obtém todos os caminhos.Por exemplo, com arestas (A,B) , (A,C) , (B,C) , (B,D) e (C,D) você obterá caminhos ABD e ACD , mas não ABCD .

Eu encontrei uma maneira de enumerar todos os caminhos, incluindo os infinitos contendo loops.

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

Encontrando Caminhos e Ciclos Atômicos

 Definition 

O que queremos fazer é encontrar todos os caminhos possíveis indo do ponto A ao ponto B. Como há ciclos envolvidos, você não pode simplesmente enumerá-los. Em vez disso, você terá que encontrar um caminho atômico que não faça um loop e os menores ciclos possíveis (você não quer que seu ciclo se repita).

A primeira definição que tirei de um caminho atômico é um caminho que não passa pelo mesmo nó duas vezes. No entanto, descobri que não estava tomando todas as possibilidades. Depois de alguma reflection, descobri que os nós não são importantes, mas as arestas são! Portanto, um caminho atômico é um caminho que não passa pela mesma borda duas vezes.

Esta definição é útil, também funciona para ciclos: um ciclo atômico do ponto A é um caminho atômico que vai do ponto A e termina no ponto A.

Implementação

 Atomic Paths A -> B 

A fim de obter todo o caminho a partir do ponto A, vamos percorrer o gráfico recursivamente a partir do ponto A. Ao passar por uma criança, vamos fazer um link filho -> pai para saber todas as arestas que já cruzou. Antes de irmos para essa criança, devemos percorrer essa linked list e garantir que a borda especificada não tenha sido percorrida.

Quando chegamos ao ponto de destino, podemos armazenar o caminho que encontramos.

 Freeing the list 

Um problema ocorre quando você deseja liberar a linked list. É basicamente uma tree encadeada na ordem inversa. Uma solução seria vincular essa lista e, quando todos os caminhos atômicos forem encontrados, liberar a tree do ponto inicial.

Mas uma solução inteligente é usar uma contagem de referência (inspirada na Garbage Collection). Cada vez que você adiciona um link a um pai, você adiciona um à sua contagem de referência. Então, quando você chega no final de um caminho, você volta para trás e libera enquanto a contagem de referência é igual a 1. Se for mais alto, basta remover um e parar.

 Atomic Cycle A 

Procurar pelo ciclo atômico de A é o mesmo que procurar o caminho atômico de A para A. No entanto, existem várias otimizações que podemos fazer. Primeiro, quando chegamos ao ponto de destino, queremos salvar o caminho apenas se a sum do custo das bordas for negativa: queremos apenas passar por ciclos de absorção.

Como você viu anteriormente, todo o gráfico está sendo percorrido ao procurar um caminho atômico. Em vez disso, podemos limitar a área de busca ao componente fortemente conectado contendo A. Encontrar esses componentes requer uma simples travessia do grafo com o algoritmo de Tarjan.

Combinando Caminhos e Ciclos Atômicos

Neste ponto, temos todos os caminhos atômicos que vão de A para B e todos os ciclos atômicos de cada nó, deixados para nós para organizar tudo para obter o caminho mais curto. A partir de agora, vamos estudar como encontrar a melhor combinação de ciclos atômicos em um caminho atômico.

Como habilmente descrito por alguns dos outros cartazes, o problema em poucas palavras é o de usar um algoritmo de busca em profundidade para pesquisar recursivamente o gráfico para todas as combinações de caminhos entre os nós finais em comunicação.

O próprio algoritmo começa com o nó inicial que você fornece, examina todos os links de saída e progride expandindo o primeiro nó filho da tree de pesquisa que aparece, pesquisando cada vez mais até que um nó de destino seja encontrado ou até encontrar um nó. que não tem filhos.

Em seguida, a pesquisa retrocede, retornando ao nó mais recente que ainda não terminou de explorar.

Eu escrevi sobre este tópico muito recentemente, postando um exemplo de implementação de C ++ no processo.

Adding to Casey Watson’s answer, here is another Java implementation,. Initializing the visited node with the start node.

 private void getPaths(Graph graph, LinkedList visitedNodes) { LinkedList 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(); } }