Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.*;
- // shortest path
- public class GraphAdjacentMatrix_BellmanFord {
- public static int empty = -1;
- private int adjMatrix[][];
- private int numVertices;
- private boolean visited[];
- // private int distance[];
- public GraphAdjacentMatrix_BellmanFord(int numVertices) {
- this.numVertices = numVertices;
- adjMatrix = new int[numVertices][numVertices];
- for (int i = 0; i < adjMatrix.length; i++) {
- for (int j = 0; j < adjMatrix[i].length; j++) {
- adjMatrix[i][j] = empty;
- }
- }
- visited = new boolean[numVertices];
- }
- public int getWeight(int i, int j){
- return adjMatrix[i][j];
- }
- public void setEdge(int i, int j, int weight) {
- adjMatrix[i][j] = weight;
- }
- public void delEdge(int i, int j) {
- adjMatrix[i][j] = empty;
- }
- public boolean isEdge(int i, int j) {
- return (adjMatrix[i][j] != -1);
- }
- public int first(int v1){
- int[] ary = this.adjMatrix[v1];
- int firstNeighborIndex = this.numVertices; // return n if none
- for (int i = 0; i < ary.length; i++) {
- if (ary[i] != empty){
- firstNeighborIndex = i;
- break;
- }
- }
- return firstNeighborIndex;
- }
- public int next(int v1, int v2){
- int[] ary = this.adjMatrix[v1];
- int nextNeighborIndex = this.numVertices; // return n if none
- for (int i = v2 + 1; i < ary.length; i++) {
- if (ary[i] != empty){
- nextNeighborIndex = i;
- break;
- }
- }
- return nextNeighborIndex; // return n if none
- }
- // calculate the shortest distances between the startingVertice to all other vertices
- public static int[] bellmanford(GraphAdjacentMatrix_BellmanFord gam, int startingVertice, Set<EdgeElemnt> edgeElemnts) {
- // initialize the final result array
- int[] distance = new int[gam.numVertices];
- for (int i = 0; i < distance.length; i++) {
- distance[i] = Integer.MAX_VALUE;
- }
- // the first vertex reached
- distance[startingVertice] = 0; // initialize first data - from startingVertice to each vertice (we will update this whenver we reach a vertex)
- // main work here
- for (int i = 1; i < gam.numVertices; i++) { // run |V| - 1 runs because the the final path can only have maximum |V| - 1 edges
- // process all edges each run (simply straightforward)
- for (EdgeElemnt ee : edgeElemnts) {
- // if the starting vertex in the directed graph is unreachable, skip it
- if (distance[ee.fromV] == Integer.MAX_VALUE) continue;
- if (distance[ee.toV] > (distance[ee.fromV] + ee.edgeWeight)) {
- distance[ee.toV] = (distance[ee.fromV] + ee.edgeWeight);
- System.out.print("");
- }
- }
- }
- // final round to check if there is a negative circle
- // if there is no negative circal, the distances of all should remain the same
- // however, if one of the distances is getting shorter and shorter each extra run, something is wrong.
- for (EdgeElemnt ee : edgeElemnts) {
- // if the starting vertex in the directed graph is unreachable, skip it
- if (distance[ee.fromV] == Integer.MAX_VALUE) continue;
- if (distance[ee.toV] > (distance[ee.fromV] + ee.edgeWeight)) {
- System.out.println("Graph contains negative weight cycle. Opration aborted");
- return distance;
- }
- }
- return distance;
- }
- public static class EdgeElemnt implements Comparable{
- public Integer fromV;
- public Integer toV;
- public Integer edgeWeight;
- public EdgeElemnt(Integer v1, Integer v2, Integer edgeWeight) {
- this.fromV = v1;
- this.toV = v2;
- this.edgeWeight = edgeWeight;
- }
- @Override
- public boolean equals(Object obj)
- {
- if(this == obj)
- return true;
- if(obj == null || obj.getClass()!= this.getClass())
- return false;
- // type casting of the argument.
- EdgeElemnt geek = (EdgeElemnt) obj;
- return (geek.fromV == this.fromV && geek.toV == this.toV) || (geek.fromV == this.toV && geek.toV == this.fromV);
- }
- @Override
- public int hashCode() {
- return Objects.hash(fromV + toV);
- }
- @Override
- public int compareTo(Object o) {
- EdgeElemnt o1 = (EdgeElemnt) o;
- return this.edgeWeight.compareTo(o1.edgeWeight);
- }
- @Override
- public String toString() {
- return " " + edgeWeight;
- // return "EdgeElemnt{" +
- // "fromV=" + fromV +
- // ", toV='" + toV +
- // ", edgeWeight=" + edgeWeight +
- // '}';
- }
- }
- // Imagine we convert the length n into n vertices and use BFS;
- // we will be making many redundant waves until we reach a vertex
- // Therefore, this method here is to help us save those steps and find the next vertex right away
- // (we could use minHeap to replace this method)
- //
- // find the shorted distance from startingVertice to D so far; this will be our next starting point
- private int minVertex(int[] distance) {
- int nextVWithShortestDistance = empty; // if all vertices are visited
- // initialize v to some unvisited vertex
- int i;
- for (i = 0; i < this.numVertices; i++) {
- if (!visited[i]) {
- nextVWithShortestDistance = i;
- break;
- }
- }
- // find the smallest D value
- for (i++; i < this.numVertices; i++) {
- if (!visited[i] && distance[i] < distance[nextVWithShortestDistance]) {
- nextVWithShortestDistance = i;
- }
- }
- return nextVWithShortestDistance;
- }
- private void Previsit(boolean[][] graph, int v) {
- System.out.println("Previsit: " + v);
- }
- private void Postvisit(boolean[][] graph, int v) {
- System.out.println("Postvisit: " + v);
- }
- public String toString() {
- StringBuilder s = new StringBuilder();
- for (int i = 0; i < numVertices; i++) {
- s.append(i + ": ");
- for (int j : adjMatrix[i]) {
- s.append((i != empty?1:0) + " ");
- }
- s.append("\n");
- }
- return s.toString();
- }
- public static void main(String[] args) {
- GraphAdjacentMatrix_BellmanFord gam = new GraphAdjacentMatrix_BellmanFord(8);
- // directed graph
- Set<EdgeElemnt> edgeElemnts = new HashSet<>();
- edgeElemnts.add(new EdgeElemnt(1, 2, -1));
- edgeElemnts.add(new EdgeElemnt(1, 3, 4));
- edgeElemnts.add(new EdgeElemnt(2, 3, 3));
- edgeElemnts.add(new EdgeElemnt(2, 4, 2));
- edgeElemnts.add(new EdgeElemnt(2, 5, 2));
- edgeElemnts.add(new EdgeElemnt(4, 3, 5));
- edgeElemnts.add(new EdgeElemnt(4, 2, 1));
- edgeElemnts.add(new EdgeElemnt(5, 4, -3));
- int[] distances = bellmanford(gam, 1, edgeElemnts);
- printArray(distances);
- System.out.printf("the shortest distance between %d and %d = %d %n", 1, 1, distances[1]);
- System.out.printf("the shortest distance between %d and %d = %d %n", 1, 2, distances[2]);
- System.out.printf("the shortest distance between %d and %d = %d %n", 1, 3, distances[3]);
- System.out.printf("the shortest distance between %d and %d = %d %n", 1, 4, distances[4]);
- System.out.printf("the shortest distance between %d and %d = %d %n", 1, 5, distances[5]);
- System.out.println();
- }
- ////////// UTIL ///////////
- private static void printArray(int[] ary){
- for (int i = 0; i < ary.length; i++) {
- System.out.printf("%4d" , ary[i]);
- }
- System.out.println();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement