【Python算法】：n个点m条边有权无向图

【Python算法】：n个点m条边有权无向图

n个点：有个位置
m条边：两点之间存在m条边有权值
有权：每条边代表一个数值
无向：没有规定行进方向

规定：
1、两点之间的行进路线，最终权值为所经过的边的权值的最大值
2、两点之间走法不止一个，最终取最小值为最终走法

问：
两点之间的最终权值为多少

如上图，我们可以将其写为列表形式，前两位是从小到大的的两个点，最后一个代表权值，如
[1, 2, 2] 代表1和2之间的权值是2，以此类推

n,m = 5, 10
road = [[1, 2, 2], [1, 3, 3], [1, 4, 7], [1, 5, 2],
        [2, 3, 4], [2, 4, 9], [2, 5, 5], [3, 4, 4],
        [3, 5, 5], [4, 5, 3]]

def hold(list1, list2):
    jiaoji = list(set(list1)&set(list2))
    need = [i for i in set(list1+list2) if i not in jiaoji]
    need.sort()
    return need

def get(road):
    option = {}
    for i in range (m):
        option[(road[i][0],road[i][1])] = [road[i][2]]
    for i in range (m):
        for j in range(i+1,m):
            dot = hold(road[i][:2], road[j][:2])
            if len(dot)==2:
                if (dot[0],dot[1]) in option.keys():
                    option[(dot[0],dot[1])].append(max([road[i][2],road[j][2]]))
                else:
                    option[(dot[0],dot[1])] = []
                    option[(dot[0],dot[1])].append(max([road[i][2],road[j][2]]))
    road_new = []
    for i in option.items():
        road_new.append(list(i[0])+[min(i[1])])
    if road==road_new:
        print(road_new)
        return road_new
    return get(road_new)

输出结果
所有可能的走法如下，并且最后一位输出最短的权值路径。

例如 [2, 3, 3]：代表 从2走到3最短的权值路径是3，对应路径从图中可以到是2-1-3
例如 [3, 5, 3]：代表 从3走到5最短的权值路径是3，对应路径从图中可以到是3-1-5

[[1, 2, 2], [1, 3, 3], [1, 4, 3], [1, 5, 2], [2, 3, 3], 
[2, 4, 3], [2, 5, 2], [3, 4, 3], [3, 5, 3], [4, 5, 3]]