# Dijkstra's algorithm: why are distances initialized to infinity and not some negative number?

I'm a high schooler who has been self-learning graph algorithms for a month or two now.

I was wondering why the distance array in Dijkstra's algorithm is initialized to infinity (INT_MAX in C++) when it could just be set to a negative number? Since Dijkstra's isn't even used for negative numbers, why isn't the distance array set to some arbitrary negative number (say, -1) and instead a very large number which takes up far more space? It's possible that I'm overestimating the space occupied in memory by a very large INT value.

I'd appreciate any constructive feedback.

• C++ ints take up the same amount of space regardless of their value. – Derek Elkins Mar 13 '18 at 1:06
• On a practical point, it's common to use INT_MAX >> 1 to represent infinity. Certainly you want to do this if using an adjacency matrix instead of adjacency lists, because it means that you save a special case by not needing to worry about overflow. – Peter Taylor Mar 14 '18 at 8:55

If you read the algorithm closely, you'll not that edge weight relaxation is triggered if new_weight < old_weight. This comparison is naturally true if all undiscovered edges are initialized with infinity (or, in programming, the largest representable value), and the algorithm correctly picks up the first "real" value it finds.