3
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • 5
    $\begingroup$ C++ ints take up the same amount of space regardless of their value. $\endgroup$
    – Derek Elkins left SE
    Commented Mar 13, 2018 at 1:06
  • $\begingroup$ 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. $\endgroup$
    – Peter Taylor
    Commented Mar 14, 2018 at 8:55

1 Answer 1

Reset to default
4
$\begingroup$

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.

If you used a negative value, you'd have to treat it as a special case which is a lot less nice.

Note that in classic algorithms, we often disregard the size of the stored numbers (RAM model, uniform cost model). If that is not a good model for your application you have to describe more closely how you represent numbers, and in particular infinity. In practice, you can represent infinity either by a special value that is larger than any number (that's the C++ constant you mention), or you just use the maximum weight you see in the input graph plus one.

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.