leetcode [Graph] No.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:

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

解题思路

通过对题目的分析，我们可以将问题抽象成如下描述：有一个无负权边的有向图，若给定一个源点，求该点到其他所有点的最短路径。如果存在某个点，从源点出发没法到达该点，则返回-1，否则返回源点到所有点中的最长路径。

既然是最短路径问题，那么我们可以直接用Dijkstra算法进行求解，算法复杂度为$O(n^2)$O(n2)。

代码：

class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int N, int K) {
    	//记录Dijkstra算法中某个点是否已经访问
        vector<bool> flag(N + 1, false);
        //记录Dijkstra算法中，目前阶段求得的最小值
		vector<int> dis(N + 1, -1);
        int time = 0;
        //记录算法是否应该结束的标志
        bool end = false;
        
        //算法初始化
        flag[K] = true;
		dis[K] = 0;
        for (int i = 1; i <= N; i++) {
        	time = getTimes(times, K, i);
        	if (time != -1) {
        		dis[i] = time;
			}
		}
		//Dijkstra算法
		while (!end) {	
			end = true;
			int min = -1;
			for (int i = 1; i <= N; i++) {
				if (!flag[i] && dis[i] != -1 && (min == -1 || dis[i] < dis[min])) {
					min = i;
					end = false;
				}
			}
			if (min != -1) {
				flag[min] = true;
				int base = dis[min];
				for (int i = 1; i <= N; i++) {
					int plus = getTimes(times, min, i);
					if (plus != -1 && (dis[i] == -1 || dis[i] > base + plus)) {
						dis[i] = base + plus;
					}
				}
			}
		}

		//在所有最短路径中寻找最长的一条路径，以及查找是否有一个点源点无法到达
		int max = 0;
		for (int i = 1; i <= N; i++) {
			if (dis[i] == -1) return -1;
			if (dis[i] > max) max = dis[i];
		}
		return max;
    }
    
private:
	//从times中查找从u到v是否有一条边，若有则返回边的权值，否则返回-1
	int getTimes(vector<vector<int>>& times, int u, int v) {
		for (auto iter : times) {
			if(iter[0] == u && iter[1] == v) {
				return iter[2];
			}
		}
		return -1;
	}
};

运行结果：
从上述代码可以看出，我们直接使用了题目给出的所有边的列表，这就导致算法的复杂度又上升了一点，为$O(mn^2)$O(mn2)，$n$n表示图中点的个数，$m$m表示图中的个数，可以看出，当输入的是一个稠密图（即图中边的个数比较多的时候），则算法会运行的很慢。

运行结果也证明了上述分析：Time Limit Exceeded（运行超时）。

改进：
我们对上述代码进行一些改进，不直接使用题目所给的边列表，而是根据这个边列表，构建一个邻接矩阵，核心算法不做改变。

改进代码：

class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int N, int K) {
    	//邻接矩阵map
    	vector<vector<int>> map;
    	//初始化邻接矩阵
    	for (int i = 0; i < N + 1; i++) {
    		map.push_back(vector<int>(N+1, -1));
		}
		//根据题目所给边列表构建邻接矩阵
		for (auto iter : times) {
			map[iter[0]][iter[1]] = iter[2];
		}
    	
    	//记录Dijkstra算法中某个点是否已经访问
        vector<bool> flag(N + 1, false);
        //记录Dijkstra算法中，目前阶段求得的最小值
		vector<int> dis(N + 1, -1);
        int time = 0;
        //记录算法是否应该结束的标志
        bool end = false;
        
        //算法初始化
        flag[K] = true;
		dis[K] = 0;
        for (int i = 1; i <= N; i++) {
        	time = map[K][i];
        	if (time != -1) {
        		dis[i] = time;
			}
		}
		
		
		//Dijkstra算法
		while (!end) {
			end = true;
			int min = -1;
			for (int i = 1; i <= N; i++) {
				if (!flag[i] && dis[i] != -1 && (min == -1 || dis[i] < dis[min])) {
					min = i;
					end = false;
				}
			}
			if (min != -1) {
				flag[min] = true;
				int base = dis[min];
				for (int i = 1; i <= N; i++) {
					int plus = map[min][i];
					if (plus != -1 && (dis[i] == -1 || dis[i] > base + plus)) {
						dis[i] = base + plus;
					}
				}
			}
		}
	//在所有最短路径中寻找最长的一条路径，以及查找是否有一个点源点无法到达
		int max = 0;
		for (int i = 1; i <= N; i++) {
			if (dis[i] == -1) return -1;
			if (dis[i] > max) max = dis[i];
		}
		return max;
    }
};

运行结果：

可以看出Dijkstra算法的效率还是挺高的，其实这一题不仅限于可以用Dijkstra算法实现，所有单源最短路径算法均可以用来求解该题，例如，SPFA等，小伙伴们可以尝试利用其它算法进行求解。