6
\$\begingroup\$

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

\$\endgroup\$
6
  • 2
    \$\begingroup\$ Perhaps unrelated, but you should not cast the result of malloc(). It returns a generic void * that is implicitly converted to any other pointer type. (malloc() once used to return a char * and the cast was necessary. Now it just adds clutter to the code.) And why typedef standard types? I doubt it saves much typing. \$\endgroup\$
    – Harith
    Mar 21 at 11:31
  • 1
    \$\begingroup\$ @Haris I was thought at uni (from our tutor which is an older student, not from a teacher) that casting malloc was a good practice. But you're the second person I see mentioning this so I will take this into account. typedef is used because those might change during our project (and the full code is longer than what you see here). \$\endgroup\$
    – c.leblanc
    Mar 21 at 11:40
  • 2
    \$\begingroup\$ Unless the code is to be compiled with a C++ compiler, I say it is an obsolete (and bad) practice. There's a discussion about this on Stackoverflow. See: stackoverflow.com/q/605845/20017547 \$\endgroup\$
    – Harith
    Mar 21 at 11:58
  • \$\begingroup\$ What about calloc ? (I guess same thing since Toby also rewrotte it without the cast in his message) \$\endgroup\$
    – c.leblanc
    Mar 21 at 13:43
  • 1
    \$\begingroup\$ In the K&R version of C malloc and calloc returned char* pointers and needed to be cast to the proper type. The ANSI version of C in 1989 fixed this. \$\endgroup\$
    – pacmaninbw
    Mar 21 at 14:38

2 Answers 2

5
\$\begingroup\$

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.

\$\endgroup\$
6
  • \$\begingroup\$ I'm using a header for queue functions, I could've paste it too sry for the confusion. The use of those type for int are non-negotiable request from higher authorities (for cross platform compatibility reasons). About INT64_MAX you are right, I believe I was making the edit while you were writing your message. I take into account all the other remarks, thanks! \$\endgroup\$
    – c.leblanc
    Mar 21 at 13:40
  • \$\begingroup\$ @c.leblanc "The use of those type for int are non-negotiable request from higher authorities (for cross platform compatibility reasons)" may be what you are stuck with, yet remains the wrong approach. Better solutions exist. To detail a better solution, we first need the goals. \$\endgroup\$ Mar 24 at 22:50
  • \$\begingroup\$ @chux This is a project for uni. It is simply a requirement in the instructions we have. \$\endgroup\$
    – c.leblanc
    Mar 25 at 9:48
  • \$\begingroup\$ @c.leblanc University - Great, a fine opportunity then to interact. It is not that different than in real-life job assignments. When requirements are weak, it is your responsibility to attempt to improve them. Consider, as time goes on, you are the coding expert, not the customer - that is why you get paid for the task. A good education environment encourages this. Hopefully yours is such an institution. If not, at least you know more of their quality. \$\endgroup\$ Mar 25 at 10:56
  • \$\begingroup\$ @chux Well, in the present case, teachers are supposed to be the expert and we are the students learning from them. I'm not sure about the "I read on a forum that we shoudln't do as you required but rater ... , please adapt your instructions". Even tough you might be right. \$\endgroup\$
    – c.leblanc
    Mar 25 at 11:37
1
\$\begingroup\$

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.
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.