# Finding the shortest path of undirected ring graph python

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()```

Added by vanderlay on Sat, 18 Jan 2020 17:59:38 +0200