title: Dijkstra's algorithm for longest path
body: <p><strong>EDIT 2: This might be too late, but I figured out the problem, it was me. I misunderstood the project, it asked for the largest bandwidth path not the longest path. which is different but I didn't know until now. So basically in any bandwidth path problem (whether largest or smallest), the weights are not accumulated, the path value is determined by the smallest weight in the path. Think of it as a path of pipes and the water flow is determined by the thinest pipe along the path.</strong></p>
  
  <p><strong>EDIT 1: I fixed the PQ issue, but still not working.</strong></p>
  
  <p>It is an assignment (I admit), but I may fail the whole course if I don't submit it. We are supposed to modify Dijkstra's algorithm to calculate the longest SIMPLE path instead of the shortest path. I couldn't figure out a solution. I searched the Internet and found <a href="http://www.csl.mtu.edu/cs2321/www/newLectures/30_More_Dijkstra.htm" rel="nofollow noreferrer">this</a> (It is even the same problem).</p>
  
  <p>But when I run it, it produces incorrect values. Is there any thing I'm missing ? Why even doesn't it sum the weight with the predecessor ? Why use min ?</p>
  
  <p>Info about the graph:
   1. We generate the graph randomly such that each node is connected to
      about 25% of the other nodes.
   2. Weights are positive.
   3. There are 25 nodes in the graph.</p>
  
  <p>The question says "Routing Algorithm is the algorithm of finding maximum bandwidth path in a graph. It is based on modification of Dijkstra’s algorithm using a Max-Heap structure". Is there any trick in it that may help ?</p>
  
  <pre><code>public class MaxDijkstra {
      Graph graph;
      PriorityQueue&lt;Node&gt; queue;
  
      public MaxDijkstra(Graph graph, Node s){
          this.graph = graph;
          s.addAttribute("ui.class", "start");
          queue = new PriorityQueue&lt;&gt;(new Comparator&lt;Node&gt;(){
              @Override
              public int compare(Node n1, Node n2) {
                  if(Utils.getNodeBW(n1) == Utils.getNodeBW(n2)){
                      return 0;
                  }else if(Utils.getNodeBW(n1) &lt; Utils.getNodeBW(n2)){
                      return 1;
                  }else{
                      return -1;
                  }
              }
          });
  
          // init
          for(Node n : graph){
              Utils.setNodeBW(n, 0);
          }
          Utils.setNodeBW(s, Float.POSITIVE_INFINITY);
  
          // add to Q
          for(Node n : graph){
              queue.add(n);
          }
  
          while(!queue.isEmpty()){
              Node u = queue.remove();
              Iterator&lt;Node&gt; iterator = u.getNeighborNodeIterator();
              while(iterator.hasNext()){
                  Node v = iterator.next();
                  float min = Float.min(Utils.getNodeBW(u), Utils.getEdgeBW(u.getEdgeBetween(v)));
                  if(min &gt; Utils.getNodeBW(v)){
                      Utils.setNodeBW(v, min);
                      Utils.setPreOfNode(v, u);
                  }
              }
  
              // validate PQ
              // I know it is not good, just for debuggin now
              // I will implemnt my own PQ later
              List&lt;Node&gt; list = new ArrayList&lt;&gt;();
              while(!queue.isEmpty()){
                  Node w = queue.remove();
                  list.add(w);
              }
              for(Node w : list){
                  queue.add(w);
              }
          }
      }
  
      public void printInfo(){
          for(Node n : graph){
              System.out.println("N="+n.getId()+" D="+Utils.getNodeBW(n)+" pre="+ (Utils.getPreOfNode(n) == null ? "NIL" : Utils.getPreOfNode(n).getId()) );
          }
      }
  
      /**
       * Just to colourise the path
       * @param target 
       */
      public void backtrack(Node target){
          target.addAttribute("ui.class", "end");
          Node currunt = target;
          Node pre = Utils.getPreOfNode(currunt);
          while(pre != null){
              currunt.getEdgeBetween(pre).addAttribute("ui.class", "route");
              currunt = pre;
              pre = Utils.getPreOfNode(currunt);
          }
      }
  </code></pre>
  
  <p>Sample output:
  <a href="https://i.stack.imgur.com/4bDpR.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/4bDpR.png" alt="Not the highest bandwidth"></a></p>
  
  <p>Thank you all in advance.</p>