# Untitled unknown
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) {
for(int i=0;i<m;i++){
int u=edges[i];
int v=edges[i];
} */
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];
int v=edges[j];
int w=edges[j];
if((dist[u]+w)<dist[v]){
dist[v]=dist[u]+w;
}
}
}

/*  for(int j=0;j<m;j++){
int u=edges[j];
int v=edges[j];
int w=edges[j];
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 */

```