_Andrii_Yalanskyi_Alamy.jpg?#)
.jpg?width=1920&height=1920&fit=bounds&quality=80&format=jpg&auto=webp#)
Bellmen-Ford
To know the shortest path of a graph we use Dijkstra algorithm . When the graph have negative weight and cycle both the Dijkstra algorithm will get a runtime error . To solve this we use Bellmen-ford . This algorithm can solve when a graph have cycle and negative weight both . We start from source 0 . The all node which is not 0 will become infinite . We will start from 0 . We will count the weight with 0 from the 0 node . . We will add the cost / weight with 0 . We will go by direction . If the value is not come from 0 . We will add the cost with infinity . This is how Bellmen-ford works . #include using namespace std; class Edge { public: int a, b, c; Edge(int a, int b, int c) { this->a = a; this->b = b; this->c = c; } }; int dis[1005]; vector edge_list; int n, e; void bellman_ford() { for (int i = 0; i < n - 1; i++) { for (auto ed : edge_list) { int a, b, c; a = ed.a; b = ed.b; c = ed.c; if (dis[a] != INT_MAX && dis[a] + c < dis[b]) dis[b] = dis[a] + c; } } } int main() { cin >> n >> e; while (e--) { int a, b, c; cin >> a >> b >> c; edge_list.push_back(Edge(a, b, c)); // edge_list.push_back(Edge(b,a,c)); undirected } for (int i = 0; i < n; i++) dis[i] = INT_MAX; dis[0] = 0; bellman_ford(); for (int i = 0; i < n; i++) cout
To know the shortest path of a graph we use Dijkstra algorithm . When the graph have negative weight and cycle both the Dijkstra algorithm will get a runtime error .
To solve this we use Bellmen-ford .
This algorithm can solve when a graph have cycle and negative weight both .
We start from source 0 . The all node which is not 0 will become infinite .
We will start from 0 . We will count the weight with 0 from the 0 node .
.
We will add the cost / weight with 0 . We will go by direction .
If the value is not come from 0 . We will add the cost with infinity .
This is how Bellmen-ford works .
#include
using namespace std;
class Edge
{
public:
int a, b, c;
Edge(int a, int b, int c)
{
this->a = a;
this->b = b;
this->c = c;
}
};
int dis[1005];
vector edge_list;
int n, e;
void bellman_ford()
{
for (int i = 0; i < n - 1; i++)
{
for (auto ed : edge_list)
{
int a, b, c;
a = ed.a;
b = ed.b;
c = ed.c;
if (dis[a] != INT_MAX && dis[a] + c < dis[b])
dis[b] = dis[a] + c;
}
}
}
int main()
{
cin >> n >> e;
while (e--)
{
int a, b, c;
cin >> a >> b >> c;
edge_list.push_back(Edge(a, b, c));
// edge_list.push_back(Edge(b,a,c)); undirected
}
for (int i = 0; i < n; i++)
dis[i] = INT_MAX;
dis[0] = 0;
bellman_ford();
for (int i = 0; i < n; i++)
cout << i << " -> " << dis[i] << endl;
return 0;
}
Time Complexity
O(VE)
