BFS+Other Algorithm

Network Delay Time

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.
Example 1:


image.png

image.png

这道题,因为边带有权重,且题目给定了起始点,所以本质上是求单源最短路径的问题,可以通过Dijkstra算法求得图中每个点到初始点的最短距离,然后返回这些距离里面最长的一个就可以了。

Dijkstra算法

Dijkstra算法,和贪心有些类似:每次遍历都只寻找初始点A距离最近的点。比如下图:A到E的最短路径就是A->D->C->E。那么这个步骤是如下的:
Dijkstra需要几个辅助信息:

  1. 一个记录各点与A最近距离的数组: dist
  2. 一个纪录下已获得最近距离的点的数组 visited
  3. 按情况而异,这里我们使用连接矩阵表示各个点之间的连接情况,如果点点之间有连接,那么矩阵对应位置的值就是权重,否则设置为一个较大的数字,cost矩阵
  • 初始化dist数组,dist[i] 的值为A到i的距离,若A-i相连,值为权重,否则为无穷大
    先从A出发,找遍所有结点,找到和A最近的点,注意:如果节点之间不相连,则权重为无穷大,这也是为什么cost矩阵含有无穷大的原因。
  • 我们找到了与A直接相连的最近的是D,所以,下一个开始的点是D。
    从离A最近的点D开始,与D相连的点有ABCE,其中A,D已经被visited了,我们发现D的加入,导致了A到B点的最短距离为 A-D-B,所以此处,我们相应的需要更新 A-B的距离
  • 重复上面的步骤寻找,直到遍历完所有的点,这样,每次只能更新一个点,也就是遍历一遍只找到一个离A最近的点
image.png
#define INFINITY 9999

class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int N, int K) {
        vector<int> distance(N+1,INFINITY);
        vector<vector<int>> cost(N+1,vector<int>(N+1,INFINITY));
        vector<bool> visited(N+1,false);
        int tmp_min;
        int nextnode;
        
        for(auto item:times)
            cost[item[0]][item[1]] = item[2];
        for(int i=1;i<=N;i++)
            distance[i] = cost[K][i];
       
        distance[K] = 0;
        visited[K] = true;
        int count = 1;
        while(count<N-1){
            tmp_min = INFINITY;
            for(int i=1;i<=N;i++){
                if(distance[i]<tmp_min && !visited[i]){
                    tmp_min = distance[i];
                    nextnode = i;
                }
            }
            visited[nextnode] = true;
            for(int i=1;i<=N;i++){
                if((tmp_min+cost[nextnode][i])<distance[i] && !visited[i]){
                    distance[i] = tmp_min+cost[nextnode][i];
                    }
                }

            count++;
            }

        int max_time = *max_element(distance.begin()+1,distance.end());

        return max_time==INFINITY?-1:max_time;
    }
};
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

  • 专业考题类型管理运行工作负责人一般作业考题内容选项A选项B选项C选项D选项E选项F正确答案 变电单选GYSZ本规程...
    小白兔去钓鱼阅读 11,171评论 0赞 13
  • 1736年,瑞士数学家Euler(欧拉)在他的一篇论文中讨论了格尼斯七桥问题,由此诞生了一个全新的数学分支——图论...
    不困于情阅读 4,615评论 0赞 9
  • 1. 关于诊断X线机准直器的作用,错误的是()。 (6.0 分) A. 显示照射野 B. 显示中心线 C. 屏蔽多...
    我们村我最帅阅读 11,778评论 0赞 5
  • Dijkstra Dijkstra属于单源最短路径算法,用于计算一个顶点到其他所有顶点的最短路径。 使用前提:不能...
    ducktobey阅读 703评论 0赞 0
  • https://zh.visualgo.net/graphds 浅谈图形结构https://zh.visualgo...
    狼之独步阅读 4,526评论 0赞 0

友情链接更多精彩内容