Todos os caminhos com menos de um determinado comprimento em um gráfico direcionado entre dois nós

Contar todos os caminhos possíveis, ou todos os caminhos possíveis com um determinado comprimento, entre dois nós em um gráfico direcionado ou não direcionado é um problema clássico. Atenção deve ser dada a todos os meios, devido aos ciclos possíveis.

Esta questão é um pouco diferente, ou pelo menos eu acho.

ENTRADA: Seja G um gráfico direcionado. G pode ter ciclos e também nós auto-conectados. Seja A (G) a matriz de adjacência de G (com 1 em G _{i, j} se houver um link que vá de i a j e a 0 em caso contrário). Defina T e B dois subconjuntos de nós de G , possivelmente com interseção nula.

RESULTADO: A lista de todos os caminhos de comprimento , no máximo k indo de um nó no T em um nó B . Os caminhos podem conter várias vezes as mesmas arestas, desde que passem do nó de origem para o nó de destino em etapas estritamente inferiores a k + 1.

PERGUNTA: Gostaria de saber qual algoritmo tem melhor desempenho nesta tarefa. Estou tentando desenvolver uma resposta possível com base no fato de que o n-ésimo poder da matriz de adjacência, se computado simbolicamente (com uma variável diferente para cada entrada em vez de 1), mantém traços de todos esses caminhos (e reduz à contagem de caminhos se computado numericamente com 1 nas entradas). Mas eu realmente não sei se essa é a maneira mais rápida de fazer a tarefa (provavelmente não).

CAVEAT: Não estou pedindo o problema da contagem, nem os caminhos mais curtos, o comprimento de um caminho é definido como o número de bordas usadas (contando a repetição). Estou usando R, mas se você preferir, pense sobre isso em qualquer outro idioma! Sinto muito se a questão já foi colocada e resolvida. Obrigado pela ajuda!

informações adicionais: Tentei uma abordagem de séries de potências matriciais (A ^ 3 fornece todos os três caminhos longos, ...) e dfs / bfs. Eu acho que os dois últimos estão longe da otimização, pois não levam em conta que eu estou trabalhando em conjuntos de fontes e destinos e, portanto, faço muito trabalho redundante ...

algorithms graphs search-algorithms shortest-path gvdr
fonte

Olá! Você ainda está interessado em multiplicar as matrizes simbolicamente em R?

Ferdinand.kraft

Sim, embora seja mais parecido com um símbolo simbólico (veja a pergunta no stackoverflow). Obrigado.

precisa saber é o seguinte

Então veja minha resposta no Stackoverflow .

Ferdinand.kraft

Respostas:

Se não estiver faltando algo sobre sua pergunta, você poderá aplicar o truque padrão para reduzir a pergunta sobre várias origens e destinos ao caso de origem única e destino único:

Adicione dois novos nós e , $s$ $t$

Conecte a todas as fontes, $s$

Conecte todos os destinos a . $t$

Após essa redução, estamos na configuração padrão de perguntas com dois vértices extras e queremos encontrar caminhadas de a de comprimento no máximo . $s$ $t$ $s$ $t$ $k+2$

Kaveh
fonte

Como eu não pude ver o truque? Isso é apenas fazer o trabalho, depois de tudo parecer bastante direto.

gvdr

Você também pode usar a abordagem de alimentação de matriz diretamente na matriz de adjacência original: é o número de caminhos de comprimento de a .

(A^{k})_{i j}

$(A^k)_{ij}$

k

$k$

i

$i$

j

$j$

Yuval Filmus

@YuvalFilmus, como disse, não estou contando os caminhos, mas sim encontrando-os. Portanto, não posso simplesmente usar a alimentação de matriz, mas uma versão "string" disso.

Gvdr #

@Yuval Filmus: Yuval está certo! Quando ele se refere ao "número de caminhos", isso não deve ser entendido como a solução do problema de contá-los, mas apenas para saber qual índice observar na matriz de adjacência . Se , pesquise para trás em dfs ou bfs examinando todos os nós se e somente se também é igual a 1

A^{k - 1}

$A^{k-1}$

{(A^{k})}_{i j} = 1

$\left(A^k\right)_{ij}=1$

{(A^{k - 1})}_{i ω} = 1

$\left(A^{k-1}\right)_{i\omega}=1$

{(A^{k - 1})}_{ω j}

$\left(A^{k-1}\right)_{\omega j}$

Carlos Linares López

Desculpe Carlos, eu perdi sua resposta.

gvdr