uopspop

Untitled

Sep 27th, 2019
131
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // shortest path
  2. public class GraphAdjacentMatrix_Dijkstra_BFS {
  3.     public static int empty = -1;
  4.  
  5.     private int adjMatrix[][];
  6.     private int numVertices;
  7.     private boolean visited[];
  8. //    private int distance[];
  9.  
  10.     public GraphAdjacentMatrix_Dijkstra_BFS(int numVertices) {
  11.         this.numVertices = numVertices;
  12.  
  13.         adjMatrix = new int[numVertices][numVertices];
  14.         for (int i = 0; i < adjMatrix.length; i++) {
  15.             for (int j = 0; j < adjMatrix[i].length; j++) {
  16.                 adjMatrix[i][j] = empty;
  17.             }
  18.         }
  19.  
  20.         visited = new boolean[numVertices];
  21. //        distance = new int[numVertices];
  22. //        for (int i = 0; i < distance.length; i++) {
  23. //            distance[i] = Integer.MAX_VALUE;
  24. //        }
  25.     }
  26.  
  27.  
  28.     public int getWeight(int i, int j){
  29.         return adjMatrix[i][j];
  30.     }
  31.  
  32.     public void setEdge(int i, int j, int weight) {
  33.         adjMatrix[i][j] = weight;
  34. //        adjMatrix[j][i] = true; // directed
  35.     }
  36.  
  37.     public void delEdge(int i, int j) {
  38.         adjMatrix[i][j] = empty;
  39. //        adjMatrix[j][i] = false; // directed
  40.     }
  41.  
  42.     public boolean isEdge(int i, int j) {
  43.         return (adjMatrix[i][j] != -1);
  44.     }
  45.  
  46.     public int first(int v1){
  47.         int[] ary = this.adjMatrix[v1];
  48.         int firstNeighborIndex = this.numVertices; // return n if none
  49.         for (int i = 0; i < ary.length; i++) {
  50.             if (ary[i] != empty){
  51.                 firstNeighborIndex = i;
  52.                 break;
  53.             }
  54.         }
  55.         return firstNeighborIndex;
  56.     }
  57.  
  58.     public int next(int v1, int v2){
  59.         int[] ary = this.adjMatrix[v1];
  60.         int nextNeighborIndex = this.numVertices; // return n if none
  61.         for (int i = v2 + 1; i < ary.length; i++) {
  62.             if (ary[i] != empty){
  63.                 nextNeighborIndex = i;
  64.                 break;
  65.             }
  66.         }
  67.         return nextNeighborIndex; // return n if none
  68.     }
  69.  
  70.     // calculate the shortest distances between the startingVertice to all other vertices
  71.     public int[] dijkstra(int startingVertice) {
  72.         // initialize the final result array
  73.         int[] distance = new int[numVertices];
  74.         for (int i = 0; i < distance.length; i++) {
  75.             distance[i] = Integer.MAX_VALUE;
  76.         }
  77.         // the first vertex reached
  78.         distance[startingVertice] = 0; // initialize first data - from startingVertice to each vertice (we will update this whenver we reach a vertex)
  79.  
  80.         for (int i = 0; i < this.numVertices; i++) { // process all vertices
  81.             int v = minVertex(distance); // get the next vertice with the shorted path here
  82.             if (v == empty) return distance;// all vertices are visited
  83.             if (distance[v] == Integer.MAX_VALUE) return distance; // if the next vertex is not reachable
  84.  
  85.             this.visited[v] = true;
  86.  
  87.             // to think about whether it would be shorter if we take advantage the newly oppcupied vertex.
  88.             for (int neighborV = first(v); neighborV < numVertices; neighborV = next(v, neighborV)) {
  89.                 if (distance[neighborV] > (distance[v] + getWeight(v, neighborV))) {
  90.                     distance[neighborV] = (distance[v] + getWeight(v, neighborV));
  91.                 }
  92.             }
  93.  
  94.         }
  95.  
  96.         return distance;
  97.     }
  98.  
  99.     // Imagine we convert the length n into n vertices and use BFS;
  100.     // we will be making many redundant waves until we reach a vertex
  101.     // Therefore, this method here is to help us save those steps and find the next vertex right away
  102.     // (we could use minHeap to replace this method)
  103.     //
  104.     // find the shorted distance from startingVertice to D so far; this will be our next starting point
  105.     private int minVertex(int[] distance) {
  106.         int nextVWithShortestDistance = empty; // if all vertices are visited
  107.         // initialize v to some unvisited vertex
  108.         int i;
  109.         for (i = 0; i < this.numVertices; i++) {
  110.             if (!visited[i]) {
  111.                 nextVWithShortestDistance = i;
  112.                 break;
  113.             }
  114.         }
  115.         // find the smallest D value
  116.         for (i++; i < this.numVertices; i++) {
  117.             if (!visited[i] && distance[i] < distance[nextVWithShortestDistance]) {
  118.                 nextVWithShortestDistance = i;
  119.             }
  120.         }
  121.  
  122.         return nextVWithShortestDistance;
  123.     }
  124.  
  125.     private void Previsit(boolean[][] graph, int v) {
  126.         System.out.println("Previsit: " + v);
  127.     }
  128.  
  129.     private void Postvisit(boolean[][] graph, int v) {
  130.         System.out.println("Postvisit: " + v);
  131.     }
  132.  
  133.     public String toString() {
  134.         StringBuilder s = new StringBuilder();
  135.         for (int i = 0; i < numVertices; i++) {
  136.             s.append(i + ": ");
  137.             for (int j : adjMatrix[i]) {
  138.                 s.append((i != empty?1:0) + " ");
  139.             }
  140.             s.append("\n");
  141.         }
  142.         return s.toString();
  143.     }
  144.  
  145.     public static void main(String[] args) {
  146.         GraphAdjacentMatrix_Dijkstra_BFS gam = new GraphAdjacentMatrix_Dijkstra_BFS(8);
  147.  
  148.         // directed graph
  149.         gam.setEdge(1, 2, 10);
  150.         gam.setEdge(1, 3, 3);
  151.         gam.setEdge(1, 4, 20);
  152.         gam.setEdge(2, 4, 5);
  153.         gam.setEdge(3, 2, 2);
  154.         gam.setEdge(3, 5, 15);
  155.         gam.setEdge(4, 5, 11);
  156.  
  157.         int[] distances = gam.dijkstra(1);
  158.         printArray(distances);
  159.  
  160.         System.out.printf("the shortest distance between %d and %d = %d %n", 1, 4, distances[4]);
  161.         System.out.printf("the shortest distance between %d and %d = %d %n", 1, 5, distances[5]);
  162.  
  163.         System.out.println();
  164.     }
  165.  
  166.  
  167.     ////////// UTIL ///////////
  168.  
  169.     private static void printArray(int[] ary){
  170.         for (int i = 0; i < ary.length; i++) {
  171.             System.out.printf("%4d" , ary[i]);
  172.         }
  173.         System.out.println();
  174.     }
  175.  
  176. }
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.

×