número de rutas en el gráfico

Question

¿cómo se puede calcular el número de rutas en un gráfico dirigido? ¿Hay algún algoritmo para este propósito?

mejores deseos

EDITAR: El gráfico no es un árbol.

Answer 1

No creo que haya nada más rápido que atravesar el gráfico, empezando desde la raíz.

En pseudo-código -

visit(node) { 
    node.visited = true; 
    for(int i = 0; i < node.paths.length; ++i) { 
    ++pathCount; 
    if (!node.paths[i].visited) 
     visit(node.paths[i]); 
    } 

} 

Answer 2

Todos los resultados de búsqueda que veo son para el número de caminos de un nodo dado a otro nodo dado. Pero aquí hay un algoritmo que debe encontrar el número total de rutas en cualquier parte del gráfico, para cualquier dígrafo acíclico. (Si hay ciclos, hay un número infinito de caminos a menos que especifique están excluidos que ciertas trayectorias repetitivas.)

etiqueta cada nodo con el número de caminos que terminan en ese nodo:

While not all nodes are labeled: 
    Choose an unlabeled node with no unlabeled ancestors. 
    (An implementation might here choose any node, and recursively 
    process any unlabeled ancestors of that node first.) 
    Label the node with one plus the sum of the labels on all ancestors. 
    (If a node has no ancestors, its label is simply 1.) 

Ahora solo agregue las etiquetas en todos los nodos.

Si no desea contar las rutas de "longitud cero", reste la cantidad de nodos.

Answer 3

Si es realmente un árbol, el número de rutas es igual a la cantidad de nodos-1 si cuenta las rutas a los nodos internos. Si solo cuenta las rutas a las hojas, el número de rutas es igual al número de hojas. Entonces, el hecho de que estamos hablando de árboles simplifica la cuestión simplemente contando nodos o hojas. Un algoritmo BFS o DFS simple será suficiente.

Answer 4

Si el gráfico no es un árbol, habrá infinitos caminos: recorra un ciclo en cualquier momento.

Answer 5

Puede usar depth-first search. Sin embargo, no finaliza la búsqueda cuando encuentra una ruta de inicio a destino, como lo hace normalmente la búsqueda de profundidad-primera. En su lugar, solo agrega al recuento de rutas y regresa de ese nodo como si fuera un callejón sin salida. Probablemente este no sea el método más rápido, pero debería funcionar.

También es posible que utilice una búsqueda amplia, pero luego necesita encontrar la manera de pasar información sobre los recuentos de ruta hacia adelante (o hacia atrás) a través del árbol mientras la busca. Si pudieras hacer eso, probablemente sería mucho más rápido.

Answer 6

Suponiendo que el gráfico es acíclico (un DAG), puede hacer una clasificación topológica de los vértices y hacer una programación dinámica para calcular el número de caminos distintos. Si desea imprimir todas las rutas, no hay mucho uso en la discusión de la notación O grande ya que la cantidad de rutas puede ser exponencial en la cantidad de vértices.

Pseudo-código:

paths := 0 
dp[i] := 0, for all 0 <= i < n 
compute topological sorting and store on ts 
for i from n - 1 to 0 
    for all edges (ts[i], v) // outbound edges from ts[i] 
     dp[ts[i]] := 1 + dp[ts[i]] + dp[v] 
    paths := paths + dp[ts[i]] 

print paths 

Editar: Bug en el código

Answer 7

Deje A ser la matriz de adyacencia de un grafo G. Entonces A^n (es decirA multiplicado n veces con sí mismo) tiene la siguiente propiedad interesante:

La entrada en la posición de (i,j)A^n igual al número de diferentes caminos de longitud n desde el vértice al vértice ij.

Por lo tanto:

• representan el gráfico como una matriz de adyacencia A
• multiplican A con sí mismo varias veces hasta que se aburre
• en cada paso: calcular la suma de todos los elementos de la matriz y agregarlo para el resultado, comenzando en 0

Puede ser conveniente comprobar primero si G contiene un ciclo, porque en este caso contiene infinitamente m cualquier camino Para detectar ciclos, configure todos los pesos de borde a -1 y use Bellman-Ford.

Answer 8

admat da la longitud 1 caminos entre vértices;

admat^2 da la longitud 2 caminos entre vértices;

admat^3 da la longitud 3 rutas entre vértices;

¿Alinee el patrón todavía?