一起刷leetcode(743):Network Delay Time——Dijkstra算法的堆优化(附动画)


题目地址
https://leetcode.com/problems/ ... tion/

题号
743

题目描述
There are N network nodes, labelled 1 to N.

Given times, a list of travel times as directed edges times[i] = (u, v, w), where u is the source node, v is the target node, and w is the time it takes for a signal to travel from source to target.

Now, we send a signal from a certain node K. How long will it take for all nodes to receive the signal? If it is impossible, return -1.

Note:
N will be in the range [1, 100].
K will be in the range [1, N].
The length of times will be in the range [1, 6000].
All edges times[i] = (u, v, w) will have 1 <= u, v <= N and 1 <= w <= 100.

中文解释
这是很有意思的一道新题,大意就是这样的:
给定N个节点的网络拓扑图,以及该拓扑图的的每一条有向边的传递信息的耗时times,再给定源点K,从K向整个网络拓扑图传播信息,求最早什么时候,每个节点都能接收到信息。

其实只要稍微想一下,就转化为我们所熟悉的带权有向图的单源最短路径问题。关于最短路径问题,相信同学们都能各显神通了。在这里,给一种常用方案,其时间复杂度还不错,就是:堆优化版本的Dijkstra算法。

算法的辅助空间
设G=(V,E),那么需要的辅助空间如下:
1、邻接表adjList,Space=O(V+E)
2、顶点的dist数组distArray,记录每个顶点的Dijkstra长度,Space=O(V)
3、pre数组,用于记录每个顶点的前趋顶点,由于pre是用数组表示树的典型结构,所以也可以叫它并查集,Space=O(V)
4、最小堆(优先队列)queue,用于存储有向图的边,每条边有四个字段{start,end,w,dist},start表示出发点,end表示到达点,w表示边的权值,dist表示Dijkstra长度,Space=O(E)
那么,整个算法的空间复杂度就显而易见了,S(N)=O(V+E),适用于稀疏图的情况;若是稠密图,则可以采用邻接矩阵,空间复杂度为O(V^2)

算法描述
一、根据题目输入,创建邻接表;这个算法相信每位同学都会,就不再赘述了
二、初始化dist数组,int[] distArray=new int[N+1],每个元素都初始化为0
三、初始化并查集pre,int[] pre=new int[N+1],每个元素都初始化为0
四、初始化最小堆queue,并把原点k所对应邻接表的所有边添加进最小堆,K添加进并查集,其pre不变,还是0
五、咱主要的核心算法就是这一步
1、弹出dist最小的边p,这时候,p的dist就是p的到达点end的dist,同时,将p的到达点end添加进并查集,end的父节点就是p的出发点start,即:
pre[p.end] = p.start;
distArray[p.end]=p.dist;
2、遍历p的到达点end所对应的邻接表,更新所有边edge的dist,并把edge添加到优先队列中,即:
for (edge : adjList[p.end]) {
edge.dist = edge.w+p.dist;
queue.offer(edge);
}
3、不断执行步骤1和步骤2,直到所有顶点都已经添加到并查集或者最小堆为空;如果并查集未填满但是最小堆为空,则说明某些点不能通过源点到达,直接返回-1。在执行步骤1和步骤2的时候,要注意略过已经在并查集中的点
六、返回distArray中最大的dist
七、如果还需要输出每个顶点的最短路径,则选取合适的搜索算法遍历pre数组
可见,整个算法的时间主要消耗在核心的第五步,由于至多把每条边添加进最小堆一次,且堆的插入、弹出均是logN,所以整个算法的时间复杂为O(ElogE),E是边集数组times的长度
仅仅从文字表述上似乎还不太好理解核心算法第五步,我们不妨举一个例子来说明。

算法图示
1、对于以下有向图,假设1是源点,一开始并查集和最小堆都是空的

请输入图片名称

2、将源点1添加进并查集,其dist记为0,将1的所有邻边添加进最小堆,并从图中删除源点1及其所有邻边

请输入图片名称

3、找到最小堆中dist最小的边{1,2,10,10}

请输入图片名称

4、从堆中删除最小边{1,2,10,10},顶点2的dist更新为10,并将顶点2添加进并查集

请输入图片名称

5、将顶点2的所有邻边添加进最小堆,并从图中删除顶点2及其所有邻边

请输入图片名称

6、找到最小堆中dist最小的边{1,4,30,30}

请输入图片名称

7、从堆中删除最小边{1,4,30,30},顶点4的dist更新为30,并将顶点4添加进并查集

请输入图片名称

8、将顶点4的所有邻边添加进最小堆,并从图中删除顶点4及其所有邻边

请输入图片名称

9、找到最小堆中dist最小的边{4,3,20,50}

请输入图片名称

10、从堆中删除最小边{4,3,20,50},顶点3的dist更新为50,并将顶点3添加进并查集

请输入图片名称

11、将顶点3的所有邻边添加进最小堆,并从图中删除顶点3及其所有邻边

请输入图片名称

12、这时候,最小边有两个,分别是{2,3,50,60}以及{3,5,10,60},但是,顶点3已经在并查集当中了,故无需再考虑,所以选取边{3,5,10,60}

请输入图片名称

13、从堆中删除最小边{3,5,10,60},顶点5的dist更新为60,并将顶点5添加进并查集

请输入图片名称

14、将顶点5的所有邻边添加进最小堆,并从图中删除顶点5及其所有邻边,显然,顶点5的邻接表为空

请输入图片名称

15、此时,虽然并查集已满,但是堆中任然有边。不过,可以直接结束循环,因为这些边是无需再考虑的。比如边{4,5,60,90}的dist为90,大于并查集中的顶点5的60,边{2,3,50,60}的dist为60,大于并查集中顶点3的50,故可以直接舍弃这些不可能造成最优解的边。

请输入图片名称

自此,pre数组、distArray数组均已填充完毕。
本人还特地制作了一个小视频,便于大家更好的理解Dijkstra算法的执行过程:
http://v.youku.com/v_show/id_X ... .html



如何输出所有的路径呢?使用类似于反序输出单链表的递归算法即可

完整代码实现
import java.util.ArrayList;
import java.util.PriorityQueue;

/**
 * 最短路径问题,迪杰斯特拉算法
 */
public class Solution {
    public int networkDelayTime(int[][] times, int N, int K) {
        // 创建邻接表
        ArrayList<ArrayList<NetwordEdge>> adjList = new ArrayList<ArrayList<NetwordEdge>>(
                N + 1);
        for (int i = 0; i <= N; i++) {
            adjList.add(new ArrayList<NetwordEdge>());
        }
        for (int[] edge : times) {
            adjList.get(edge[0])
                    .add(new NetwordEdge(edge[0], edge[1], edge[2]));
        }
        // 初始化顶点的dist数组
        int[] distArray = new int[N+1];
        // 初始化并查集
        int[] pre = new int[N + 1];
        // 初始化优先队列
        PriorityQueue<NetwordEdge> queue = new PriorityQueue<NetwordEdge>();
        for (NetwordEdge edge : adjList.get(K)) {
            queue.offer(edge);
        }
        // cnt记录并查集的大小
        int cnt = 1;
        int max = 0;
        while (!queue.isEmpty() && cnt <= N) {
            // 弹出dist最小的边
            NetwordEdge p = queue.poll();
            // 遇到原点或者已经在并查集当中的顶点,略过
            if (p.end == K || pre[p.end] != 0) {
                continue;
            }
            // 记录并查集的父节点
            pre[p.end] = p.start;
            // 更新顶点的dist
            distArray[p.end]=p.dist;
            if (p.dist > max) {
                max = p.dist;
            }
            cnt++;
            // 更新p所对应邻接表的所有边的dist,并插入到优先队列
            for (NetwordEdge edge : adjList.get(p.end)) {
                // 遇到原点或者已经在并查集当中的顶点,略过
                if (edge.end == K || pre[edge.end] != 0) {
                    continue;
                }
                edge.dist += p.dist;//或者: edge.dist = edge.w+p.dist;
                queue.offer(edge);
            }
        }
        // 输出路径
        for (int i = 1; i <= N; i++) {
            printPath(pre, i);
            System.out.println();
        }
        if (cnt != N) {
            // 不能到达所有顶点
            return -1;
        } else {
            return max;
        }
    }

    private void printPath(int[] ufList, int i) {
        if (ufList[i] == 0) {
            System.out.print(i + " ");
        } else {
            printPath(ufList, ufList[i]);
            System.out.print(i + " ");
        }
    }
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[][] times = {{1, 5, 100}, {1, 4, 30}, {1, 2, 10}, {2, 3, 50},
                {3, 5, 10}, {4, 3, 20}, {4, 5, 60}};
        System.out.println(solution.networkDelayTime(times, 5, 1));
    }
}
class NetwordEdge implements Comparable<NetwordEdge> {
    //开始
    public int start;
    //结束
    public int end;
    //权值
    public int w;
    //dist权值
    public int dist;
    public NetwordEdge(int start, int end, int w) {
        super();
        this.start = start;
        this.end = end;
        this.w = w;
        this.dist = w;
    }
    @Override
    public int compareTo(NetwordEdge o) {
        return this.dist - o.dist;
    }
}


输出:
1
1 2
1 4 3
1 4
1 4 3 5
60

去掉相关的print语句,即可在leetcode上得到一个AC的结果,Submission Detail还是比较令人满意的:

请输入图片名称

有了Dijkstra算法的基础,再去解决最小生成树问题就轻而易举了,依然是利用堆(排序)+并查集,Prim、Dijkstra、Kruscal这三个算法的思想都是类似的,有兴趣的同学可以查阅相关资料。
已邀请:

要回复问题请先登录注册

返回顶部