Bellman-Ford optimisation in C with Shortest Path Algorithm (SPFA) and Small Label first (SLF)

Question

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

Source: https://www.researchgate.net/publication/274174007_An_Improved_SPFA_Algorithm_for_Single-Source_Shortest_Path_Problem_Using_Forward_Star_Data_Structure

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

Answer 1

We're missing a lot of includes. At least the following standard headers:

#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

We're also missing declarations of queue_t, init(), enqueue(), is_empty(), dequeue(), free_queue(), is_in_queue(), and move_to_front(). In C, all identifiers need to be declared before they are used.

---

We attempt to allocate memory here:

    uint *length = (uint *)calloc(nb_nodes, sizeof(uint));

However, if the allocation fails, length is assigned a null pointer. Since we blunder on regardless, we hit Undefined Behaviour when we dereference it here:

    length[s] = 1;

This is something that's easily detectable by modern compilers (e.g. gcc -Wall -Wextra -fanalyzer). It's not very hard to fix this:

    uint *length = calloc(nb_nodes, sizeof *length);
    if (!length) {
        fprintf(stderr, "Failed to allocate memory for %" PRIu32 " nodes.\n", nb_nodes);
        free_queue(queue);
        return 1;
    }

(include <inttypes.h> to define that format specifier macro)

We don't have the definition of init() (a terrible name if ever I saw one), but it seems likely that it could also return a null pointer, so that should also be checked.

---

There are a lot of suspect conversions between signed and unsigned types, which are highlighted by gcc -Wconversion. These should be inspected and casts inserted where we are confident that the conversion is safe. These casts then serve to document where we have checked the conversions.

---

Standard convention is to use ALL_CAPS for preprocessor macro names, to indicate that these are text substitutions. However, uint, sint and lsint are much better defined as typedefs than as macros:

typedef uint32_t uint; // 32bit unsigned integer
typedef int32_t sint;  // 32bit signed integer
typedef int64_t lsint; // 64bit signed integer

Personally, I find these names unhelpful - we should be clearer why we need exactly 32 or 64 bits, and why uint_fast32_t and similar are unsuitable.

The remaining macro is in all-caps, but its name is highly misleading:

#define MAX_DISTANCE 0x7f  // Maximum value for int64_t 

The maximum value for int64_t is not 0x7f - it's INT64_MAX, which is probably 0x7fffffffffffffff.

Answer 2

Concerning *alloc() discussion, (not a major issue with OP's code)

Recommend:

• No cast

• Size to the referenced object, not type.

• Check result

• Lead any size computation with the size_t argument to avoid computations like int * int * size_t.

    // lsint *dist = (lsint *)malloc(nb_nodes * sizeof(lsint));
    lsint *dist = malloc(sizeof dist[0] * nb_nodes);
    assert(dist || nb_nodes == 0); // Or other test code.