Can't a path between two non adjacent nodes in a graph be 'undefined', rather than '$\infty$'?

Question

The words 'infinity' and 'undefined' are two different notions but linked in a sense that infinity value is also not known. My question is why do we often consider a path between two non-adjacent nodes in a graph as infinity? Why can't we say that the distance is 'undefined'?

Answer 1

We give something the value $\infty$ to indicate that it should "act like infinity": that is,

• when you start at $\infty$, then add (or subtract) any finite number, the value stays $\infty$.
• in any comparison between two values, one of which is $\infty$ and one of which is finite, the infinite one should be bigger.

Suppose we have three vertices in the graph: $u$, $v$, and $w$. There is an edge of length $1$ between $u$ and $v$, an edge of length $2$ between $v$ and $w$, and no edge between $u$ and $w$ directly. What is the shortest path from $u$ to $w$?

Well, it's the path $u \to v \to w$, of course: that's the only way to get from $u$ to $w$. It has length $1+2=3$, but it should be the shortest path no matter what those lengths are.

Now suppose we say that there is an edge of length $\infty$ between $u$ and $w$. Does that change anything? No: the direct path $u \to w$ has a length of $\infty$, which is still longer than the path $u \to v \to w$ of length $3$, and it will stay longer no matter what (finite) lengths the edges $uv$ and $vw$ have. So "no edge at all" and "edge of length $\infty$" behave identically.

Now suppose we say that there is an edge of undefined length between $u$ and $w$. What is the shortest path from $u$ to $w$? We don't know: $u \to v \to w$ has length $3$, $u \to w$ has undefined length, and the comparison between these is undefined as well. As soon as we have an edge with undefined length, we stop being able to make coherent comparisons.

If you say "okay, whenever there is an edge with undefined length along a path, that path counts as longer than any path without such an edge", then you are only redefining $\infty$ and so you might as well say that the edge you're talking about has length $\infty$.

Answer 2

My question is why do we always consider the distance between two non-adjacent nodes in a graph as infinity? Why can't we say that the distance is 'undefined'?

We absolutely can! If you want to do that, go for it.

Now, before I say anything else, let me mention that the word "undefined" is an adjective, never a noun. If somebody says "the distance between X and Y is undefined", that means "the phrase 'the distance between X and Y' does not have a definition". It does not mean "the distance between X and Y is something which is called 'undefined'".

So, when it comes to the distance between two nodes in a graph, we have two options, both of which are perfectly fine:

• We can define the distance. Usually, we define it as infinity, because this makes some amount of sense, and it's a useful thing to do.
• We can refuse to define the distance. In other words, we can leave it undefined. (We can't "define it as undefined"—that's an oxymoron.) This also makes some amount of sense, and it's somewhat useful as well (because if we do this, then the distance is always a number).