récupérer nombre chemins sur un graphe

Version imprimable

Bonjour,

je souhaiterais récupérer le nombre de chemins entre tout couple de sommets sur un graphe. j'utilise l'algo Floyd-Warshall :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 //i et j représentent les sommets départ-arrivée et k les sommets intermédiaires ......... for (k = 0; k < n; k++) { for (i = 0; i < n; i++) { for (j = 0; j < n; j++) { dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]); ....} } }
Comment je pourrais récupérer le nombre de ces chemins?

Merci.

06/10/2009, 15h31
dinobogan

Citation:

Envoyé par flora806

Comment je pourrais récupérer le nombre de ces chemins?

Commence par analyser l'algorithme de Floyd-Warshall. Explique clairement ton problème car je ne vois pas la difficulté.
Quel est pour le moment le résultat de ton programme ?

En fait en entrée de mon programme j'ai une matrice n x n qui contient les poids entre 2 sommets (dist[i][j]=..) et mon objectif est à la fois de chercher le chemin le + court entre les couples de sommets mais aussi de récupérer le nombre de chemins qui les relient .

pour l'instant mon code me permet de récupérer uniquement le poids correspondant au chemin le plus court (dans dist[i][j]) sans le nombre de chemins.
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 public double[][] getMinLenghts() { //i et j représentent les sommets départ-arrivée et k les sommets intermédiaires ......... // n est le nombre des sommets sur le graphe for (k = 0; k < n; k++) { for (i = 0; i < n; i++) { for (j = 0; j < n; j++) { //Algo Floyd Warshall dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]); ....} } } return dist; }

07/10/2009, 11h48
dinobogan

Sans réfléchir beaucoup à ton problème, une méthode récursive devrait permettre de calculer le nombre de chemins. Chaque nouveau points est ajouter dans une liste, qui est dupliquée à chaque carrefour. Si le chemin aboutie à l'arrivée, alors tu ranges cette liste dans la liste des chemins possibles. Par contre, il va falloir ajouter des données dans ta matrice pour marquer les points par lesquels tu es déjà passé. Il faut empêcher les cycles infinis.
07/10/2009, 14h27
flora806

Merci pour ta réponse,
Mais j'ai pas compris, les nouveaux points ce sont les "k"? et c'est quoi le carrefour?
07/10/2009, 16h55
dingoth

Attention, ta demande et tes données n'ont pas grand chose en commun.

Floyd-Warshall permet de découvrir la plus courte distance, tandis que tu désires le nombre de chemins.

Désires-tu compter les cycles également ?

Essaie d'utiliser l'API JGraphT, très intéressante pour tes cas.
07/10/2009, 17h11
dinobogan

Citation:

Envoyé par flora806

Merci pour ta réponse,
Mais j'ai pas compris, les nouveaux points ce sont les "k"? et c'est quoi le carrefour?

Les points, ce sont les sommets. Un carrefour est un sommet qui contient plusieurs arcs vers d'autres sommets.
09/10/2009, 12h31
flora806

Non, en fait je ne veux pas compter les cycles.
j'ai déja une librairie qui implémente Dijkstra et qui donne le nombre de chemins, par contre c'est trèèèès lent au calcul :( c'est pour ça que j'ai pensé à Floyd-Warshall.
Pour info j'ai 800 noeuds.

Citation:

Envoyé par dingoth

Attention, ta demande et tes données n'ont pas grand chose en commun.

Floyd-Warshall permet de découvrir la plus courte distance, tandis que tu désires le nombre de chemins.

Désires-tu compter les cycles également ?

Essaie d'utiliser l'API JGraphT, très intéressante pour tes cas.
09/10/2009, 16h31
dinobogan

Je ne comprends plus du tout ton problème.
Puisque tu veux connaître la liste de tous les chemins possibles, pourquoi utilises-tu un algorithme qui permet de trouver le plus court (ou l'un des plus courts) chemin ?
Il te faut un algo de "force brute" qui va faire toutes les combinaisons possibles, et on en revient à mon idée postée un peu plus haut.
09/10/2009, 16h43
flora806

Oui, t'as raison je dois penser à un autre algo.
Je suis entrain de voir les possibilités de l'API JGraphT proposée par dingoth.
c'est Dijkstra aussi qui y est implémentée, le calcul du nombre de chemins est très lent..:roll:

Citation:

Envoyé par dinobogan

Je ne comprends plus du tout ton problème.
Puisque tu veux connaître la liste de tous les chemins possibles, pourquoi utilises-tu un algorithme qui permet de trouver le plus court (ou l'un des plus courts) chemin ?
Il te faut un algo de "force brute" qui va faire toutes les combinaisons possibles, et on en revient à mon idée postée un peu plus haut.
12/10/2009, 16h20
dinobogan

Citation:

Envoyé par flora806

Oui, t'as raison je dois penser à un autre algo.
Je suis entrain de voir les possibilités de l'API JGraphT proposée par dingoth.
c'est Dijkstra aussi qui y est implémentée, le calcul du nombre de chemins est très lent..:roll:

Mais l'algo de Dijkstra permet de trouver le plus court chemin. Comment fais-tu pour qu'il te trouve tous les chemins possibles, et pas seulement le plus court ?