| 24 | } |
| 25 | |
| 26 | void BellmanFord(CreateGraph graph, int s) { |
| 27 | int V = graph.V, E = graph.E; |
| 28 | int dist[] = new int[V]; |
| 29 | |
| 30 | // Step 1: fill the distance array and predecessor array |
| 31 | for (int i = 0; i < V; ++i) |
| 32 | dist[i] = Integer.MAX_VALUE; |
| 33 | |
| 34 | // Mark the source vertex |
| 35 | dist[s] = 0; |
| 36 | |
| 37 | // Step 2: relax edges |V| - 1 times |
| 38 | for (int i = 1; i < V; ++i) { |
| 39 | for (int j = 0; j < E; ++j) { |
| 40 | // Get the edge data |
| 41 | int u = graph.edge[j].s; |
| 42 | int v = graph.edge[j].d; |
| 43 | int w = graph.edge[j].w; |
| 44 | if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v]) |
| 45 | dist[v] = dist[u] + w; |
| 46 | } |
| 47 | } |
| 48 | |
| 49 | // Step 3: detect negative cycle |
| 50 | // if value changes then we have a negative cycle in the graph |
| 51 | // and we cannot find the shortest distances |
| 52 | for (int j = 0; j < E; ++j) { |
| 53 | int u = graph.edge[j].s; |
| 54 | int v = graph.edge[j].d; |
| 55 | int w = graph.edge[j].w; |
| 56 | if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v]) { |
| 57 | System.out.println("CreateGraph contains negative w cycle"); |
| 58 | return; |
| 59 | } |
| 60 | } |
| 61 | |
| 62 | // No negative w cycle found! |
| 63 | // Print the distance and predecessor array |
| 64 | printSolution(dist, V); |
| 65 | } |
| 66 | |
| 67 | // Print the solution |
| 68 | void printSolution(int dist[], int V) { |