Bonjour tout le monde, bon voila j'ai suivi cela :
http://fr.wikipedia.org/wrg/wiki/Algorithme_de_Dijkstra

---
Déjà j'ai une question à propos des algo, c'est quoi ça :
sigma [(m+n)* ln(n)] ?
Je connais la fonction ln bien entendu hein, et aussi sigma(des souvenirs qui disaient que c'est négligeable...mais heu là dans le cas d'un algo pour savoir sa complexité.. Ca ne me parle pas du tout)
---
Ensuite j'ai sur le wiki qu'on pouvait utiliser les tas de fibonnachi(je suis allé voir sur le wiki tas de fibonnachi), cependant cela ne me parle pas du tout, je ne vois pas comment on pourrait l'utiliser dans le cas de dijkstra... : s Après si c'est trop compliqué à expliquer en un post, pas grave, oublié. C'est plus par curiosité que j'aimerais rajouter cela et non par nécessité, mais si je ne peux pas cela n'est pas bien grave.

Merci d'avance et au revoir. ^^

salut a toi expert hydra,

Personnellement je n'ai jamais vu la notation sigma[...] dans un contexte de complexite. A mon avis l'auteur de la page wikipedia francaise a fumee, la page anglais est ecrite en notation O(). (Si c'est une notation qui existe vraiment, dites le moi, ca m'interesse.)

La notation O((n+m)log(n)) veut dire que quand n et m sont grand, le temps de calcul ne grandit pas plus vite que c(n+m)log(n) pour une constante c precise. en bref, en bref, si tu double n et m, alors le temps de calcul n'augmente pas plus que d'un facteur 2log(2).

Comment cette complexite est obtenu vient de l'algorithme lui meme. En bref, dans dijkstra, tu fais deux type d'operation, tu extrais le noeud de poids minimum et ensuite tu "relache" chaque arete. La relaxation d'une arete revient a mettre a jour le poids d'un noeud. En bref, tu fais n recherche de minimum et m mise a jour. les deux sont sur des ensembles de taille n. Donc la complexite est O(n*minimum(n)+m*miseajour(n)). Tu peux implementer ces operation minimum et miseajour de plein de facon differente.

La facon al plus simple est d'utiliser un tableau de taille n pour stocker les valeures, tu scanes pour chercher le minimum en O(n). Et tu ecris directement a la bonne position pour mettre a jour en O(1). Donc si tu implemet dijkstra dans un tableau, la complexite est de O(n*n+m*1) = O(n^2).

Apres utiliser un tableau n'est pas forcement la meilleur facon de faire. Et c'est en cela que les tas de fibonacci sont utile. Ils permettent d'implementer les operations minimum et miseajour efficacement. En particulier, minimum est implemente en O(log(n)) et miseajour est implementer en O(1). (NB: c'est en fait un calcul de complexite amortie, mais je pense qu'aujourd'hui tu t'en fous.)

Est ce plus clair maintenant?

Erik

D'accord je comprends, merci encore ^^ Et oui c'est exactement cela pour le tableau.

Rebonjour, bon j'up le topic vu que je viens de me poser une question sur l'algo (et je n'ai pas spécialement envie de tout péter, ou alors de créer un bug dans un cas que je n'aurais pas pensé....) :

-En fait j'ai un tableau qui donne les distances entre les points(et si ils sont reliés ou pas, "Matrices des arcs orientés"), et bref je crée l'autre tableau qui correspond à l'algorithme de dijkstra, cependant je fais TOUTES les lignes du tableau sans exception, au lieu de faire toutes les lignes, est ce que c'est bon(ie correct, crée pas de bug..) si j'arrête l'algo une fois que le noeud d'arrivée est fixé ?(c'est à dire souligné si vous préférez comme dans http://fr.wikipedia.org/wg/wiki/Algorithme_de_Dijkstra)

Parce que je compte juste utiliser l'algo pour trouver le plus court chemin entre 2 points(savoir les noeuds dans lequels je dois passer pour aller d'un point à un autre), rien d'autre m'intéresse.

D'ailleurs, petite remarque mais j'adorais pouvoir tester des cas automatiquement au lieu à chaque fois que je veux tester un cas de taper manuellement toute la matrice des arcs orientés... Mais bon, cela m'a l'air bien trop complexe à réaliser.

expert]hydra, il suffit en effet d'arreter l'algo une fois que le noeud de destination est pop-e de la file de priorite.

Si tu veux des graphes que tu peux utiliser pour tester ton algo, tu en as plein de disponible en ligne. Dans mes projets de graphes, j'utilise typiquement les graphes de SNAP comme exemple. http://snap.stanford.edu/data/index.html

En particulier il y a des reseau routier. Mais je ne sais pas si ils contiennent des coordonnes ou des distance sur les arcs. Sinon tu peux essayer d'extraire l'information de open street map et construire les chemin les plus court dans ta ville.

Tiens et je viens de voir passer ca.

http://linuxfr.org/news/liberation-de-navitia-un-calculateur-d-itineraire-pour-les-transports-en-communs

Woh parfait merci je vais aller voir ça ! Rapide la réponse en plus.
Va falloir que je me motive à essayer de faire ces files de priorité, vu que ça a l'air d'accélérer encore plus l'algorithme..