(Dijkstra 最短路) leetcode 743. 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.

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 0 <= w <= 100.

 

这道题说的就是给了我们一些有向边，又给了一个结点K，问至少需要多少时间才能从K到达任何一个结点。其实是一个求带权的有向图的最短路的的问题，由于带权，所以BFS不能用，我们可以用Dijkstra算法、FLoyd算法以及Bellman-Ford算法。参考链接：http://www.cnblogs.com/grandyang/p/8278115.html

这个题中我用Dijkstra算法，其实，Dijkstra算法有比较固定的模板，本质是利用贪心的。Dijkstra算法由于贪心的性质，所以只能解决权都为正的有向图的最短路的问题。

普通的Dijkstra算法的时间复杂度为O(V²)。

C++代码：

int INF = 0x3f3f3f3f; class Solution { public: int networkDelayTime(vector<vector<int>>& times, int N, int K) { int mp[N+1][N+1]; int dis[N+1]; int book[N+1]; for(int i = 1; i <= N; i++){ for(int j = 1; j <= N; j++){ mp[i][j] = INF; } } int len = times.size(); for(int i = 1;i <= len; i++){ int w = times[i-1][2]; int u = times[i-1][0]; int v = times[i-1][1]; if(w < mp[u][v]){ mp[u][v] = w; } } for(int i = 1; i <= N; i++){ dis[i] = mp[K][i]; book[i] = 0; } dis[K] = 0; book[K] = 1; for(int i = 1; i <= N; i++){ int minn = INF,t = K; for(int j = 1; j <= N; j++){ if(book[j] == 0 && dis[j] < minn){ minn = dis[j]; t = j; } } book[t] = 1; for(int j = 1; j <= N; j++){ if(book[j] == 0 && dis[t] + mp[t][j] < dis[j] && mp[t][j] < INF){ dis[j] = dis[t] + mp[t][j]; } } } int sum = 0; for(int i = 1; i <= N; i++){ sum = max(sum,dis[i]); } if(sum == INF) return -1; return sum; } };

如果是基于优先队列的实现方法的话，时间复杂度就是O(E + VlogV)。

转载于:https://www.cnblogs.com/Weixu-Liu/p/10894676.html