5

I made weight directed graph, just like this

6
0 3 4 INFINITY INFINITY INFINITY
INFINITY 0 INFINITY 7 INFINITY INFINITY
INFINITY 3 0 5 11 INFINITY
INFINITY INFINITY INFINITY 0 6 3
INFINITY INFINITY INFINITY INFINITY 0 4
INFINITY INFINITY INFINITY INFINITY INFINITY 0

at first, I used some integer value to express infinity like 99 or 20000. but when I find it is wrong, v5 -> v4 must be express infinity but some integer value is expressed.

ex : Shortest Path from v2 to v3 : v2 v3 (length : 200000)

is there any infinity value for integer?

friend of mine says ~(1<<31) but it doesn't work

Cœur
  • 37,241
  • 25
  • 195
  • 267
Silvester
  • 2,819
  • 5
  • 22
  • 23

3 Answers3

9

Unlike floating-point types, integer types don't have a standard value for infinity. If you have to have one, you'll have to pick a value yourself (e.g. INT_MAX) and correctly handle it throughout your code. Note that if you do this, you can use the special value in assignments and comparisons, but not in arithmetic expressions.

NPE
  • 486,780
  • 108
  • 951
  • 1,012
  • +1 And casting an infinite float to an int [is undefined behavior](http://stackoverflow.com/questions/3986795/casting-float-inf-to-integer). – netcoder Nov 16 '11 at 14:16
4

Infinity doesn't exist for integers. What your friend suggested was the biggest number in a 32 bit signed integer, but that still is not infinity. That also introduces the possibility of overflow if you add it to something (for example in shortest path), you actually might end up getting a smaller number. So don't do it.

The proper way to do it, is to handle infinity case by case. Use a flag for infinity, for example that same ~(1<<31), or perhaps even better, -1 and in your code, whenever you want to add two values, check if either of them is equal to this flag (equal to infinity), set the result to infinity without actually doing any summations. Or when you are checking if one value is smaller than another, check if one is equal to this flag (equal to infinity), then the other is definitely smaller, again without actually doing the comparison.

Shahbaz
  • 46,337
  • 19
  • 116
  • 182
0

edit: didn't realize you were specifying integers.

a solution might be to use '-1' instead of infinity as your cardinal value. if i recall correctly, directed graphs should not have negative values anyway.

drjrm3
  • 4,474
  • 10
  • 53
  • 91
  • Directed Graphs are allowed to use negative values when you are applying all-pair shortest path algorithm like Floyd-Warshall. – Programmer Sep 28 '14 at 13:01