récupérer nombre chemins sur un graphe

**flora806** · 06/10/2009, 14h10

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

**dinobogan** · 06/10/2009, 14h31

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 ?

**flora806** · 06/10/2009, 14h59

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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;
}

**dinobogan** · 07/10/2009, 10h48

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.

**flora806** · 07/10/2009, 13h27

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

**dingoth** · 07/10/2009, 15h55

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.