Advertisement
Guest User

Dijkstra Algorithm

a guest
Nov 12th, 2017
1,372
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. package dijkstra;
  2.  
  3. import java.util.Iterator;
  4. import java.util.PriorityQueue;
  5.  
  6. public class TestGraphs {
  7.  
  8.     public static void main(String[] args) {
  9.         Graph g = new Graph(5);
  10.        
  11.         System.out.println("Graph:");
  12.         // add Edges
  13.         g.addEdge(0, 1, 5.2f);
  14.         g.addEdge(0, 3, 12.8f);
  15.         g.addEdge(0, 2, 10.3f);
  16.         g.addEdge(1, 3, 5.9f);
  17.         g.addEdge(1, 4, 15.2f);
  18.         g.addEdge(2, 1, 1.5f);
  19.         g.addEdge(2, 3, 2.3f);
  20.         g.addEdge(3, 4, 8.5f);
  21.         g.addEdge(4, 2, 2.7f);
  22.        
  23.         // print Graph
  24.         g.printGraph();
  25.  
  26.         // Dijkstra Shortest Path Algorithm
  27.         System.out.println("Dijkstra Shortest Path:");
  28.         Dijkstra(g, 0);
  29.     }
  30.  
  31.     public static void Dijkstra(Graph g, int startVertex) {
  32.         // for storing distances after removing vertex from Queue
  33.         float[] distances = new float[g.getvCount()];
  34.         // for storing father id's after removing vertex from Queue
  35.         int[] parents = new int[g.getvCount()];
  36.         for (int i = 0; i < g.getvCount(); i++) {
  37.             parents[i] = -1;
  38.         }
  39.  
  40.         // set up vertex queue
  41.         PriorityQueue<Vertex> Q = new PriorityQueue<Vertex>();
  42.         for (int i = 0; i < g.getvCount(); i++) {
  43.             if (i != startVertex) {
  44.                 Q.add(new Vertex(i));
  45.             }
  46.         }
  47.  
  48.         // add startVertex
  49.         Vertex node = new Vertex(startVertex);
  50.         node.setDistance(0);
  51.         Q.add(node);
  52.  
  53.         // loop through all vertices
  54.         while (!Q.isEmpty()) {
  55.             // get vertex with shortest distance
  56.             Vertex u = Q.remove();
  57.             distances[u.getId()] = u.getDistance();
  58.  
  59.             // iterate through all neighbours
  60.             Iterator<Edge> it = g.neighbours(u.getId()).iterator();
  61.             while (it.hasNext()) {
  62.                 Edge e = it.next();
  63.                 Iterator<Vertex> it2 = Q.iterator();
  64.                 while (it2.hasNext()) {
  65.                     Vertex v = it2.next();
  66.                     // check if vertex was visited already
  67.                     if (e.getEndPoint() != v.getId()) {
  68.                         continue;
  69.                     }
  70.                     // check distance
  71.                     if (v.getDistance() > u.getDistance() + e.getWeight()) {
  72.                         v.setDistance(u.getDistance() + e.getWeight());
  73.                         v.setParent(u);
  74.                         parents[v.getId()] = v.getParent().getId();
  75.                     }
  76.                 }
  77.             }
  78.  
  79.         }
  80.        
  81.         // print final shortest paths
  82.         System.out.println("Vertex\tDistance\tParent Vertex");
  83.         for (int i = 0; i < g.getvCount(); i++) {
  84.             System.out.println(i + "\t" + distances[i] + "\t\t" + parents[i]);
  85.         }
  86.  
  87.     }
  88. }
Advertisement
RAW Paste Data Copied
Advertisement