uopspop

Untitled

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

×