Bonjour,

J'aurais aimé savoir s'il était possible de trouver un algorithme
calculant tous les plus courts chemins entre toutes les pairs dans un arbre pondéré avec une complexité en O(N)
et si oui pouvait vous détailler comment faire ?

J'ai beaucoup de mal à trouver des informations sur ce sujet.

Je sais que cela est possible en O(N3) avec l'algorithme de Floyd-Warshall
mais que l'on peut réduire cela en O(N²) en faisant N parcours en profondeur ou en largeur puisque cela se fait en O(N) dans un arbre.

Mais je cherche comment le faire en O(N) dans la mesure ou cela est possible.
J'ai pensé à cherche le plus proche ancêtre commun mais il faut le faire pour chaque paire de nœud (ce qui fait beaucoup pour 10 000 nœuds par exemple) .

Merci d'avance !