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