<p>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.</p>

CC BY-SA 3.0
2015-08-15T06:45:58.017Z
This question might be more suitable for [cs.se].
Kaveh
CC BY-SA 3.0
2015-08-16T10:12:52.270Z
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](https://en.wikipedia.org/wiki/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 [CS.SE]).
Juho
<shortest-path>
In a shortest path between two nodes, find if a certain node is unique
Satabdi Aditya
# In a shortest path between two nodes, find if a certain node is unique

(Asked by: username_0 on 2015-08-14)

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.

**Tags:** shortest-path
> **Comments:**
> **username_1**: This question might be more suitable for [cs.se].  
> **username_2**: 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](https://en.wikipedia.org/wiki/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 [CS.SE]).  

---

## 0 answers

