Ecrit par Jean-Claude ARBAUT le Decembre 08, 2000 at 10:00:07:
En réponse à: Recherche des plus courts chemin en Matlab écrit par anch_bapar le Decembre 01, 2000 at 16:22:56:
Je ne sais pas si ça va aider, mais voici:
le plus court chemin d'un point à un autre,
dans un graphe à N sommet, peut être trouvé
avec l'algorithme de Dijkstra, en un temps
en O(n^2) je crois.
Pour des détails, consulter un livre d'algorithmique
comme le fameux "Aho, Hopcroft & Ullman".
Pour la partie "matlab", c'est de la
programmation ! On peut implémenter les graphes
sous forme de matrice d'adjacence, i.e.
A(i,j)=la distance de M(i) à M(j), où les M(i)
sont les sommets du graphe. L'algorithme ne
marche pas que pour la distance euclidienne...