算法设计与分析第四周练习（图论）

Network Delay Time

1. 题目

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.

2. 基础知识

解决这题需要图的相关方面的知识。尤其是图的广度遍历的知识。
具体的遍历过程如下

从某个顶点V出发，访问该顶点的所有邻接点V1，V2…VN。
从邻接点V1，V2…VN出发，再访问他们各自的所有邻接点。
重复上述步骤，直到所有的顶点都被访问过。
此时还有一种特殊得情况就是，当图不是连通图的时候，我们需要从另一个源点出发去遍历。整个算法过程如下：

我们以这个基本的遍历为基础，引入图的非常重要的算法，Dijkstra算法和Bellman-Ford算法。
Dijkstra算法
这个算法是求点对所有点的最短路径的算法，其适用与图没有负边的情况。
Dijkstra算法采用的是一种贪心的策略，声明一个数组dis来保存源点到各个顶点的最短距离和一个保存已经找到了最短路径的顶点的集合：T，
- 初始时，原点 s 的路径权重被赋为 0 （dis[s] = 0）。若对于顶点 s 存在能直接到达的边（s,m），则把dis[m]设为w（s, m）,同时把所有其他（s不能直接到达的）顶点的路径长度设为无穷大。初始时，集合T只有顶点s。
- 从dis数组选择最小值，则该值就是源点s到该值对应的顶点的最短路径，并且把该点加入到T中，OK，此时完成一个顶点，
- 我们需要看看新加入的顶点是否可以到达其他顶点并且看看通过该顶点到达其他点的路径长度是否比源点直接到达短，如果是，那么就替换这些顶点在dis中的值。
- 又从dis中找出最小值，重复上述动作，直到T中包含了图的所有顶点。
Bellman-Ford算法
- 初始化：将除源点外的所有顶点的最短距离估计值 dist[v] ← +∞, dist[s] ←0;
- 迭代求解：反复对边集E中的每条边进行松弛操作，使得顶点集V中的每个顶点v的最短距离估计值逐步逼近其最短距离；（运行|v|-1次）
- 检验负权回路：判断边集E中的每一条边的两个端点是否收敛。如果存在未收敛的顶点，则算法返回false，表明问题无解；否则算法返回true，并且从源点可达的顶点v的最短距离保存在 dist[v]中。

3. 题目分析

这里的目的是求出网络从一个源点发布信息到这个图中，问至少需要多长的时间。这里我们将网络抽象成一个图的结构，从源点到某个点信息的传播可以看成是图的一条路径。那么何时才会有当所有的点都收到信息的时候时间确最短呢？为了时间最少，我们必须确保源点到每一个点的路径是最短的，同时，为了让所有的点都能收到的话，我们必须在这些最短的路径中取需要的时间最长的。那么问题就转化为求图某个点到所有点的最短路径，并取出其中的最大值。再看题目数据的特点，路径的权值是正数，说明Dijkstra算法是合适的，那么Bellman-Ford算法也必定合适。

4. 算法实现

首先，我们需要对图用合适的数据结构表示出来，由于在找最小路径的时候需要遍历同一个起点的所有边，那么我们需要将同一起点的边表示在一起，同时还需要保存权重，所以我最后决定用map<int, vector<vector > > graph;作为本题图的数据结构。

4.1 Dijkstra算法
- 建图：将图用我们决定的数据结构表示出来，map<int, vector<vector > > graph，其中key是边的起点，vector的第一个元素是边的终点，第二个元素是边的权值。
- 确定优先队列的形式，我们这里采用最简单的形式，也就是数组，但为了模拟优先队列，取出队列中的最小的未访问的元素，我们需要一个bool数组。
- 初始化dist和优先队列。
- 从优先队列选择最小值，则该值就是源点s到该值对应的顶点的最短路径，并且把该点加入到T中，OK，此时完成一个顶点。
- 新加入的顶点是否可以到达其他顶点并且看看通过该顶点到达其他点的路径长度是否比源点直接到达短，如果是，那么就替换这些顶点在dis中的值。
- 重复。
4.2 利用队列优化Bellman-Ford算法
由于我们这里的数据结构不是邻接矩阵的形式，对同一个点遍历所有的顶点（包括没有边相连的点）比较困难，并且这步没有实际的意义，所以我们这里用队列优化的Bellman-Ford算法来实现。这样的话，我们只需要遍历那行存在边的顶点。
具体的做法如下

5. 源码

Dijkstra算法

class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int N, int K) {
        /*build a graph
		* the key of map is the source
		* the first element of vector is the target
		* the second is the distance
        */
        int count = 0;
        map<int, vector<vector<int> > > graph;
        for(auto a : times) {
        	vector<int> temp;
        	temp.push_back(a[1]);
        	temp.push_back(a[2]);
        	graph[a[0]].push_back(temp);
        }

        //the min distance
        vector<int> dist(N+1, INT_MAX);
        dist[K] = 0;

        //array to tag weather the element is visited
        vector<int> array_queue(N+1, INT_MAX);
        vector<bool> bool_(N+1, false);
        array_queue[K] = 0;

        int index = 0;
        while(count < N) {
        	int min = INT_MAX;
        	for(int i = 1; i < array_queue.size(); i++) {
        		if(bool_[i] == false) {
        			if(array_queue[i] < min) {
        				min = array_queue[i];
        				index = i;
        			}
        		}
        	}

        	bool_[index] = true;
        	count++;
        	//cout << "index " << index << endl;

        	//find the distance
        	for(int i = 0; i < graph[index].size(); i++) {
        		//cout << "graph[index][i][0] " << graph[index][i][0] << endl;
        		if(dist[graph[index][i][0]] > dist[index] + graph[index][i][1]) {
        			dist[graph[index][i][0]] = dist[index] + graph[index][i][1];
        			array_queue[graph[index][i][0]] = dist[graph[index][i][0]];
        		}
        	}
   	    }
   		int result = -1;
        for(int i = 1; i < N+1; i++) {
        	if(dist[i] == INT_MAX) {
        		return -1;
        	}
        	if(dist[i] > result) {
        		result = dist[i];
        	}
        }
        return result;
    }
};

利用队列优化Bellman-Ford算法

class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int N, int K) {
        /*build a graph
		* the key of map is the source
		* the first element of vector is the target
		* the second is the distance
        */
        int count = 0;
        map<int, vector<vector<int> > > graph;
        for(auto a : times) {
        	vector<int> temp;
        	temp.push_back(a[1]);
        	temp.push_back(a[2]);
        	graph[a[0]].push_back(temp);
        }

        //the min distance
        vector<int> dist(N+1, INT_MAX);
        vector<bool> visited(N+1, false);
        dist[K] = 0;

        queue<int> q;
        set<int> s;
        q.push(K);
        s.insert(K);

        while(!q.empty()) {
        	int index = q.front();
        	s.erase(index);
        	visited[index] = true;
        	//cout << index << endl;
        	q.pop();
        	for(int i = 0; i < graph[index].size(); i++) {
        		if(dist[graph[index][i][0]] > dist[index] + graph[index][i][1]) {
        			dist[graph[index][i][0]] = dist[index] + graph[index][i][1];
        			if(s.find(graph[index][i][0]) == s.end())
        				q.push(graph[index][i][0]);
        		}
        			
        	}
        }

        int result = -1;
        for(int i = 1; i < N+1; i++) {
        	if(dist[i] == INT_MAX) {
        		return -1;
        	}
        	if(dist[i] > result) {
        		result = dist[i];
        	}
        }
        return result;
    }
};

6. 算法复杂度分析

6.1 Dijkstra算法
这里外层循环的复杂度是确定的，为O(n)，整个算法的复杂度取决于内层优先队列的实现，我们这里采用简单的数组实现，也就是说，在我们寻找队列的最小值的时候，我们需要遍历数组，内层也是O(n)，最后整个算法的算法复杂度为O(n*n)。
6.2 利用队列优化Bellman-Ford算法
本来用Bellman-Ford的算法，由于每个点与其他顶点都需要遍历一遍，总的复杂度为O(n*n)，现在优化了以后，只有那行有边存在的才需要遍历，复杂度是降低了。