Bellman - Ford Algorithm

                                                  Bellman - Ford Algorithm

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118

import java.util.ArrayList; import java.util.List; /** * Edge of Graph * @author Prateek */ class Edge { int src; int dest; int weight; public Edge(int src,int dest,int weight) { this.src=src; this.dest=dest; this.weight=weight; } @Override public String toString() { return "Edge: "+src+ " - " + dest + " | " +" Weight: "+ weight; } } /** * Bellman's Algorithm for Single Source Shortest Path * @author Prateek * */ class BellmanFord { private static final int MAX_INF=999999; private int mNumVertices; // Number of vertices in the graph private int mNumEdges; // Number of edges in the graph // Input Edge List private List<Edge> mEdgeList; public BellmanFord(int numVertices,int numEdges) { this.mNumVertices=numVertices; this.mNumEdges=numEdges; this.mEdgeList=new ArrayList<Edge>(numEdges); } private boolean bellmanFord(int src) { // maintains the updated distance int[] dist=new int[mNumVertices]; //Initialisation for(int i=0;i<mNumVertices ; i++) dist[i] = MAX_INF; dist[src]=0; for(int i=0;i<= mNumVertices ; i++) { for(int j=0;j< mNumEdges ; j++) { Edge edge=mEdgeList.get(j); int u=edge.src; int v=edge.dest; int weight=edge.weight; // Relaxing the edge if(dist[v] > dist[u]+weight) dist[v]=dist[u]+weight; } } //check for negative cycles, by inspecting the distance of all vertices // if we find any dist[v] greater distance than dist[u]+ weight, that means // we have already cycled through some edge more than once for(int i=0 ;i< mNumEdges ;i++) { Edge edge=mEdgeList.get(i); int u=edge.src; int v=edge.dest; int weight=edge.weight; if(dist[u]+weight < dist[v]) { System.out.println("Undefined Graph , Shortest path cant be calculated"); return false; } } printShortestPath(src , dist); return true; } private void printShortestPath(int src , int[] dist) { for(int i=0;i<mNumVertices ;i++) System.out.println(src + " ---> " + i + " " +dist[i]); } public static void main(String[] args) { BellmanFord graph=new BellmanFord(5, 6); graph.helper(); } public void helper() { mEdgeList.add(new Edge(0, 1, 2)); mEdgeList.add(new Edge(0, 2, 4)); mEdgeList.add(new Edge(1, 3, 2)); mEdgeList.add(new Edge(1, 2, 1)); mEdgeList.add(new Edge(2, 4, 4)); mEdgeList.add(new Edge(3, 4, 2)); int sourceVertex = 0; bellmanFord(sourceVertex); } }

References: http://faculty.ycp.edu/~dbabcock/PastCourses/cs360/lecture/lecture21.html