I am trying to code an optimized version of Bellman-Ford algorithm. This post is a continuation of the following post Bellman-Ford optimisation in C in which I posted a first version of the classic Bellman-Ford algorithm (without the SPFA and SLF optimizations).
Descriptions of the variation I'm trying to implement can be found here: https://en.wikipedia.org/wiki/Shortest_path_faster_algorithm
Here is an interesting pseudo-code describing both Shortest Path Algorithm optimization (using a queue of potential candidates) and Small Label first (some sort of ordering providing better average complexity
Improved-SPFA-Algorithm(G, s)
1 for each vertex v ≠s in V(G)
2 d(v) ← ∞
3 d(s) ← 0
4 min ← ∞
5 push s into front of Q
6 while Q is not empty
7 node p ← null
8 u ← pop Q
9 for each edge (u, v) in E(G)
10 if d(u) + w(u, v) < d(v) then
11 d(v) ← d(u) + w(u, v)
12 if v is not in Q then
13 push v into back of Q
14 if( d(v) < min ) then
15 min ← d(v)
16 label v as p
17 move p into front of Q
My current implementation in C is:
#define uint uint32_t // 32bit unsigned integer
#define sint int32_t // 32bit signed integer
#define lsint int64_t // 64bit signed integer
// This section contains the function declarations for the Bellman-Ford algorithm, file I/O, and utility functions used in the program.
int bellman_ford(sint links[][3], uint links_size, uint s, lsint *dist, uint *path, uint nb_nodes);
int SPFA(sint links[][3], uint links_size, uint s, lsint *dist, uint *path, uint nb_nodes);
int SPFA_SLF(sint links[][3], uint links_size, uint s, lsint *dist, uint *path, uint nb_nodes);
/**
* Computes the shortest path between a given source node and all other nodes in a weighted graph.
*
* Arguments:
* links: A 2D array of integers representing the links between nodes. Each row represents a link and contains the indices of the two nodes and the cost of the link.
* links_size: The number of links in the links array.
* s: The index of the starting node.
* dist: An array of size nb_nodes to store the shortest distances from each node to s.
* path: An array of size nb_nodes to store the shortest paths from each node to s.
* nb_nodes: The total number of nodes in the graph.
*
* Returns:
* 0 if the computation succeeded, 1 if a negative cycle was detected in the graph.
**/
int SPFA_SLF(sint links[][3], uint links_size, uint s, lsint *dist, uint *path, uint nb_nodes)
{
queue_t *queue = init(); // Initialize the queue
uint *length = (uint *)calloc(nb_nodes, sizeof(uint));
// Initialize dist
for (int i = 0; i < nb_nodes; i++) {
dist[i] = INT64_MAX;
}
// Initialise path
memset(path, -1, nb_nodes * sizeof(sint));
dist[s] = 0; // Set the distance of the source node to 0
enqueue(queue, s); // Add the source node to the queue
length[s] = 1;
// While the queue is not empty, perform iterations of the algorithm
while (!is_empty(queue))
{
int current_node = dequeue(queue); // Dequeue the next node to process
// If the length of the shortest path for any link reaches nb_nodes, there is a negative cycle in the graph
if (length[current_node] >= nb_nodes)
{
printf("Negative cycle detected\n");
free(length);
free_queue(queue);
return 1;
}
sint min = INT32_MAX;
int min_node = -1;
// Iterate through all the links in the graph
for (uint i = 0; i < links_size; i++)
{
// If the current link starts from the dequeued node (current_node)
if (links[i][0] == current_node)
{
uint node_from = links[i][0];
uint node_to = links[i][1];
lsint cost = links[i][2];
// If a shorter path is found, update the distances and paths
if (dist[node_from] + cost < dist[node_to])
{
dist[node_to] = dist[node_from] + cost;
path[node_to] = node_from;
length[node_to] = length[node_from] + 1;
// If the destination node (node_to) is not in the queue, enqueue it
if (!is_in_queue(queue, node_to))
{
enqueue(queue, node_to);
}
// Check if the current node's distance is less than the current minimum distance
if (dist[node_to] < min)
{
min = dist[node_to];
min_node = node_to;
}
}
}
}
if (min_node != -1)
{
// Move the node with the minimum distance to the front of the queue
move_to_front(queue, min_node);
}
}
free(length);
free_queue(queue);
return 0;
}
I'm still unsure about the performances. While it is 3 to 4 times faster than the previous version for big and dense graphs (say hundreds or thousands of vertex for tenth or hundreds of nodes, respectively). I am at the same speed or even slower for smaller graph. Is it possible that it is only due to the extra lines of my new version, even though their time complexity is just O(1) ? (Can this play a significant role for graphs containing only a few tens of edges?).
Here is the type of test I used (it is a test loop creating random graphs responding to the chosen parameters: number of nodes, number of edges, max/min costs, number of test iterations (n)). Not the cleanest of final test at all, just a little something to get an idea of where I stand:
// Add this function to generate a random graph
void generate_random_graph(sint (*links)[3], uint links_size, uint nb_nodes, sint min_cost, sint max_cost)
{
for (uint i = 0; i < links_size; i++)
{
links[i][0] = rand() % nb_nodes;
links[i][1] = rand() % nb_nodes;
links[i][2] = min_cost + rand() % (max_cost - min_cost + 1);
}
}
int main(int argc, char *argv[])
{
// Initialize the random number generator
srand(time(NULL));
// Define the variables for the test graph
uint s = 0;
uint nb_nodes = 24;
uint links_size = 312;
uint n = 100;
// Allocate memory for the dist and path arrays
lsint *dist = (lsint *)malloc(nb_nodes * sizeof(lsint));
uint *path = (uint *)malloc(nb_nodes * sizeof(uint));
// clock_t start2, end2;
clock_t start1, start3, end1, end3;
double cpu_time_used1 = 0;
// double cpu_time_used2 = 0;
double cpu_time_used3 = 0;
// Loop for n iterations
for (uint i = 0; i < n; i++)
{
// Generate a random graph
sint links[links_size][3];
generate_random_graph(links, links_size, nb_nodes, -10, 10);
// Apply the basic Bellman-Ford algorithm on the random graph
start1 = clock();
bellman_ford(links, links_size, s, dist, path, nb_nodes);
end1 = clock();
// start2 = clock();
// SPFA(links, links_size, s, dist, path, nb_nodes);
// end2 = clock();
// Apply the SPFA_SLF algorithm on the random graph
start3 = clock();
SPFA_SLF(links, links_size, s, dist, path, nb_nodes);
end3 = clock();
cpu_time_used1 += ((double)(end1 - start1)) / CLOCKS_PER_SEC;
// cpu_time_used2 += ((double)(end2 - start2)) / CLOCKS_PER_SEC;
cpu_time_used3 += ((double)(end3 - start3)) / CLOCKS_PER_SEC;
}
printf("Time taken for %d iterations for BF: %f seconds\n", n, cpu_time_used1);
// printf("Time taken for 100,000 iterations for SPFA: %f seconds\n", cpu_time_used2);
printf("Time taken for %d iterations for SPFA_SLF: %f seconds\n", n, cpu_time_used3);
// Free the memory allocated for the dist and path arrays
free(dist);
free(path);
return 0;
}
What also surprises me is that if I use the queue without SFL (small label first), so without ordering, the performances are then very bad. It is 2 to 20 times worse than the basic Bellman-Ford version , whatever the number of nodes/edges/costs is. Isn't SPFA supposed to work better than classic Bellman-Ford even without the SFL trick?
Apart from that, any comments or advice to obtain better performance are welcome
malloc()
. It returns a genericvoid *
that is implicitly converted to any other pointer type. (malloc()
once used to return achar *
and the cast was necessary. Now it just adds clutter to the code.) And whytypedef
standard types? I doubt it saves much typing. \$\endgroup\$