title: Floyd-warshall algorithm
body: <p>i'm currently working on a small towerdefense project in Java and i got stuck with the pathfinding.
  I read a lot about A* dijkstra and such things but i decided that it is probably the best to use Floyd-Warshall for pathfinding (at least it seems to me as its solving the all pair shortest path problem).</p>
  
  <p>Anyway i tried to implement it on my own but it doesn't exactly work as it should.
  i used the code on wikipedia as a start <a href="http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm" rel="nofollow">http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm</a></p>
  
  <p>So here's my Code:</p>
  
  <pre><code>public class MyMap {
  public class MyMapNode {
      // list of neighbour nodes
      public List&lt;MyMapNode&gt; neighbours;
      // Currently no need for this :)
      public int cellX, cellY;
      // NodeIndex for pathreconstruction
      public int index;
      // this value is checked by units on map to decide wether path needs
      // reconstruction
      public boolean isFree = true;
  
      public MyMapNode(int cellX, int cellY, int index) {
          this.cellX = cellX;
          this.cellY = cellY;
          this.index = index;
          neighbours = new ArrayList&lt;MyMapNode&gt;();
      }
  
      public void addNeighbour(MyMapNode neighbour) {
          neighbours.add(neighbour);
      }
  
      public void removeNeighbour(MyMapNode neighbour) {
          neighbours.remove(neighbour);
      }
  
      public boolean isNeighbour(MyMapNode node) {
          return neighbours.contains(node);
      }
  }
  //MapSize
  public static final int CELLS_X = 10;
  public static final int CELLS_Y = 10;
  
  public MyMapNode[][] map;
  
  public MyMap() {
      //Fill Map with Nodes
      map = new MyMapNode[CELLS_X][CELLS_Y];
      for (int i = 0; i &lt; CELLS_X; i++) {
          for (int j = 0; j &lt; CELLS_Y; j++) {
              map[i][j] = new MyMapNode(i, j, j + i * CELLS_Y);
          }
      }
      //-------------------------------------------------
      initNeighbours();
      recalculatePath();
  }
  
  public void initNeighbours() {
      //init neighbourhood without diagonals
      for (int i = 0; i &lt; CELLS_X; i++) {
          for (int j = 0; j &lt; CELLS_Y; j++) {
              int x, y;// untere Grenze
              if (j == 0)
                  y = 0;
              else
                  y = -1;
              if (i == 0)
                  x = 0;
              else
                  x = -1;
              int v, w;// obere Grenze
              if (j == CELLS_Y - 1)
                  w = 0;
              else
                  w = 1;
              if (i == CELLS_X - 1)
                  v = 0;
              else
                  v = 1;
              for (int h = x; h &lt;= v; h++) {
                  if (h != 0)
                      map[i][j].addNeighbour(map[i + h][j]);
              }
              for (int g = y; g &lt;= w; g++) {
                  if (g != 0)
                      map[i][j].addNeighbour(map[i][j + g]);
              }
  
          }
      }
  }
  //AdjacencyMatrix
  public int[][] path = new int[CELLS_X * CELLS_Y][CELLS_X * CELLS_Y];
  //for pathreconstruction
  public MyMapNode[][] next = new MyMapNode[CELLS_X * CELLS_Y][CELLS_X
          * CELLS_Y];
  
  public void initAdjacency() {
      for (int i = 0; i &lt; map.length; i++) {
          for (int j = 0; j &lt; map[0].length; j++) {
              path[i][j] = 1000;
              List&lt;MyMapNode&gt; tmp = map[i][j].neighbours;
              for (MyMapNode m : tmp) {
                  path[m.index][map[i][j].index] = 1;
                  path[map[i][j].index][m.index] = 1;
              }
          }
      }
  }
  
  public void floydWarshall() {
      int n = CELLS_X * CELLS_Y;
      for (int k = 0; k &lt; n; k++) {
          for (int i = 0; i &lt; n; i++) {
              for (int j = 0; j &lt; n; j++) {
                  if (path[i][k] + path[k][j] &lt; path[i][j]) {
                      path[i][j] = path[i][k] + path[k][j];
                      next[i][j] = getNodeWithIndex(k);
                  }
              }
          }
      }
  }
  
  public void recalculatePath() {
      initAdjacency();
      floydWarshall();
  }
  
  public MyMapNode getNextWayPoint(MyMapNode i, MyMapNode j) {
      if (path[i.index][j.index] &gt;=1000)
          return null;
      MyMapNode intermediate = next[i.index][j.index];
      if (intermediate == null)
          return j; /* there is an edge from i to j, with no vertices between */
      else
          return getNextWayPoint(i, intermediate);
  }
  
  public MyMapNode getNodeWithIndex(int k) {
      //for testing purpose,this can be done faster
      for (int i = 0; i &lt; map.length; i++) {
          for (int j = 0; j &lt; map[0].length; j++) {
              if (map[i][j].index == k)
                  return map[i][j];
          }
      }
      return null;
  }
  
  public void removeMapNode(MyMapNode m) {
      //for testing purpose,this can be done faster
      m.isFree = false;
      for (int i = 0; i &lt; map.length; i++) {
          for (int j = 0; j &lt; map[0].length; j++) {
              if (map[i][j].neighbours.contains(m)) {
                  map[i][j].neighbours.remove(m);
              }
          }
      }
  }
  </code></pre>
  
  <p>}</p>
  
  <p>the Floyd-Warshall algorithm is designed to work on a graph so i create one where every node knows its neighbours (which are the nodes it is connected to).</p>
  
  <p>I actually don't now where it goes wrong but it somehow does.
  but at least it looks like the initialization of the adjacency matrix works.</p>
  
  <p>in the floydwarshall function i hoped to get the index of the next node in the next[][] but i only get null or 10/11;</p>
  
  <p>So my question is what am i doing wrong or is my approach wrong at all?
  i hope someone can help me.
  if you need any further information please ask</p>
  
  <p>p.S. sorry for my bad english ;)</p>