1
$\begingroup$

So my exact problem is, I have to find if there is any node which is unique in a shortest path. For example, in a square, any node is in the shortest path between any two adjacent nodes,but it is not unique because even if we delete that we will have another shortest path of exactly the same length.

$\endgroup$
  • $\begingroup$ This question might be more suitable for Computer Science. $\endgroup$ – Kaveh Aug 15 '15 at 6:45
  • 1
    $\begingroup$ Suppose you have a shortest path between $s$ and $t$. Using two breadth first searches (one from $s$, the other from $t$), measure the distance to every other vertex, and drop the vertices that cannot be on any shortest $s$-$t$ path. Basically, you then have a level structure: any shortest $s$-$t$ path can be formed by choosing a vertex from each level. Now it's easy to see if there are any vertices that must be on any shortest $s$-$t$ path. (With that being said, the question is indeed more appropriate for Computer Science). $\endgroup$ – Juho Aug 16 '15 at 10:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.