Created
August 24, 2020 18:06
-
-
Save SuryaPratapK/5d8de644480b94fe57041a6b6c857659 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include<bits/stdc++.h> | |
using namespace std; | |
struct edge{ | |
int src,dst,wt; | |
}; | |
int V,E; | |
void bellmanFord(vector<edge>& Edges) | |
{ | |
int parent[V]; //Stores Shortest Path Structure | |
int cost_parent[V]; //Cost of the node to parent edge weight | |
vector<int> value(V,INT_MAX); //Keeps shortest path values to each vertex from source | |
//Assuming start point as Node-0 | |
parent[0] = -1; //Start node has no parent | |
value[0] = 0; //start node has value=0 to get picked 1st | |
//Include (V-1) edges to cover all V-vertices | |
bool updated; | |
for(int i=0;i<V-1;++i) | |
{ | |
updated = false; | |
for(int j=0;j<E;++j) | |
{ | |
int U = Edges[j].src; | |
int V = Edges[j].dst; | |
int wt = Edges[j].wt; | |
if(value[U]!=INT_MAX and value[U]+wt<value[V]) | |
{ | |
value[V] = value[U]+wt; | |
parent[V] = U; | |
cost_parent[V] = value[V]; | |
updated = true; | |
} | |
} | |
if(updated==false) | |
break; | |
} | |
//Now check by relaxing once more if we have a negative edge cycle | |
for(int j=0;j<E and updated==true;++j) | |
{ | |
int U = Edges[j].src; | |
int V = Edges[j].dst; | |
int wt = Edges[j].wt; | |
if(value[U]!=INT_MAX and value[U]+wt<value[V]) | |
{ | |
cout<<"Graph has -VE edge cycle\n"; | |
return; | |
} | |
} | |
//Print Shortest Path Graph | |
for(int i=1;i<V;++i) | |
cout<<"U->V: "<<parent[i]<<"->"<<i<<" Cost to reach "<<parent[i]<<"from source 0 = "<<value[i]<<"\n"; | |
} | |
int main() | |
{ | |
cin>>V>>E; //Enter no of Vertices and Edges | |
vector<edge> Edges(E); | |
//Now input all E edges | |
int src,dst,wt; | |
for(int i=0;i<E;++i) | |
{ | |
cin>>src>>dst>>wt; | |
Edges[i].src = src; | |
Edges[i].dst = dst; | |
Edges[i].wt = wt; | |
} | |
bellmanFord(Edges); | |
return 0; | |
} | |
//TIME COMPLEXITY: O(V.E) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
it is used to find the distance of different vertex from the source node