Contents    Page-10    Prev    Next    Page+10    Index   

Dijkstra's Algorithm


public void dijkstra( Vertex s ) {
  for ( Vertex v : vertices ) {
    v.visited = false;
    v.cost = 999999; }
  s.cost = 0;
  s.parent = null;
  PriorityQueue<Vertex>
      fringe = new PriorityQueue<Vertex>(20,
        new Comparator<Vertex>() {
          public int compare(Vertex i, Vertex j) {
              return (i.cost - j.cost); }});
  fringe.add(s);
  while ( ! fringe.isEmpty() ) {
    Vertex v = fringe.remove();  // lowest-cost
    if ( ! v.visited )
      { v.visited = true;
        for ( Edge e : v.edges )
          { int newcost = v.cost + e.cost;
            if ( newcost < e.target.cost )
             { e.target.cost = newcost;
               e.target.parent = v;
               fringe.add(e.target);  } } } } }