patternMinor
Locally finite graph without an optimal path
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?
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$.
$$(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.