2
votes

I'm trying to implement in C some graph algorithms, using an adjacency matrix as support data structure. I need to implement a weighted graph, with weigths represented by a real number.

Given that 0 and negative numbers would be a correct weight for an edge, how can I represent the absence of an edge between two nodes?

3
Hmmm ... maybe C99's nan()pmg

3 Answers

2
votes

You could use instead of a number (double) a structure like this:

struct weight
{
   double weight;
   bool edge_exists;
};

and create an adjacency matrix of weight's. So if edge_exists is false there is no reason to check the weight, otherwise weight will be meaningful.

I would use the above if every(?) double could be a possible weight value.

0
votes

What about a nonsensical (I'm guessing you're making the assumption all weights should be positive) number, such as -1?

This would keep the code light (no need to add extra data structures), and it would be simple to remember.

0
votes

If you are using C99 or later you can use the INFINITY macro defined in math.h and assign all non existent edges a weight of INFINITY.

Look here for more details on using infinity in C: How to use nan and inf in C?

(You could also technically use NaN, but it's not guaranteed to be defined and I think using infinity works nicer in a lot a algorithms anyways)