最短路练习

算法一：Floyed算法 O(n^3)

1 for(int k = 1; k <= n; ++k) //中转结点！！！！
2         for(int i = 1; i <= n; ++i)
3             for(int j = 1; j <= n; ++j)
4                 dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);

这个算法复杂度有点高，所以我们推荐下一个算法。

算法二：Dijkstra算法 O(n^2) ：求某个结点到其它所有结点的最短路，但无法用于存在负权边的图

这个算法复杂度低一些，主要思想就是先设定起点 dis[i] = 0, mark[i] = 1; 然后对剩下所有未被打标记 (mask[j] == 0) 的结点进行一次O(n)的扫描，找出距离当前顶点最近的结点，将其加入顶点所在的集合T中，集合T中的结点到起点的最短路是全部是目前已经能确定的，所以我们可以通过这些结点再去扩充结点，T中每增加一个结点，就需要对所有未打标记的结点进行重新计算，计算经过新加入的结点到达起点的路径是否比之前不经过该新结点的路径短，若是，更新此结点的dis的值，否，就不用暂时不用管这个结点。所以我们给出如下代码：

 1 // 这里我们以1为起点，n为终点
 2 memset(mark, 0, sizeof(mark));
 3 mark[1] = 1;
 4 dis[1] = 0;
 5 for(int i = 1; i <= n; ++i) dis[i] = M[1][i];
 6 
 7 for(int i = 1; i < n; ++i){
 8     int MIN = INF, pos;
 9     for(int j = 1; j <= n; ++j){
10         if(mark[j] == 0 && dis[j] < MIN){
11             MIN = dis[j];
12             pos = j;
13         }
14     }
15 
16     mark[pos] = 1;
17     for(int j = 1; j <= n; ++j){
18         if(mark[j] == 0 && dis[j] > (dis[pos] + M[pos][j])){
19             dis[j] = dis[pos] + M[pos][j];
20         }
21     }
22 }

此算法还可以利用优先队列优化成O(nlogn)的算法，思想是一样的，代码如下：

 1 // 这里我们以1为起点，n为终点
 2 typedef pair<int, int> P;
 3 
 4 int start = 1;
 5 memset(mark, 0, sizeof(mark));
 6 memset(dis, INF, sizeof(dis)); // 注意，必须将dis初始化为INF
 7 dis[start] = 0;
 8 priority_queue<P, vector<P>, greater<P> > q;
 9 q.push(P(0,start));
10 while(!q.empty()){
11     P t = q.top(); q.pop();
12     //加上这句是因为，某个结点入队之后，其dis值可能会改变，
13     //所以一个结点在队列中可能存在多个pair对，为了避免重复
14     //我们加上这条语句
15     if(mark[t.second] == 1) continue;
16     mark[t.second] = 1;
17 
18     for(int i = 1; i <=n; ++i){
19         if(!mark[i] && dis[i] > dis[t.second] + M[t.second][i]){
20             dis[i] = dis[t.second] + M[t.second][i];
21             q.push(P(dis[i], i));
22         }
23     }
24 }

算法三：SPFA

这个算法是比较高效的算法，可以用于处理负权边，具体做法就是，利用一个队列，每次从队列中取出一个结点，并且对所有结点扫描一遍，判断所有扫到的结点经过取出的结点到达自身的距离是否能更小，若更小则更新结点值并且尝试将该结点加入队列中(若该结点已经在队列中则不需要再次加入到队列中)，否则不进行处理。具体算法实现如下：

 1 int start = 1;
 2 queue<int> q;
 3 memset(dis, INF, sizeof(dis));
 4 memset(mark, 0, sizeof(mark));
 5 dis[start] = 0;
 6 mark[start] = 1;
 7 q.push(start);
 8 while(!q.empty()){
 9     int t = q.front(); q.pop();
10     mark[t] = 0;
11     for(int i = 1; i <= n; ++i)
12         if(dis[i] > dis[t] + M[t][i]){
13             dis[i] = dis[t] + M[t][i];
14             if(!mark[i]){
15                 q.push(i);
16                 mark[i] = 1;
17             }
18         }
19 }

以上，可以利用 https://vjudge.net/problem/HDU-2544 来检验正确性