Not a member of GistPad yet?
Sign Up,
it unlocks many cool features!
- // User function Template for Java
- class iPair
- {
- int vertex;
- int weight;
- iPair(int vertex, int weight)
- {
- this.vertex = vertex;
- this.weight = weight;
- }
- }
- class Pair
- {
- int node;
- int dist;
- Pair(int node, int dist)
- {
- this.node = node;
- this.dist = dist;
- }
- }
- class Solution {
- // Diff: In dijkstra we do not have cycle in weighted, undirected, connected graph but here we can have cycle
- /**
- * Idea
- * 1. Create a distance array and assign values as (int)1e8
- * 2. Relax the edges N-1 times
- * 3. Now relax the edges again and see if you if relaxation is possible
- * - if possible then we have negative cycle, return array of -1 element
- * - else keep continuing
- * 4. At last return distance array
- */
- public int[] bellmanFord(int V, int[][] edges, int src) {
- // Step-1 create a distance array
- int[] distance = new int[V];
- distance[src] = 0;
- // Step-2 Relax edges V-1 times
- for(int i=0; i<V-1; i++)
- {
- for(int[] edge : edges)
- {
- int u = edge[0];
- int v = edge[1];
- int w = edge[2];
- if(distance[u] != (int)1e8 && distance[v] > distance[u] + w)
- {
- distance[v] = distance[u] + w;
- }
- }
- }
- // Step-3 to detect negative cycle
- for(int[] edge : edges)
- {
- int u = edge[0];
- int v = edge[1];
- int w = edge[2];
- if(distance[u] != (int)1e8 && distance[v] > distance[u] + w)
- {
- return new int[]{-1};
- }
- }
- return distance;
- }
- }
RAW Paste Data
Copied
