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?
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.
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)
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.
