无向图中给定单源,求到某点路径中最小权边的最大值。
可以将其看成求单源最短路径的变种,使用dijkstra算法+最大堆。
单源最短路径的算法是:记录从源点出发访问每一点i的最短路为value[i],对于当前所有value中的最小值点u,进行BFS式的操作,对于每条Edge(u,v),如果edge(u,v)+value[u] < value[v] 则更新v。这是一个贪心的算法,可以证明每次出队列的u最优。
本题求的是最大单边,对此稍做修改。记录每条边目前能承受的最大重量为value[i](即从源点所遍历路径的最小权中的最大值)。设u是当前结点,对于每条Edge(u,v),当......
阅读全文