Bellman-Ford optimisation in C

Question

Here is my current code:

#define uint uint32_t // unsigned integer
#define sint int32_t  // signed integer

// Declaration of the bellman_ford function 
int bellman_ford(sint links[][3], uint links_size, uint s, int64_t *dist, uint *path, uint nb_nodes);

int bellman_ford(sint links[][3], uint links_size, uint s, int64_t
*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 updates;

    // Initialize dist and path arrays with memset
    memset(dist, 0x7f, nb_nodes * sizeof(int64_t));
    memset(path, -1, nb_nodes * sizeof(sint));

    dist[s] = 0;

    // Perform nb_nodes - 1 iterations of Bellman-Ford algorithm
    for (uint _ = 0; _ < nb_nodes - 1; _++)
    {
        updates = 0;
        // For each link in the links array, attempt to update shortest distances for each node.
        for (uint j = 0; j < links_size; j++)
        {
            uint node_from = links[j][0];
            uint node_to = links[j][1];
            int64_t cost = links[j][2];

            // If a shorter distance is found, store it in the dist array and update the path array
            if ((dist[node_from] != INT64_MAX) && (dist[node_from] + cost < dist[node_to]))
            {
                dist[node_to] = dist[node_from] + cost;
                path[node_to] = node_from;
                updates++;
            }
        }

        // If no update was made during the previous iteration, exit the loop
        if (updates == 0)
        {
            break;
        }
    }

    // Check for negative cycle in the graph
    for (uint k = 0; k < links_size; k++)
    {
        uint node_from = links[k][0];
        uint node_to = links[k][1];
        int64_t cost = links[k][2];

        // If a shorter distance is still found, there is a negative cycle
        if ((dist[node_from] != INT64_MAX) && (dist[node_from] + cost < dist[node_to]))
        {
            printf("Negative cycle detected\n");
            return 1;
        }
    }

    return 0;}

I would like to optimize performance as much as possible, with the limitation that the code should remain readable and fluid and the algorithm should not become overly complicated. Also, it is important to keep the same input and output data as now, the code must detect negative cycles and cover corner cases.

I have read interesting stuff which I'd like to implement, (full descriptions are here: https://en.wikipedia.org/wiki/Shortest_path_faster_algorithm)

The basic idea of SPFA is the same as the Bellman-Ford algorithm in that each vertex is used as a candidate to relax its adjacent vertices. The improvement over the latter is that instead of trying all vertices blindly, SPFA maintains a queue of candidate vertices and adds a vertex to the queue only if that vertex is relaxed. This process repeats until no more vertex can be relaxed.

The performance of the algorithm is strongly determined by the order in which candidate vertices are used to relax other vertices. In fact, if Q is a priority queue, then the algorithm pretty much resembles Dijkstra's. However, since a priority queue is not used here, two techniques are sometimes employed to improve the quality of the queue, which in turn improves the average-case performance (but not the worst-case performance). Both techniques rearrange the order of elements in Q so that vertices closer to the source are processed first. Therefore, when implementing these techniques, Q is no longer a first-in, first-out queue, but rather a normal doubly linked list or double-ended queue.

Also, I have read that binary heap and Fibonacci heap might be interesting structures to keep element ordered. Is it a good idea to investigate this direction? (wouldn't it be even better than the trick with the queue they talk about?)

More generally, what would you advise?

EDIT: This post has a continuation here: Bellman-Ford optimisation in C with Shortest Path Algorithm (SPFA) and Small Label first (SLF)

Answer 1

    for (uint _ = 0; _ < nb_nodes - 1; _++)

Maybe this was python code translated into C?!? Repect the norms of the community. Even though _ is a valid identifier that we can sneak past the compiler, that doesn't make it a good identifier.

Think about having a conversation with a colleague over the phone. Are we really going to talk about this line of code by reciting "underscore" three times? The name is essentially saying "nothing to see here, don't even pronounce me." Yet after initializing it we need to be concerned with it twice more. Please fix this.

And when in doubt, choose size_t for an array index. Then let the compiler take it from there, in case there's things we'd like to prove about its maximum magnitude.

---

There's a comment above memset(dist, 0x7f, ..., but it doesn't illuminate the intent of the memset. At first I thought "positive infinity!" until I noticed the value is 0x7f7f7f7f7f7f7f7f. A value like 0xdeadbeef would have been more helpful.

---

Signed link distances apparently are constrained to fall within some range of values, smaller than what the C compiler allows for. The range is not documented in narrative nor comments. The range is not checked by an assert or similar test. We perform signed comparisons against dist elements. It is hard for caller to know if he is submitting valid inputs, and it is hard to know if we get back correct results, for some nebulous definition of "correct".

---

Here's the int32_t declaration:

sint links[][3]

Here's the use:

            int64_t cost = links[j][2];

The upcast is unexpected. Please declare cost to be a signed 32-bit quantity. Or describe the typical distribution of path lengths so we know how many orders of magnitude we're talking about.

More generally, the motivating use case was never introduced, nor example values. It appears it's important to describe how both distances and costs are range limited in your business use case, and perhaps introduce appropriate high-level types. This comes up with e.g. comparing distance against INT64_MAX instead of, say, MAX_DISTANCE. I'm not going to attempt to scroll through any more of this source.

---

This code appears to achieve some of its design goals, in that it runs without crashing and computes correct results for some digraphs, even ones with a constrained set of edges having negative weights.

No example data or unit tests appeared in this submission.

I would not be willing to delegate or accept maintenance tasks for the codebase in its current form.

Answer 2

A few pieces of advice you can consider:

• As far as I'm aware, documentation comments are conventionally immediately before the declaration, not between the signature and the body of the implementation.
• I think you meant to memset dist with 0xff/-1 (all bits set) rather than 0x7f (one bit unset).
• It would make more sense to declare updates when it's initialized to 0, rather than at the start of the function, to prevent it from getting used where it shouldn't be used.
• Why do you have typedefs for the 32-bit integers, but not the 64-bit integer?
• Why is the signature line-wrapped in the implementation but not the declaration?
• What is this check intended to do? dist[node_from] != INT64_MAX
• To give optimizing compilers more power, you can add the restrict keyword to the pointer/array parameters.