Discussion :

[daliz]

bonjour tout le monde,

J'utilise l'algoithme de dijkstra pour calculer les k-plus courts chemins entre une source et une destination. Il fonctionne correctement.

Maintennat je voudrais calculer des chemins DISJOINTS entre une source et une destination.

Y'aurait -il une version de dijkstra qui fournit un tel résultat?

Merci d'avance

[FrancisSourd]

Il faut définir un peu plus formellement ce que sont les k plus courts chemins distincts (arcs distincts je suppose)
Si les k chemins ont des distances d1 <= d2 <= ... <= dk, on peut minimiser

• max(d_i)=d_k, ou
  la somme des d_i, ou
  l'ordre lexicographique (d_1,d_2,...d_k)

Dans le premier cas (max), trouver k chemins distincts qui sont tous de longueur inférieure à une distance d est NP-complet (je vois une réduction de Partition si cela t'intéresse). Il faudra donc utiliser une approche énumérative.

Dans le deuxième (somme), il me semble que l'on peut modéliser le problème comme un problème de flot de coût minimal en mettant des capacités et des coûts unitaires sur tous les arcs.

Dans le troisième (lexico), on aurait envie de calculer le plus court chemin, d'enlever les arcs de ce chemin, puis le plus court chemin dans le nouveau graphe jusqu'à obtenir k chemins. Par contre, il y a un problème s'il existe plusieurs plus court chemin dans un graphe donné: lequel choisir???

[vivlotel]

bonjour tout le monde,

J'utilise l'algoithme de dijkstra pour calculer les k-plus courts chemins entre une source et une destination. Il fonctionne correctement.

Merci d'avance

Salut tu l'as programmé en quel langage ton algorithme de Dijkstra?
Si c'est du java je suis interessé par tes sources.