加权非定向图中的最长路径

解决加权非定向图中的最长路径问题可以使用动态规划和深度优先搜索两种方法。

下面是使用动态规划的解决方法的代码示例：

def longest_path(graph, start, end):
    # 创建一个数组dp，用于存储从起点到每个节点的最长路径长度
    dp = [float('-inf')] * len(graph)
    dp[start] = 0

    # 遍历所有节点，更新最长路径长度
    for i in range(len(graph)):
        for j in range(len(graph[i])):
            # 获取当前节点的邻居节点和边的权值
            neighbor, weight = graph[i][j]
            # 更新邻居节点的最长路径长度
            dp[neighbor] = max(dp[neighbor], dp[i] + weight)

    return dp[end]

# 示例图的邻接表表示
graph = [[(1, 2), (2, 3)],  # 节点0的邻居节点和对应的边的权值
         [(0, 2), (2, 1), (3, 4)],  # 节点1的邻居节点和对应的边的权值
         [(0, 3), (1, 1), (3, 2)],  # 节点2的邻居节点和对应的边的权值
         [(1, 4), (2, 2)]]  # 节点3的邻居节点和对应的边的权值

start = 0  # 起始节点
end = 3  # 结束节点

print(longest_path(graph, start, end))  # 输出最长路径的长度

另一种解决方法是使用深度优先搜索。下面是使用深度优先搜索的解决方法的代码示例：

def dfs(graph, start, end, visited, max_weight, current_weight):
    # 标记当前节点为已访问
    visited[start] = True

    # 到达终点节点，更新最大路径长度
    if start == end:
        max_weight[0] = max(max_weight[0], current_weight)
        return

    # 遍历当前节点的邻居节点
    for neighbor, weight in graph[start]:
        # 如果邻居节点未访问过，则继续深度优先搜索
        if not visited[neighbor]:
            dfs(graph, neighbor, end, visited, max_weight, current_weight + weight)

    # 回溯时将当前节点标记为未访问
    visited[start] = False

def longest_path(graph, start, end):
    visited = [False] * len(graph)
    max_weight = [float('-inf')]

    dfs(graph, start, end, visited, max_weight, 0)

    return max_weight[0]

# 示例图的邻接表表示
graph = [[(1, 2), (2, 3)],  # 节点0的邻居节点和对应的边的权值
         [(0, 2), (2, 1), (3, 4)],  # 节点1的邻居节点和对应的边的权值
         [(0, 3), (1, 1), (3, 2)],  # 节点2的邻居节点和对应的边的权值
         [(1, 4), (2, 2)]]  # 节点3的邻居节点和对应的边的权值

start = 0  # 起始节点
end = 3  # 结束节点

print(longest_path(graph, start, end))  # 输出最长路径的长度

这两种方法都可以找到加权非定向图中的最长路径。使用动态规划的方法具有更高的时间复杂度，但在某些情况下可能更快，而使用深度优先搜索的方法则适用于小规模的图。