Untitled
plain_text
a month ago
1.6 kB
1
Indexable
Never
//directed weighted graph //#include<unordered_map> #define occ 1e8 #include<vector> #include<list> #include<cmath> vector<int> bellmonFord(int n, int m, int src, vector<vector<int>> &edges) { /* unordered_map<int,list<pair<int,int>>> adj; for(int i=0;i<m;i++){ int u=edges[i][0]; int v=edges[i][1]; adj[u].push_back(v); } */ vector<int> dist(n+1,occ); dist[src]=0; for(int i=1;i<n;i++){ //n-1 times update for(int j=0;j<m;j++){ int u=edges[j][0]; int v=edges[j][1]; int w=edges[j][2]; if((dist[u]+w)<dist[v]){ dist[v]=dist[u]+w; } } } /* for(int j=0;j<m;j++){ int u=edges[j][0]; int v=edges[j][1]; int w=edges[j][2]; if(dist[u]!=occ &&((dist[u]+w) <dist[v])){ return-1; } } */ return dist; } /* The Bellman-Ford algorithm is applied n-1 times because it is the maximum number of edges in any shortest path of a graph with n vertices. The algorithm works by iteratively relaxing the edges of the graph, updating the distance estimates for each vertex. After k iterations, the algorithm has found the shortest paths between the source vertex and all other vertices that have at most k edges. Since the longest possible shortest path in a graph with n vertices has at most n-1 edges, it is sufficient to run the algorithm for n-1 iterations to find the shortest paths between the source vertex and all other vertices */