Bellman ford function to check negative cycle * v = no. of verties * e = no. of edges * edges = vector of {x, {y, w}} such that x->y is an edge of weight w */
| 35 | * edges = vector of {x, {y, w}} such that x->y is an edge of weight w |
| 36 | */ |
| 37 | bool bellman_ford(int source, int v, int e, vector <int> &dist) { |
| 38 | |
| 39 | // till i-th iteration, paths with atmost i edges are considered |
| 40 | for (int i = 0; i <= v - 1; i ++) { |
| 41 | |
| 42 | // consider all the edges and relax the edges if possible |
| 43 | for (int edge_idx = 0; edge_idx < e; edge_idx ++) { |
| 44 | |
| 45 | pair <int, pair <int, int> > edge; |
| 46 | edge = edges[edge_idx]; |
| 47 | int first_node = edge.first; |
| 48 | int second_node = edge.second.first; |
| 49 | int weight = edge.second.second; |
| 50 | |
| 51 | bool possible = relax(first_node, second_node, weight, dist); |
| 52 | |
| 53 | } |
| 54 | } |
| 55 | |
| 56 | // after the end, no more edge should be relaxed if no negative cycle |
| 57 | for (int edge_idx = 0; edge_idx < e; edge_idx ++) { |
| 58 | pair <int, pair <int, int> > edge; |
| 59 | edge = edges[edge_idx]; |
| 60 | int first_node = edge.first; |
| 61 | int second_node = edge.second.first; |
| 62 | int weight = edge.second.second; |
| 63 | if (relax(first_node, second_node, weight, dist)) { |
| 64 | // negative weight cycle found |
| 65 | return true; |
| 66 | } |
| 67 | } |
| 68 | return false; |
| 69 | } |
| 70 | |
| 71 | |
| 72 | /* Function to find the shortest path from source |