Comptage du nombre de chemins les plus courts à travers un nœud dans un DAG

Question

Je cherche un algorithme pour compter le nombre de chemins traversant un nœud spécifique dans un DAG (similaire au concept de 'betweenness'), avec les conditions suivantes et contraintes:

Je dois faire le comptage pour un ensemble de nœuds source/destination dans le graphe, et pas tous les nœuds, ie pour un nœud milieu n, je veux savoir combien de chemins distincts sont les plus courts S à l'ensemble des nœuds D passent à travers n (et par distinct, je veux dire tous les deux chemins qui ont au moins un nœud non commun)

Quels sont les algorithmes que vous pourriez suggérer de faire, étant donné que le DAG peut être très grand mais clairsemé dans les bords, et poule Cette préférence n'est pas donnée aux boucles imbriquées profondes sur les nœuds.

Answer 1

Vous pouvez utiliser une première recherche approfondie pour chaque paire de nœuds Src/Dest et voir laquelle d'entre elles a votre nœud donné dans le chemin. Vous devez modifier légèrement la recherche de sorte qu'une fois que vous avez trouvé votre chemin le plus court, vous continuez à vider la file d'attente jusqu'à ce que vous atteigniez un chemin qui vous pousse à augmenter la taille. De cette façon, vous n'êtes pas lié par hasard si plusieurs chemins sont les plus courts. Ce n'est qu'une option avec des graphiques non pondérés, bien sûr.