ShortestPaths.java

//Dijkstrin algoritem za drevo najkrajsih poti
 
public class ShortestPaths {
 
  class DijkstraVertex extends VertexAdj implements HeapPosNode {
    boolean visited;
    DijkstraVertex parent;
    double distance ;
    int heapIndex ;
 
    public int compareTo(Object v) {
      return Double.compare(distance, ( (DijkstraVertex) v).distance);
    }
    public Comparable getKey() {
      return new Double(distance) ;
    }
    public void setKey(Comparable k) {
      distance = ((Double)k).doubleValue();
    }
    public int getHeapIndex() {
      return heapIndex ;
    }
    public void setHeapIndex(int idx) {
      heapIndex = idx ;
    }
  }
 
  public void dijkstra(DijkstraVertex a, DiGraph g) {
    //  rezultat sta za vsako vozlisce 'parent' in 'distance'
    PQDecrease q = new HeapPos(); // prioritetna vrsta vozlisc urejena po distance
    Edge e; // trenutna povezava
    DijkstraVertex v, w ; // trenutno vozlisce in njegov naslednik
 
    // nobeno vozlisce se ni v prioritetni vrsti
    for (DijkstraVertex t = (DijkstraVertex)g.firstVertex();  t!= null ;
          t = (DijkstraVertex)g.nextVertex(t))
        t.visited = false;
    // pripravi zacetno vozlisce in prioritetno vrsto
    a.visited = true;
    a.parent = null;
    a.distance = 0.0 ;
    q.insert(a);
    // glavna zanka: dokler ne dodamo v drevo vseh vozlisc
    while (!q.empty()) {
      v = (DijkstraVertex)q.deleteMin();
      e = g.firstEdge(v);
      while (e != null) {
        w = (DijkstraVertex)g.endPoint(e); // naslednik vozlisca v
        if (!w.visited) {
          // uredi w in dodaj v prioritetno vrsto
          w.visited = true;
          w.parent = v;
          w.distance = v.distance + ((Double)e.evalue).doubleValue() ;
          q.insert(w);
        }
        else if (v.distance + ((Double)e.evalue).doubleValue() < w.distance) {
          // nova, krajsa pot do w
          w.parent = v;
          q.decreaseKey(w,  new Double(v.distance + ((Double)e.evalue).doubleValue()));
        }
        e = g.nextEdge(v, e);
      } // while e
    } // while !empty
  } // Dijkstra
 
 
  public void breadthFirstSearch(DijkstraVertex a, DiGraph g) throws Exception{
    //  rezultat sta za vsako vozlisce 'parent' in 'distance'
    Queue q = new QueueLinked(); // vrsta vozlisc implicitno urejena po distance
    Edge e; // trenutna povezava
    DijkstraVertex v, w ; // trenutno vozlisce in njegov naslednik
 
    // nobeno vozlisce se ni v prioritetni vrsti
    for (DijkstraVertex t = (DijkstraVertex)g.firstVertex();  t!= null ;
          t = (DijkstraVertex)g.nextVertex(t))
        t.visited = false;
    // pripravi zacetno vozlisce in vrsto
    a.visited = true;
    a.parent = null;
    a.distance = 0.0 ;
    q.enqueue(a);
    // glavna zanka: dokler ne dodamo v drevo vseh vozlisc
    while (!q.empty()) {
      v = (DijkstraVertex)q.front();
      q.dequeue();
      e = g.firstEdge(v);
      while (e != null) {
        w = (DijkstraVertex)g.endPoint(e); // naslednik vozlisca v
        if (!w.visited) {
          // uredi w in dodaj v prioritetno vrsto
          w.visited = true;
          w.parent = v;
          w.distance = v.distance + 1 ;
          q.enqueue(w);
        }
        e = g.nextEdge(v, e);
      } // while e
    } // while !empty
  } // Dijkstra
 
 
  public void printShortestPathGraph(DiGraph g) {
     for (DijkstraVertex v = (DijkstraVertex)g.firstVertex(); v != null; v = (DijkstraVertex)g.nextVertex(v))
       if (v.parent != null)
         System.out.println(v.value + "(" + v.distance + ") <- " + v.parent.value);
       else System.out.println(v.value + "(" + v.distance + ") <- null");
   }
 
  public DijkstraVertex dijkstraVertex() {
    return new DijkstraVertex() ;
  }
 
  public static void main(String[] args) throws Exception{
    ShortestPaths sp = new ShortestPaths();
    DiGraph g = new DiGraphAdj() ;
   // primer: mrezni diagram s slike 54
   DijkstraVertex va[] = new DijkstraVertex[7] ;
   for (int i = 0 ; i < va.length ; i++) {
     va[i] = sp.dijkstraVertex();
     va[i].value = new String(Integer.toString(i)) ;
     g.insertVertex(va[i]);
   }
   g.insertEdge(va[0],va[1]);
   g.firstEdge(va[0]).evalue = new Double(11) ;
   g.insertEdge(va[0],va[2]);
   g.firstEdge(va[0]).evalue = new Double(17) ;
   g.insertEdge(va[0],va[3]);
   g.firstEdge(va[0]).evalue = new Double(27) ;
   g.insertEdge(va[1],va[2]);
   g.firstEdge(va[1]).evalue = new Double(15) ;
   g.insertEdge(va[1],va[3]);
   g.firstEdge(va[1]).evalue = new Double(9) ;
   g.insertEdge(va[2],va[3]);
   g.firstEdge(va[2]).evalue = new Double(13) ;
   g.insertEdge(va[2],va[4]);
   g.firstEdge(va[2]).evalue = new Double(38) ;
   g.insertEdge(va[3],va[5]);
   g.firstEdge(va[3]).evalue = new Double(16) ;
   g.insertEdge(va[3],va[6]);
   g.firstEdge(va[3]).evalue = new Double(3) ;
   g.insertEdge(va[4],va[5]);
   g.firstEdge(va[4]).evalue = new Double(7) ;
   g.insertEdge(va[6],va[5]);
   g.firstEdge(va[6]).evalue = new Double(34) ;
 
   System.out.println("Graph:") ;
   g.printGraph();
 
   System.out.println("Shortest paths graph:") ;
   sp.dijkstra(va[0], g) ;
   sp.printShortestPathGraph(g) ;
   System.out.println("Breath first search graph:") ;
   sp.breadthFirstSearch(va[0], g) ;
   sp.printShortestPathGraph(g) ;
  }
}