uopspop

Untitled

Sep 27th, 2019
168
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.util.Comparator;
  2. import java.util.Objects;
  3. import java.util.PriorityQueue;
  4.  
  5. // shortest path
  6. public class GraphAdjacentMatrix_Dijkstra_BFS_MinHeap {
  7.     public static int empty = -1;
  8.  
  9.     private int adjMatrix[][];
  10.     private int numVertices;
  11.     private boolean visited[];
  12.  
  13.     public GraphAdjacentMatrix_Dijkstra_BFS_MinHeap(int numVertices) {
  14.         this.numVertices = numVertices;
  15.  
  16.         adjMatrix = new int[numVertices][numVertices];
  17.         for (int i = 0; i < adjMatrix.length; i++) {
  18.             for (int j = 0; j < adjMatrix[i].length; j++) {
  19.                 adjMatrix[i][j] = empty;
  20.             }
  21.         }
  22.  
  23.         visited = new boolean[numVertices];
  24.     }
  25.  
  26.  
  27.     public int getWeight(int i, int j){
  28.         return adjMatrix[i][j];
  29.     }
  30.  
  31.     public void setEdge(int i, int j, int weight) {
  32.         adjMatrix[i][j] = weight;
  33. //        adjMatrix[j][i] = true; // directed
  34.     }
  35.  
  36.     public void delEdge(int i, int j) {
  37.         adjMatrix[i][j] = empty;
  38. //        adjMatrix[j][i] = false; // directed
  39.     }
  40.  
  41.     public boolean isEdge(int i, int j) {
  42.         return (adjMatrix[i][j] != -1);
  43.     }
  44.  
  45.     public int first(int v1){
  46.         int[] ary = this.adjMatrix[v1];
  47.         int firstNeighborIndex = this.numVertices; // return n if none
  48.         for (int i = 0; i < ary.length; i++) {
  49.             if (ary[i] != empty){
  50.                 firstNeighborIndex = i;
  51.                 break;
  52.             }
  53.         }
  54.         return firstNeighborIndex;
  55.     }
  56.  
  57.     public int next(int v1, int v2){
  58.         int[] ary = this.adjMatrix[v1];
  59.         int nextNeighborIndex = this.numVertices; // return n if none
  60.         for (int i = v2 + 1; i < ary.length; i++) {
  61.             if (ary[i] != empty){
  62.                 nextNeighborIndex = i;
  63.                 break;
  64.             }
  65.         }
  66.         return nextNeighborIndex; // return n if none
  67.     }
  68.  
  69.     // calculate the shortest distances between the startingVertice to all other vertices
  70.     public static int[] dijkstra(int startingVertice, GraphAdjacentMatrix_Dijkstra_BFS_MinHeap gam) {
  71.         // initialize the final result array
  72.         int[] distance = new int[gam.numVertices];
  73.         for (int i = 0; i < distance.length; i++) {
  74.             distance[i] = Integer.MAX_VALUE;
  75.         }
  76.         // the first vertex reached
  77.         distance[startingVertice] = 0; // initialize first data - from startingVertice to each vertice (we will update this whenver we reach a vertex)
  78.  
  79.         // build MinHeap
  80.         PriorityQueue<VElement> minHeap = new PriorityQueue<>(new VElementComparrator());
  81.         for (int i = 0; i < gam.numVertices; i++) {
  82.             minHeap.add(new VElement(i, distance[i]));
  83.         }
  84.  
  85.         while(!minHeap.isEmpty()){
  86.             VElement ve = minHeap.remove(); // newtVertexWithTheMinimumDistance
  87.             if (distance[ve.v] == Integer.MAX_VALUE) return distance; // if the next vertex with the minimum path is not reachable, we can end here noew
  88.  
  89.             gam.visited[ve.v] = true;
  90.  
  91.             // to think about whether it would be shorter if we take advantage the newly oppcupied vertex.
  92.             for (int neighborV = gam.first(ve.v); neighborV < gam.numVertices; neighborV = gam.next(ve.v, neighborV)) {
  93.                 if (distance[neighborV] > (distance[ve.v] + gam.getWeight(ve.v, neighborV))) {
  94.                     int previousDistance = distance[neighborV];
  95.                     distance[neighborV] = (distance[ve.v] + gam.getWeight(ve.v, neighborV));
  96.                     // if this happens, we need to update our minHeap, too
  97.                     minHeap.remove(new VElement(neighborV, previousDistance));// check the overrided equals(...) and hash(...) of VElemnt
  98.                     minHeap.add(new VElement(neighborV, distance[neighborV]));// check the overrided equals(...) and hash(...) of VElemnt
  99.                 }
  100.             }
  101.         }
  102.  
  103. //        for (int i = 0; i < gam.numVertices; i++) { // process all vertices
  104. //            int v = gam.minVertex(distance); // get the next vertice with the shorted path here
  105. //            if (v == empty) return distance;// all vertices are visited
  106. //            if (distance[v] == Integer.MAX_VALUE) return distance; // if the next vertex is not reachable
  107. //
  108. //            gam.visited[v] = true;
  109. //
  110. //            // to think about whether it would be shorter if we take advantage the newly oppcupied vertex.
  111. //            for (int neighborV = gam.first(v); neighborV < gam.numVertices; neighborV = gam.next(v, neighborV)) {
  112. //                if (distance[neighborV] > (distance[v] + gam.getWeight(v, neighborV))) {
  113. //                    distance[neighborV] = (distance[v] + gam.getWeight(v, neighborV));
  114. //                }
  115. //            }
  116. //
  117. //        }
  118.  
  119.         return distance;
  120.     }
  121.  
  122.     // Imagine we convert the length n into n vertices and use BFS;
  123.     // we will be making many redundant waves until we reach a vertex
  124.     // Therefore, this method here is to help us save those steps and find the next vertex right away
  125.     // (we could use minHeap to replace this method)
  126.     //
  127.     // find the shorted distance from startingVertice to D so far; this will be our next starting point
  128.     private int minVertex(int[] distance) {
  129.         int nextVWithShortestDistance = empty; // if all vertices are visited
  130.         // initialize v to some unvisited vertex
  131.         int i;
  132.         for (i = 0; i < this.numVertices; i++) {
  133.             if (!visited[i]) {
  134.                 nextVWithShortestDistance = i;
  135.                 break;
  136.             }
  137.         }
  138.         // find the smallest D value
  139.         for (i++; i < this.numVertices; i++) {
  140.             if (!visited[i] && distance[i] < distance[nextVWithShortestDistance]) {
  141.                 nextVWithShortestDistance = i;
  142.             }
  143.         }
  144.  
  145.         return nextVWithShortestDistance;
  146.     }
  147.  
  148.     private void Previsit(boolean[][] graph, int v) {
  149.         System.out.println("Previsit: " + v);
  150.     }
  151.  
  152.     private void Postvisit(boolean[][] graph, int v) {
  153.         System.out.println("Postvisit: " + v);
  154.     }
  155.  
  156.     public String toString() {
  157.         StringBuilder s = new StringBuilder();
  158.         for (int i = 0; i < numVertices; i++) {
  159.             s.append(i + ": ");
  160.             for (int j : adjMatrix[i]) {
  161.                 s.append((i != empty?1:0) + " ");
  162.             }
  163.             s.append("\n");
  164.         }
  165.         return s.toString();
  166.     }
  167.  
  168.     public static void main(String[] args) {
  169.         GraphAdjacentMatrix_Dijkstra_BFS_MinHeap gam = new GraphAdjacentMatrix_Dijkstra_BFS_MinHeap(8);
  170.  
  171.         // directed graph
  172.         gam.setEdge(1, 2, 10);
  173.         gam.setEdge(1, 3, 3);
  174.         gam.setEdge(1, 4, 20);
  175.         gam.setEdge(2, 4, 5);
  176.         gam.setEdge(3, 2, 2);
  177.         gam.setEdge(3, 5, 15);
  178.         gam.setEdge(4, 5, 11);
  179.  
  180.         int[] distances = dijkstra(1, gam);
  181.         printArray(distances);
  182.         System.out.printf("the shortest distance between %d and %d = %d %n", 1, 1, distances[1]);
  183.         System.out.printf("the shortest distance between %d and %d = %d %n", 1, 2, distances[2]);
  184.         System.out.printf("the shortest distance between %d and %d = %d %n", 1, 3, distances[3]);
  185.         System.out.printf("the shortest distance between %d and %d = %d %n", 1, 4, distances[4]);
  186.         System.out.printf("the shortest distance between %d and %d = %d %n", 1, 5, distances[5]);
  187.  
  188.         System.out.println();
  189.     }
  190.  
  191.  
  192.  
  193.     public static class VElement {
  194.         public Integer v;
  195.         public Integer distanceFromStartToV;
  196.  
  197.         public VElement(Integer v, Integer distanceFromStartToV) {
  198.             this.v = v;
  199.             this.distanceFromStartToV = distanceFromStartToV;
  200.         }
  201.  
  202.         @Override
  203.         public boolean equals(Object obj)
  204.         {
  205.             if(this == obj)
  206.                 return true;
  207.             if(obj == null || obj.getClass()!= this.getClass())
  208.                 return false;
  209.  
  210.             // type casting of the argument.
  211.             VElement ve = (VElement) obj;
  212.             return  (ve.v == this.v);
  213.         }
  214.  
  215.         @Override
  216.         public int hashCode() {
  217.             return Objects.hash(v);
  218.         }
  219.  
  220.     }
  221.  
  222.     public static class VElementComparrator implements Comparator<VElement> {
  223.         @Override
  224.         public int compare(VElement ve1, VElement ve2) {
  225.             return ve1.distanceFromStartToV.compareTo(ve2.distanceFromStartToV);
  226.         }
  227.     }
  228.  
  229.     ////////// UTIL ///////////
  230.  
  231.     private static void printArray(int[] ary){
  232.         for (int i = 0; i < ary.length; i++) {
  233.             System.out.printf("%4d" , ary[i]);
  234.         }
  235.         System.out.println();
  236.     }
  237. }
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×