title: Shortest Path Implementation in Java
body: <p>I'm working with an Adjacency matrix and trying to create a function that finds a shortest path within a graph. I'm trying to modify Prim's algorithm which I used to write a minimal spanning tree function.</p>
  
  <pre><code>public static int shortest(int first, int last)  throws Exception{
                int weight[] = new int[Nodes.length]; //keeps track of the weights of the added edges
                int path[] = new int[Nodes.length];   //keeps track of the nodes in the path
                boolean visited[] = new boolean[Nodes.length];    //keeps track of nodes visited
                int current;
                int total;
                int minWeight;
                int nodes = Nodes.length;
                int i;
  
                for (i=0;i&lt;nodes;i++){    //initialization
                      path[i]=0;
                      visited[i]=false;
                      weight[i]=32767;    //largest short int
                }
  
                current=first;
                weight[current]=0;
                total=1;
                visited[current]=true;
                path[0]=current;
  
                while(total!=nodes){
                      for(i=1;i&lt;nodes;i++){
                          if(AMatrix[current][i] != 0 &amp;&amp; visited[i]==false &amp;&amp; weight[i]&gt;AMatrix[current][i]){     
                                  weight[i]=AMatrix[current][i]; 
                                      path[i]=current;
                          }
                      }
                      minWeight=32767;
                      for(i=1;i&lt;nodes;i++){
                          if(visited[i]==false &amp;&amp; weight[i]&lt;minWeight){
                              minWeight=weight[i];
                              current=i;
                          }
                      }
                      write("current = "+ current);
                      visited[current]=true;
                      total++;
  
                      if(current == last){
                          path[total-1]=current;
                          for(i=1;i&lt;total;i++){
                              write("includes the node "+Nodes[path[i]]); 
                          }
  
                          minWeight=0;
                          int j=1;
                          for(i=2;i&lt;total;i++){
                              write("The weight from "+Nodes[path[j]]+" to "+Nodes[path[i]]+" is "+AMatrix[path[j]][path[i]]);
                              minWeight = minWeight+AMatrix[path[j]][path[i]];
                              write("min weight= "+minWeight);
                              j++;
                          }
                          return minWeight;
                      }
                  }
  
                  return -1;
          }
  </code></pre>
  
  <p>It works with one of the inputs I gave it where I started with the first node, but if I try starting with a different node, it creates a path that connects two nodes that aren't actually connected. I've stared at this for so long, and I can't see why it's doing that. The minimal spanning tree works great, and I thought that this was going to be a simple modification but it's just not working.</p>
  
  <p>I actually think that there's a lot of things wrong with this, such as if I try to print out the elements starting the path array from 0, it will print out the first one twice, so I'm sure I've made lots of mistakes, but that's the one that's being blatantly obvious to me right now.</p>
  
  <p>AMatrix is my adjacency matrix and Nodes is the matrix of each of my nodes. Write is I function I wrote that writes to an output file.</p>