Discussion :

[laurent_m]

Bonjour à tous
J'ai à résoudre un problème de routage en JAVA
Avec l'algo de Floyd-Warshall en j'ai un problème avec la question de la matrice de distances
Je stocke les liens suivants dans une matrice 2D

Code :

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

1
2
3
4
5
6
7
8
 
0 1
1 2
2 3
3 4
4 5
5 1
6 7

Jutilise le code suivant pour, entre autre, générer la matrice des distances:

Code JAVA :

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
 
for (int v = 0; v < n; v++) {
            matriceDistance[v][v] = INF;
            matriceDesSucc[v][v] = -1;
        }
        for (int i = 0; i < m; i++) {
            int u = liens[i][0];
            int v = liens[i][1];
            matriceDistance[u][v] = 0; //poids
            matriceDesSucc[u][v] = v;
        }
 
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (matriceDistance[i][j] > (matriceDistance[i][k] + matriceDistance[k][j])) {
                        matriceDistance[i][j] = matriceDistance[i][k] + matriceDistance[k][j];
                        matriceDesSucc[i][j] = matriceDesSucc[i][k];
                    }
                }
            }
        }

Mon questionnement se situe à la ligne 8.. Comme calculer le poids d'un lien ?
j'ai cherché partout et dans les exemples ça semble être attribué par hasard....

Éclairez-moi SVP
Merci

[Nico02]

Salut,

Normalement tu dois avec un graphe valué pour pouvoir utiliser Floyd-Warshall. Si ce n'est pas le cas tu peux toujours considérer que toutes tes arrêtes on un poids de 1.

Source Wikipédia

L'algorithme de Floyd-Warshall prend en entrée un graphe orienté et valué (V, E), sous la forme d'une matrice d'adjacence donnant le poids d'un arc lorsqu'il existe et la valeur ∞ sinon. Le poids d'un chemin entre deux sommets est la somme des poids sur les arcs constituant ce chemin.

Dans tous les cas si tu veux des réponses plus précises sur l'algo (qui sortent du cadre de la programmation Java) tu devrais poster sur la Algo du forum, il seront surement plus enclin à te répondre

Cdt.