# 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
5.     public static int empty = -1;
6.
8.     private int numVertices;
9.     private boolean visited[];
10. //    private int distance[];
11.
13.         this.numVertices = numVertices;
14.
16.         for (int i = 0; i < adjMatrix.length; i++) {
17.             for (int j = 0; j < adjMatrix[i].length; j++) {
19.             }
20.         }
21.
22.         visited = new boolean[numVertices];
23.     }
24.
25.
26.     public int getWeight(int i, int j){
28.     }
29.
30.     public void setEdge(int i, int j, int weight) {
32.     }
33.
34.     public void delEdge(int i, int j) {
36.     }
37.
38.     public boolean isEdge(int i, int j) {
40.     }
41.
42.     public int first(int 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){
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) {
205.
206.         // directed graph
207.         Set<EdgeElemnt> edgeElemnts = new HashSet<>();
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