Recently, in the process of project, we have encountered such a problem: in the undirected ring graph with 15 nodes, we need to find the shortest path between any a and b points.

My approach is to first convert the graph into adjacency matrix and store it as a two-dimensional array. The connected node is 0 and the unconnected node is - 1

```
[[ 0 0 0 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1]
[ 0 0 -1 -1 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1]
[ 0 -1 0 -1 0 0 -1 -1 -1 -1 -1 -1 -1 -1 -1]
[ 0 -1 -1 0 -1 0 -1 -1 -1 0 -1 -1 0 -1 -1]
[-1 0 0 -1 0 -1 0 -1 -1 -1 -1 -1 -1 -1 -1]
[-1 -1 0 0 -1 0 0 0 0 -1 -1 -1 -1 -1 -1]
[-1 -1 -1 -1 0 0 0 -1 -1 -1 -1 -1 -1 -1 -1]
[-1 -1 -1 -1 -1 0 -1 0 -1 -1 0 -1 -1 -1 -1]
[-1 -1 -1 -1 -1 0 -1 -1 0 0 -1 -1 -1 -1 0]
[-1 -1 -1 0 -1 -1 -1 -1 0 0 -1 -1 -1 0 -1]
[-1 -1 -1 -1 -1 -1 -1 0 -1 -1 0 -1 -1 0 -1]
[-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 0 0 0]
[-1 -1 -1 0 -1 -1 -1 -1 -1 -1 -1 0 1 -1 -1]
[-1 -1 -1 -1 -1 -1 -1 -1 -1 0 0 0 -1 0 -1]
[-1 -1 -1 -1 -1 -1 -1 -1 0 -1 -1 0 -1 -1 0]]
```

Then, according to the idea of recursion, the problem is simplified to judge whether the other nodes connected to the current node have an endpoint b

So it can be solved according to the following methods.

```
def calculate_short_jump(self, a):
"""
//Calculating the shortest hops between two nodes in an undirected ring graph
:param a:
:return:
"""
self.min_nodes = []
self.graph1 = self.get_state(self.cur_state)
# print(self.graph1)
actions = self.get_next([a[0]], a[0])
self.fun(actions, [a[0]], a[1])
res = self.min_nodes[0]
for x in self.min_nodes:
if len(res) > len(x):
res = x
return res
def get_next(self, cur, s):
res = []
for i, x in enumerate(self.graph1[s]):
if x == 0 and i not in cur:
res.append(i)
return res
def fun(self, action_space, cur, s):
if not action_space:
return False
for x in action_space:
if x in cur:
continue
if self.graph1[x][s] == 0:
cur.append(x)
cur.append(s)
stack = cur[:]
self.min_nodes.append(stack)
cur.pop()
cur.pop()
else:
cur.append(x)
actions = self.get_next(cur, x)
res = self.fun(actions, cur, s)
cur.pop()
```