algorithme de Warshall (théorie des graphes)

[loulou40]

Bonjour à tous,
J'étudie cet algorithme en ce moment et même si je comprends à peu près l'algo en lui-même, je ne sais pas comment interprêter le résulat qu'il fournit (à savoir, une matrice si je ne me trompe pas)
Si quelqu'un a déjà vu cet algo et sait à quoi il sert concrètement, merci de m'éclairer

[acx01b]

salut apparement il permet simplement de savoir s'il existe un chemin de i à j
et par extension l'algorithme de floyd warshall permet de connaître la valeur du plus court chemin de i à j

l'intéret est simplement de constater que si le plus court chemin de i à j se calcule en O(n²), le plus court chemin de i à j pour tout i,j se calcule en O(n^3) et non pas en O(n^4)

la méthode basique en O(n^4) consiste en:
pour tout i,j calculer le plus court chemin de i à j avec un algo en O(n²)

[damboy]

Serait-ce une version améliorée de l'algorithme de Dijkstra ?

http://fr.wikipedia.org/wiki/Algorithme_de_Dijkstra

[acx01b]

O(n^3) ce n'est pas une amélioration de O(n²)

dijkstra calcule le plus court chemin entre i et j
(floyd) warshall le plus court (l'existence d'un) chemin entre i et j pour tout sommet i et j

[loulou40]

Merci pour vos solutions
Je m'aperçois que je ne comprends pas vraiment la solution de l'algorithme : on part de la matrice d'incidence qu'on modifie puis on fait des opérations sur la matrice de sorte qu'elle ne soit plus composée que de 0 et 1 et à la fin, on a surtout des 1. Peut-on interpréter cette matrice comme donnant tous les chemins possibles entre i et j (défini par les 1 de la matrice finale)?

[acx01b]

oui et non
il y a un 1 dans cette matrice s'il existe un chemin entre i et j (regarde sur wikipedia c'est bien expliqué)

donc on sait que s'il existe un chemin entre i et k, et un chemin entre k et j, alors il existe un chemin entre i et j qui passe par k, mais qui peut très bien passer 2 fois au même endroit

(par exemple on va de i à m, puis de m à k, puis on rebrousse chemin de k à m, puis on va de m à j --> peut-on dire qu'il y a un chemin de i à j qui passe par k ?)

[loulou40]

oui et non
il y a un 1 dans cette matrice s'il existe un chemin entre i et j (regarde sur wikipedia c'est bien expliqué)

donc on sait que s'il existe un chemin entre i et k, et un chemin entre k et j, alors il existe un chemin entre i et j qui passe par k, mais qui peut très bien passer 2 fois au même endroit

(par exemple on va de i à m, puis de m à k, puis on rebrousse chemin de k à m, puis on va de m à j --> peut-on dire qu'il y a un chemin de i à j qui passe par k ?)

je pense que c'est l'algo de (warshall) floyd et pas de warshall...ceci dit, (warshall) floyd utilise warshall...
j'ai regardé l'explication de Wikipedia mais je ne comprend toujours pas le rapport entre ce qui semble être le but de cet algo : trouver les chemins entre tous les sommets et cette matrice qu'on obtient à la fin de l'algo puisqu'on peut dire de cette matrice : s'il existe un chemin entre i et m et m et k, ça veut dire qu'il existe une chaîne entre i et k (pas forcément un chemin).