Utilisation de l'algorithme de Floyd-Warshall pour compter le nombre de chemins entre 2 sommets

Question

Étant donné un graphique acyclique dirigé non pondéré, j'essaie d'adapter l'algorithme de Floyd-Warshall pour compter le nombre de chemins entre 2 sommets. Mon code ressemble actuellement à ceci:

pour tout k en 1 à n pour tout i en 1 à n pour tous j en 1 à n = Aij Aij + (Aik * Akij).

Par conséquent, au lieu de vérifier et de remplacer la distance min, je fais ce qui suit:

Nombre de chemins entre (i, j) sans k + (Nombre de chemins i-k * Nombre de chemins de k * j)

Mon tableau final doit avoir le nombre de chemins entre 2 sommets.

Je ne suis pas en mesure de prouver que cela ne me donne pas le nombre de chemins simples entre 2 sommets, mais il n'y a pas de suggestions pour utiliser cette approche ailleurs.

Quelqu'un peut-il fournir un exemple de compteur où cela échoue? PS: Ce n'est pas mon devoir, mais juste un exercice de programmation que j'ai choisi.

Answer 1

Dans un graphe acyclique non pondéré non orienté, il y a au plus 1 chemin entre deux sommets quelconques. S'il y avait plus de chemins distincts, ils créeraient un cycle. (non pertinent après modification de la question)

Pour les graphes orientés, je ne vois pas de problème avec votre algorithme. L'utilisation de l'algorithme modifié de Floyd-Warshall est actuellement mentionnée dans this paper. La raison pour laquelle il n'est pas utilisé est très probablement sa complexité - O (n) par rapport à O (m + n) de this simple approach

Answer 2

Dans le cas du graphique cyclique, vous ne pouvez pas le faire avec le Floyd-Warshall droite algorithme, car le comptage de chemins simples nécessite de garder une trace de l'endroit où vous avez été. La programmation dynamique suppose que l'état calculé n'est fonction que des états de la récurrence, ce qui n'est pas vrai dans ce cas.

Cependant, je ne vois pas pourquoi ce ne fonctionnerait pas. Mais pourquoi utiliser Floyd-Warshall pour calculer seulement deux verticies (il suffit d'utiliser un DFS ou un BFS).