Representing edge absence in adjacency matrix of weighted graph

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开发者_如何学Go two nodes?

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.

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.

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)