Implémentation Java de l'algorithme de Floyd Warshall

Question

J'ai essayé pendant une semaine de trouver un chemin pour travailler sur un jeu sur lequel je travaille. J'utilise this implementation de l'algorithme de Floyd Warshall. Je crois que je suis parvenu à limiter le problème à l'intérieur de cette boucle:

for(int k = 0; k < nodes.length; k++) 
    for(int i = 0; i < nodes.length; i++) 
     for(int j = 0; j < nodes.length; j++) 
      if(D[i][k] != Integer.MAX_VALUE 
      && D[k][j] != Integer.MAX_VALUE 
      && D[i][k] + D[k][j] < D[i][j]){ 
       D[i][j] = D[i][k]+D[k][j]; 
       P[i][j] = nodes[k]; 
      } 

J'ai testé avec 4 nœuds étaient chaque nœud se connecte à tous les autres noeuds et toutes les connexions ont un poids de 1. Voici les valeurs de toutes les variables pertinentes avant la boucle.

for(Node n:nodes)System.out.println(n.pos.toString() + " " + n.index); 

Sortie:

[x: 4, y: 4] 0 
[x: 4, y: 5] 1 
[x: 5, y: 4] 2 
[x: 5, y: 5] 3 

Ceci est comme prévu

for(Edge e:edgeList) 
    System.out.println(e.from.pos.toString() + " " + e.to.pos.toString()); 

Sortie:

[x: 4, y: 4] [x: 5, y: 4] 
[x: 4, y: 4] [x: 4, y: 5] 
[x: 4, y: 4] [x: 5, y: 5] 
[x: 4, y: 5] [x: 4, y: 4] 
[x: 4, y: 5] [x: 5, y: 4] 
[x: 4, y: 5] [x: 5, y: 5] 
[x: 5, y: 4] [x: 4, y: 4] 
[x: 5, y: 4] [x: 4, y: 5] 
[x: 5, y: 4] [x: 5, y: 5] 
[x: 5, y: 5] [x: 4, y: 4] 
[x: 5, y: 5] [x: 5, y: 4] 
[x: 5, y: 5] [x: 4, y: 5] 

Ceci est également comme prévu.

for(int[] ia:D){ 
    for(int a:ia)System.out.print(a + " "); 
    System.out.print("\n"); 
} 

Sortie:

2147483647 1 1 1 
1 2147483647 1 1 
1 1 2147483647 1 
1 1 1 2147483647 

Ceci est également comme prévu.

P = new Node[nodes.length][nodes.length]; 
for(int k = 0; k < nodes.length; k++) 
    for(i = 0; i < nodes.length; i++) 
     for(int j = 0; j < nodes.length; j++) 
      if(D[i][k] != Integer.MAX_VALUE 
      && D[k][j] != Integer.MAX_VALUE 
      && D[i][k]+D[k][j] < D[i][j]){ 
       D[i][j] = D[i][k]+D[k][j]; 
       P[i][j] = nodes[k]; 
       System.out.println(nodes[k].pos.toString() + " " + k); 
      } 

Sortie:

[x: 4, y: 4] 0 
[x: 4, y: 4] 0 
[x: 4, y: 4] 0 
[x: 4, y: 5] 1 

C'est là je pense que le problème est, j'attendais la sortie pour contenir tous les différents nœuds, seuls les deux noeuds trouvés travaillent ici dans la fonction getShortestPath. Je crois que ce serait la sortie correcte de la boucle et l'ordre devrait être hors de propos pour autant que je comprenne. Je n'ai aucune idée de ce qui cause exactement le problème dans la boucle ou si j'ai mal compris quelque chose à propos de l'algorithme.

Answer 1

A partir du résultat:

[x: 4, y: 4] 0 
[x: 4, y: 4] 0 
[x: 4, y: 4] 0 
[x: 4, y: 5] 1 

Je peux presque deviner ce qui est arrivé. Vous avez peut-être initialisé tous D[i][j] à 1 mais D[i][i] à Integer.MAX_VALUE. Donc, la première mise à jour 3 était D[i][i] = D[i][0] + D[i][0] avec k = 0, i = 1..3. Mais D[0][0] peut être mis à jour seulement être d[0][1] + d[1][0].

Votre implémentation de floyd-warshall semble totalement correcte. Peut-être que vous devriez vérifier votre bug dans un autre endroit comme la récupération de la route la plus courte qui est plus défectueuse pour avoir un bug.