Hey everyone! This article is a followup to my last one about the Bellman Ford Algorithm.
/*
Bellman-Ford with an Adjacency List
*/
#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.
adj_list graph(n);
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
// start with `start`
// keep track of predecessors
// do it V-1 times
bool changes_made = true;
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;
changes_made = true;
}
}
}
if (!changes_made)
break;
changes_made = false;
}
// 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.
Adjacency List
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 vectors of pairs. 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;
adj_list graph(n); // declares adjacency list for n elements
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.