1
$\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.

$\endgroup$
  • 5
    $\begingroup$ C++ ints take up the same amount of space regardless of their value. $\endgroup$ – Derek Elkins Mar 13 '18 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 Mar 14 '18 at 8:55
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.

$\endgroup$
  • $\begingroup$ I think I understand it now. I was initially under the impression that the comparison could be reversed with negative numbers i.e. new_weight < old_weight, but I now see why would that lead to erroneous answers. $\endgroup$ – Tazik_S Mar 13 '18 at 16:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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