# Bellman-Ford optimisation in C

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);

*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.
*     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.
**/ {

// 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; _++)
{
// For each link in the links array, attempt to update shortest distances for each node.
for (uint j = 0; j < links_size; j++)
{

// 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;
}
}

// If no update was made during the previous iteration, exit the loop
{
break;
}
}

// Check for negative cycle in the graph
for (uint k = 0; k < links_size; k++)
{

// 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)

• When you say "remain readable", do you actually think that #defines like uint and sint and variable names like _ are good for readability? Mar 20 at 17:08
• The quoted text talks about priority queues, and in your addendum you talk about heaps. Are you not aware that heaps are the data structures upon which efficient priority queues are usually implemented? Some sources even treat "heap" and "priority queue" as synonyms. Mar 20 at 17:14
• @JohnBollinger I was not, I'm just discovering those terms (I'm new to C even though I coded a bit more in Python and Java) That's actually the main reason why I'm asking here, I don't want to mess with this stuff. Mar 20 at 17:18
• Do you in fact need to handle graphs having negative weights? Because if not, then Dijkstra's algorithm is probably a better choice than any variation on Bellman-Ford. Mar 20 at 17:27
• Welcome to Code Review! Incorporating advice from an answer into the question violates the question-and-answer nature of this site. You could post improved code as a new question, as an answer, or as a link to an external site - as described in I improved my code based on the reviews. What next?. I have rolled back the edit, so the answers make sense again. Mar 21 at 11:18

    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.

• that was indeed a code translated from python :) I have edited my message with a new version of the code and corrected the different points as I understood them. The upcast to int64_t is mandatory (non-negotiable request from higher authorities), as well as the choice of the other cast. But this might change in the future, hence the use of define in the beginning of the code to make a change easier. Also, I'm still working on the remark on the value range Mar 21 at 10:21
• @c.leblanc Please read What should I do when someone answers my question? for information specific to Code Review Stack Exchange. Mar 21 at 10:41
• @c.leblanc Yep, that's what I'm referring to. "If you'd like to share the revised version of your code, the following are acceptable (and by no means mandatory) options: Posting a new question. If you incorporate advice from one or more answers, but are still unsure that the code is as good as it should be, then post a new question with your revised code. For the benefit of other users, add mutual links: mention the previous question in the new question, and add a comment on the old question linking to the follow-up question." Meanwhile, I've added an optimization idea to my answer. Mar 21 at 11:02

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.
• I edited a new version of the code with fixes. I don't think I need 0xff/-1 ? I just want to set all value to the maximum possible (in theory the Bellman Ford algorithm is using infinity there). Also dist[node_from] != INT64_MAX was used because its is not necessary to check updates if the cost to the node is still set to maximum value (//infinity), anyway this piece of code doesn't make sense in the new version. Mar 21 at 10:41
• @c.leblanc memset with 0x7f results in 0x7f7f7f7f, not 0x7fffffff. Mar 21 at 10:43
• I'm really not an expert on that. But it seems to work (I have the correct value if I print the element of the array). Also I couldn't use 0x7fffffff in memset but I could use 0x7f, which is interpreted or smth as the correct number when associated to an int64_t ? Mar 21 at 10:58
• @c.leblanc: For historical reasons, memset takes an int parameter even though it sets bytes, not words.
– You
Mar 21 at 12:42
• @Davislor: They have int64_t *dist and a length in number of int64_t elements. Almost certainly they should be looping over that array and filling it with INT64_MAX. IDK why you'd want memcpy for this, unless you mean using it to do 4-byte aliasing-safe stores. If you did want 4-byte patterns inside an array of int64_t, you could loop over the int64_t elements storing 0x7fffffff7fffffff. Mar 21 at 17:02