Contando el número de rutas más cortas a través de un nodo en un DAG

Question

Estoy buscando un algoritmo para contar el número de rutas que cruzan un nodo específico en un DAG (similar al concepto de 'betweenness'), con las siguientes condiciones y restricciones:

Necesito hacer el recuento para un conjunto de nodos de origen/destino en el gráfico, y no todos los nodos, es decir, para un nodo medio n, quiero saber cuántas rutas más cortas distintas del conjunto de nodos S para establecer los nodos D pasan por n (y por separado, me refiero a cada dos rutas que tienen al menos un nodo no común)

¿Cuáles son los algoritmos que puede sugerir para hacer esto, considerando que el DAG puede ser muy grande pero escaso en los bordes, y la gallina La preferencia ce no se da a los bucles anidados profundos en los nodos.

Answer 1

Puede utilizar una primera búsqueda de ancho para cada par de nodos Src/Dest y ver cuál de ellos tiene su nodo dado en la ruta. Tendría que modificar la búsqueda ligeramente de modo que una vez que haya encontrado su ruta más corta, continúe vaciando la cola hasta que llegue a una ruta que le haga aumentar el tamaño. De esta forma, no estás sujeto a ninguna posibilidad aleatoria si hay múltiples rutas más cortas. Esta es solo una opción con gráficos no ponderados, por supuesto.