最短路径算法代码python回溯

以下是Python中使用回溯法实现最短路径算法的示例代码：

def find_shortest_path(graph, start, end, path=[]):
    """
    使用回溯法寻找图中的最短路径
    :param graph: 图的邻接矩阵表示
    :param start: 起点
    :param end: 终点
    :param path: 当前路径
    :return: 最短路径
    """
    path = path + [start]
    if start == end:
        return path
    shortest_path = None
    for node in graph[start]:
        if node not in path:
            new_path = find_shortest_path(graph, node, end, path)
            if new_path:
                if shortest_path is None or len(new_path) < len(shortest_path):
                    shortest_path = new_path
    return shortest_path

其中，`graph` 是图的邻接矩阵表示，`start` 和 `end` 分别是起点和终点。函数使用递归实现回溯，每次将当前节点加入路径中，如果当前节点为终点，则返回当前路径。否则，遍历当前节点的所有邻居节点，如果邻居节点未被访问过，则递归调用函数，将邻居节点作为新的起点，终点不变，继续搜索路径。如果找到了一条新的路径，则比较其长度与当前最短路径长度，如果更短，则更新最短路径。最终返回最短路径。