Python实现Dijkstra算法

描述

地图上有 m 条无向边，每条边 (x, y, w) 表示位置 x 到位置 y 的权值为 w。从位置 0 到 位置 n 可能有多条路径。我们定义一条路径的危险值为这条路径中所有的边的最大权值。

请问从位置 0 到 位置 n 所有路径中最小的危险值为多少？

• 1 <= m <= 500，1 <= n <= 50，0 <= x, y <= n，1 <= w <= 100000。
• 题目保证位置 0 一定可以通往位置 n。
• 题目保证地图中不包含重边。

样例
样例 1:

给出 n = 2, m = 2, x = [0, 1], y = [1, 2], w = [1, 2]，返回2。
输入:
2
2
[0,1]
[1,2]
[1,2]
输出:
2

解释：
路径 1：0->1->2（危险值：2）
最小危险值为2。

样例 2:

给出 n = 3, m = 4, x = [0, 0, 1, 2], y = [1, 2, 3, 3], w = [1, 2, 3, 4]，返回3。
输入:
3
4
[0,0,1,2]
[1,2,3,3]
[1,2,3,4]
输出:
3

解释：
路径 1：0->1->3（危险值：3）
路径 2：0->2->3（危险值：4）
最小危险值为3。

class Solution:
    """
    @param n: maximum index of position.
    @param m: the number of undirected edges.
    @param x: 
    @param y: 
    @param w: 
    @return: return the minimum risk value.
    """
    def getMinRiskValue(self, n, m, x, y, w):
        start = 0  #起点编号
        end = n  #终点编号


        #构建一个邻接散列表
        graph = {}
        for i,j,k in zip(x,y,w):
            if i not in graph.keys():
                graph[i] = {}
            graph[i][j] = k
        graph[end] = {}


        #构建一个散列表存储从起点到该节点的开销
        Inf = float('inf')
        costs = {}
        for i,j,k in zip(x,y,w):
            if i == start:
                costs[j] = k
            else:
                costs[j] = Inf

                
        #构建一个散列表存储各节点的父节点，用于记录路径
        parents = {}
        for i,j,k in zip(x,y,w):
            if i == start:
                parents[j] = start
            else:
                parents[j] = None

                
        #构建一个数组，记录处理过的节点
        processed = []

        #构建一个函数，在未处理的节点中找出开销最小的节点
        def find_lowest_cost_node(costs):
            lowest_cost = Inf
            lowest_cost_node = None
            for node in costs:
                cost = costs[node]
                if cost < lowest_cost and node not in processed:
                    lowest_cost = cost
                    lowest_cost_node = node
            return lowest_cost_node

        node = find_lowest_cost_node(costs)
        while node is not None:
            cost = costs[node]
            neighbors = graph[node]
            for n in neighbors.keys():
                new_cost = max([cost,neighbors[n]])
                if costs[n] > new_cost:
                    costs[n] = new_cost
                    parents[n] = node
            processed.append(node)
            node = find_lowest_cost_node(costs)
        #获取最小危险值
        cost = costs[end]
        return cost