algoritmo para encontrar el número de trayectorias distintas en un grafo dirigido

Duplicar posible:
Graph Algorithm To Find All Connections Between Two Arbitrary Vertices algoritmo para encontrar el número de trayectorias distintas en un grafo dirigido

Tengo un grafo dirigido, lo algoritmo puedo usar para encontrar el número de distinta rutas acíclicas entre 2 vértices particulares, y contar el máximo de veces que se utiliza una ruta en estas rutas distintas? Dos caminos son distintos si visitan un número diferente de vértices o visitan vértices en un orden diferente.

Fuente

2009-10-29 Pranav

En mi opinión Esto no tiene porque ser un duplicado. Existe una diferencia entre conocer el número de valores (entero) y conocer todos los valores (un conjunto de listas de nodos). Para mi propósito, incluso una estimación razonable del número (límite superior) está bien, así que para mí esto no es un duplicado. – danatel

[Algoritmo de gráfico para buscar todas las conexiones entre dos vértices arbitrarios] (http://stackoverflow.com/q/58306) no es un duplicado en absoluto: enumerar y contar son problemas diferentes, y un gráfico dirigido es una bestia diferente de un gráfico no dirigido. En cuanto a la complejidad de contar caminos simples, consulte [¿Qué tan difícil es contar el número de caminos simples entre dos nodos en un gráfico dirigido?] (Http://cs.stackexchange.com/q/423) en [cs.se]. – Gilles

Estoy de acuerdo con Danatel: para gráficos grandes, no es deseable contar una enumeración de todas las rutas posibles. –

Si sigue un algoritmo de Dijkstra ligeramente modificado, puede tener una solución para todos los pares.

Explicación: Caminos de u a v es la suma de los siguientes:

Caminos u-v que no pasa a través de w
caminos que pasan por w = número de caminos de u a wveces cantidad de rutas de w a v

Inicialice la matriz con ceros, excepto cuando hay un borde de i a j (que es 1). A continuación, el siguiente algoritmo le dará el resultado (todo-par-path-count)

for i = 1 to n: 
    for j = 1 to n: 
     for k = 1 to n: 
      paths[i][i] += paths[i][k] * paths[k][j]

No hace falta decir: O(n^3)

Con ganas de leer una solución de un solo par. :)

Fuente

2009-10-29 09:08:38 ThisIsMeMoony

Esta solución no trata correctamente el requisito de que las rutas no tengan ciclos. – hugomg

Este es un Bellman-Ford modificado, no un Dijkstra modificado (de ahí el problema del ciclo). –

algoritmo para encontrar el número de trayectorias distintas en un grafo dirigido

Respuesta

Cuestiones relacionadas