Representing edge absence in adjacency matrix of weighted graph

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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)