HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Locally finite graph without an optimal path

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
withoutfinitepathgraphoptimallocally

Problem

If I have a locally finite graph (every node has finite number of neighbors) with positive edge weights, is it possible for there to be a path between some start node and goal node but no shortest path between them?

I think that it can only happen if the goal node is somewhere in the infinity, but then we wouldn't be saying that the goal node actually exists, right?

Could anyone help me on this?

Solution

It can happen. Let $P_0,P_1,\ldots$ be a one-way infinite path, where $P_0$ is the start node, and the edge from $P_i$ to $P_{i+1}$ has weight $1/2^{i+1}$. Let $Q_0,Q_1,\ldots$ be a one-way infinite path, where $Q_0$ is the goal node, and the edge from $Q_i$ to $Q_{i+1}$ has weight $1/2^{i+1}$. Connect $P_i$ to $Q_i$ with an edge of weight $1/2^{i-2}$. The weight of the path $P_0-\cdots-P_i-Q_i-\cdots-Q_0$ is
$$(1/2+\cdots+1/2^i)+1/2^{i-2}+(1/2^i+\cdots+1/2) = \\
(1+\cdots+1/2^{i-1})+1/2^{i-2} = \\
(2-1/2^{i-1})+1/2^{i-2} = \\
2+1/2^{i-1} \, .
$$ So for each $\epsilon > 0$ there is a $P-Q$ path of weight $2+\epsilon$, but there is no path of weight $2$.

Context

StackExchange Computer Science Q#43559, answer score: 6

Revisions (0)

No revisions yet.