uopspop

Untitled

Sep 21st, 2019
146
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // shortest path
  2. public class GraphAdjacentMatrix_Dijkstra {
  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(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.         distance[startingVertice] = 0; // initialize first data - from startingVertice to startingVertice
  73.         for (int i = 0; i < this.numVertices; i++) { // process all vertices
  74.             int v = minVertex(); // get the next vertice with the shorted path here
  75.             if (v == empty) return distance;// all vertices are visited
  76.             if (distance[v] == Integer.MAX_VALUE) return distance;
  77.  
  78.             this.visited[v] = true;
  79.  
  80.             for (int neighborV = first(v); neighborV < numVertices; neighborV = next(v, neighborV)) {
  81.                 if (distance[neighborV] > (distance[v] + getWeight(v, neighborV))) {
  82.                     distance[neighborV] = (distance[v] + getWeight(v, neighborV));
  83.                 }
  84.             }
  85.  
  86.         }
  87.  
  88.         return distance;
  89.     }
  90.  
  91.     // find the shorted distance from startingVertice to D so far; this will be our next starting point
  92.     private int minVertex() {
  93.         int nextVWithShortestDistance = empty; // if all vertices are visited
  94.         // initialize v to some unvisited vertex
  95.         int i;
  96.         for (i = 0; i < this.numVertices; i++) {
  97.             if (!visited[i]) {
  98.                 nextVWithShortestDistance = i;
  99.                 break;
  100.             }
  101.         }
  102.         // find the smallest D value
  103.         for (i++; i < this.numVertices; i++) {
  104.             if (!visited[i] && distance[i] < distance[nextVWithShortestDistance]) {
  105.                 nextVWithShortestDistance = i;
  106.             }
  107.         }
  108.  
  109.         return nextVWithShortestDistance;
  110.     }
  111.  
  112.     private void Previsit(boolean[][] graph, int v) {
  113.         System.out.println("Previsit: " + v);
  114.     }
  115.  
  116.     private void Postvisit(boolean[][] graph, int v) {
  117.         System.out.println("Postvisit: " + v);
  118.     }
  119.  
  120.     public String toString() {
  121.         StringBuilder s = new StringBuilder();
  122.         for (int i = 0; i < numVertices; i++) {
  123.             s.append(i + ": ");
  124.             for (int j : adjMatrix[i]) {
  125.                 s.append((i != empty?1:0) + " ");
  126.             }
  127.             s.append("\n");
  128.         }
  129.         return s.toString();
  130.     }
  131.  
  132.     public static void main(String[] args) {
  133.         GraphAdjacentMatrix_Dijkstra gam = new GraphAdjacentMatrix_Dijkstra(8);
  134.  
  135.         // directed graph
  136.         gam.setEdge(1, 2, 10);
  137.         gam.setEdge(1, 3, 3);
  138.         gam.setEdge(1, 4, 20);
  139.         gam.setEdge(2, 4, 5);
  140.         gam.setEdge(3, 2, 2);
  141.         gam.setEdge(3, 5, 15);
  142.         gam.setEdge(4, 5, 11);
  143.  
  144.         int[] distances = gam.dijkstra(1);
  145.         printArray(distances);
  146.  
  147.         System.out.printf("the shortest distance between %d and %d = %d %n", 1, 4, distances[4]);
  148.         System.out.printf("the shortest distance between %d and %d = %d %n", 1, 5, distances[5]);
  149.  
  150.         System.out.println();
  151.     }
  152.  
  153.  
  154.     ////////// UTIL ///////////
  155.  
  156.     private static void printArray(int[] ary){
  157.         for (int i = 0; i < ary.length; i++) {
  158.             System.out.printf("%4d" , ary[i]);
  159.         }
  160.         System.out.println();
  161.     }
  162.  
  163. }
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.

×