3
$\begingroup$

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?

$\endgroup$
6
$\begingroup$

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

$\endgroup$
  • $\begingroup$ But in your graph, the node $Q$ has an infinite degree. $\endgroup$ – avakar Jun 13 '15 at 16:59
  • $\begingroup$ @avakar that's true, but easy to fix. Add a path originating at A and imitate the construction on the P side. $\endgroup$ – Yuval Filmus Jun 13 '15 at 17:00
  • $\begingroup$ It seems A is a new player who did not get introduced to the audience. I suppose you mean to do a symetric constuction $P_0, P_1, .. P_i ... ... Q_i ... Q_1, Q_0$ and have edges $(P_i,Q_i)$ with weight $1/2^{i-1}$., thother weights being unchanged on the $P$ side, and symmetrical to that on the $Q$ side. $\endgroup$ – babou Jun 13 '15 at 22:21
  • 1
    $\begingroup$ @Jules I wrote out the construction in full. You can check that the maximal degree is $3$. The path $P_0-Q_0$ is shortest in terms of number of edges, but not in terms of total weight of edges. $\endgroup$ – Yuval Filmus Jun 14 '15 at 3:57
  • 1
    $\begingroup$ @Jules That seems to be exactly what I wrote in my first comment, up to a factor 2 (i.e. my lower limit is 4 instead of 2 as I just took th initial construction and symmetrized it (as suggested by Yuval Filmus), thus doubling the path length. $\endgroup$ – babou Jun 14 '15 at 9:36

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.