'lut,
 
j'ai codé un TP des plus courts chemins il y a un bon moment maintenant et google m'a rappelé qu'il ne fallait pas de boucles dans le graphe...
 
je cherche un algo calculant le plus court chemin mais sachant se défaire de boucles présentes dans le graphes.
 
si vous me répondez 'A*', bah va falloir que je creuse alors car je n'ai pas tout capté dans l'exemple que j'avais.
 
ah. autre point, je cherche un algo assez rapide car il sera utilisé en parallèle très souvent (simu de trafic au sol dans un aéroport)
 

cas général : le graphe orienté, pondéré.
les boucles ne gènent en rien le pb... le seul problème pour les boucles, c'est qu'il n'y a pas toujours de solution théorique pour un graphe qui admet des pondération négatives... mais pour une simu de traffic, le cas ne se pose pas !

donc pour toi Dijkstra passe ?
je vais continuer de toute façon mon analyse...

 
1) ton graphe est-il entierement pondere ?, si oui utilise djikstra : algorithme rapide mais avec explosion memoire si ton graphe est trop connecte/a beaucoup de noeud
 
2) Si non entierement pondere, tu utilises A* : tu dois faire comme djikstra mais il faut utilise en plus une estimation du cout heuristique vers le noeud de destination
 
A toi de faire le choix correspondant !
 
EDIT : les 2 methodes sont optimales

A* est une bonne idée! sur les distances (je suppose que c'est de distance que l'on parle) le vol-d'oiseau est très efficace comme heuristique. Il va couper plein de branches.
Je vote A* (Dijsktra, ça serait dommage)
Et oui les deux méthodes donne le plus court chemin.

 
1) il ne peut en exister d'autre de toute facon pour un calcul de distance
 
2) Il ne s'agit pas de voter, il s'agit de faire le bon choix en fonction du probleme ! Les methodes admettent exactement la meme complexite...et meme A* est un peu plus lent du fait qu'il a en plus a estimer un cout heuristique !

Voilà le cours de ma penser :
Il veut un plus court chemin : Dijsktra, il le veut sur des distances donc heuristique = vol d'oiseau, très peu cher, donc le surcout de A* sera facilement rentabilisé

j'étais parti sur d'autres parties de mon projet mais je viens d'y revenir
 
mes datas sont prêtes... je n'ai plus qu'à...
 
je partais en effet sur du A* après réflexion. sur le fait que c'est un peu plus lent, ce n'est pas grave car mes objets sont des threads qui peuvent prendre le temps de calculer leur chemin.
 
edit: par "rapide" dans le premier post, je voulais dire pas affamé en CPU mais c'est ok maintenant, ils sont threadés.
 
pour vos réflexion sur le sujet.
 
je reviendrai avec des interrogations quand mes p'tits avions bougeront tout seuls