 Graph Algorithms (Part 2.1): Bellman-Ford [Implementation]

(oaktree) #1

``````/*
*/
#include <vector>
#include <iostream>
#include <algorithm>
#include <limits>
#include <utility>

typedef std::vector< std::vector< std::pair<int,int> > > adj_list;

void bellman(const int start, const adj_list& graph, std::vector<int>& distances);

int main() {
int n,m; std::cin >> n >> m;

// adj-list using vector of size n holding a vector for
// each vertex.

int f,s,w; // first, second, weight
for (int i = 0; i < m; i++) {
std::cin >> f >> s >> w;

// graph is directed
graph[f-1].push_back( std::make_pair(s-1,w) );
}

int start; std::cin >> start;

std::vector<int> distances(n /* n = graph.size() */, std::numeric_limits<int>::max());
bellman(start - 1, graph, distances);

// print out the distances here
for (int i = 0; i < n; i++)
std::cout << "The distance from " << start << " to "
<< i+1 << " is " << distances[i] << ".\n";

return 0;
}

void bellman(const int start, const adj_list& graph, std::vector<int>& distances) {
// setting to infinity is done in main;
distances[start] = 0;

// for later.
std::vector<int> pred(graph.size());

// visit every node
// keep track of predecessors

// do it V-1 times
for (int i = 1, n = graph.size(); i < n; i++) {
// go through each node
for (int j = 0; j < n; j++) {
if (distances[j] == std::numeric_limits<int>::max())
continue; // skip if we don't know how to reach a node yet.

// go through a node's neighbors
for (auto& neighbor : graph[j]) {
if (distances[neighbor.first] > distances[j] + neighbor.second) {
distances[neighbor.first] = distances[j] + neighbor.second;
pred[neighbor.first] = j;
}
}
}
break;
}

// now we do it one more time to find any negative cycles
for (int i = 0, n = graph.size(); i < n; i++) {
if (distances[i] == std::numeric_limits<int>::max())
continue; // skip if we don't know how to reach a node yet.

// go through a node's neighbors
for (auto& neighbor : graph[i]) {
if (distances[neighbor.first] > distances[i] + neighbor.second)
std::cout << "Found negative cycle from " << i << " to " << neighbor.first << ".\n";
}
}
}
``````

The code is well-commented, so I won’t talk much about it here. Review my last article for an explanation of the underlying algorithm and the pseudocode.

``````6 8
1 2 10
1 6 8
2 4 2
3 2 1
4 3 -2
5 4 -1
6 5 1
5 2 -4
1
``````

The above is a sample input to use. It follows this convention. The first line has `n` and `m`, the number of vertices and number of edges, respectively. The next `m` lines are `f`, `s`, `w`, denoting an edge of weight `w` between nodes `f` and `s`. The last line takes one number, `start`, the node to start from.

The program expects input of nodes labeled `1` through `n`. The code itself will convert this to `0` through `n-1` for easier storage.

There is one final thing I must mention.

This program utilizes a certain way of representing a graph. An adjacency list has space complexity `|E|`, while an adjacency matrix (remember this article?) has `|V|*|V|` space complexity. If it wasn’t obvious, space complexity is how much space something takes up in memory.

We design the adjacency list in this line:

``````typedef std::vector< std::vector< std::pair<int,int> > > adj_list;
``````

It is a `vector` of `vector`s of `pair`s. Each index in the outer vector represents a node. Each element is a `vector` of edges connected to a node `f` at index `f`. The first value in the `pair` is a node `s` connected to `f` by an edge of weight `w` (the weight is the second value in the pair).

Thus, if I did the following (making use of our `typedef`):

``````// ...
int f = 0, s = 1, w = 3;
graph[f].push_back( std::make_pair(s, w);
//...
``````

We add an edge between `f` and `s` with weight `w`. Specifically, we add an edge of weight `3` between nodes `0` and `1`.

Conclusion

I hope you can take some time to review the source code. Alternatively, you can find it here. If you have any questions, comment below or hit me up on IRC at ##0x00sec.

@oaktree out.

2 Likes

Graph Algorithms (Part 3.1): Kruskal's MST [Code]
(oaktree) closed #2

This topic was automatically closed after 30 days. New replies are no longer allowed.

0 Likes