Conteggio del numero di percorsi più brevi attraverso un nodo in un DAG

Question

Sto cercando un algoritmo per contare il numero di percorsi che attraversano un nodo specifico in un DAG (simile al concetto di "parentela"), con le seguenti condizioni e vincoli:

Ho bisogno di fare il conteggio per un insieme di nodi sorgente/destinazione nel grafico, e non tutti i nodi, cioè per un nodo centrale n, voglio sapere quanti distinti percorsi più brevi dal set di nodi S per set di nodi D passano n (e per distinti, intendo ogni due percorsi che hanno almeno un nodo non comune)

Quali sono gli algoritmi che potresti suggerire di fare, considerando che il DAG può essere molto grande ma rada nei bordi e gallina La preferenza ce non viene data ai loop nidificati profondi sui nodi.

Answer 1

È possibile utilizzare una ricerca di ampiezza per ogni coppia di nodi Src/Dest e vedere quali di questi hanno il nodo dato nel percorso. Dovresti modificare leggermente la ricerca in modo che, una volta individuato il percorso più breve, continui a svuotare la coda finché non raggiungi un percorso che ti fa aumentare le dimensioni. In questo modo non sei legato da casualità se ci sono più percorsi più brevi. Questa è solo un'opzione con grafici non ponderati, ovviamente.