flyod算法：

　　　　对于起点与终点，引入第三点p，d[s][t]=min(d[s][t],d[s][p]+d[p][t])；

　　　　代码：//k为引入点

 1 for(int i=0;i<=n;i++)
 2         for(int j=0;j<=n;j++)
 3             if(i==j)d[i][j]=0;
 4             else    d[i][j]=1e9;//边的初始化，
 5 
 6 
 7 
 8 for(int k=0;k<n;k++)                    //
 9             for(int i=0;i<n;i++)                //
10             for(int j=0;j<n;j++)                //
11             d[i][j]=min(d[i][j],d[i][k]+d[k][j]);//flyod核心算法，就四行

View Code

spfa算法：（介绍部分摘自http://www.cnblogs.com/scau20110726/archive/2012/11/18/2776124.html）

是一种求单源最短路的算法

算法中需要用到的主要变量

int n; //表示n个点，从1到n标号

int s,t; //s为源点，t为终点

int d[N]; //d[i]表示源点s到点i的最短路

int p[N]; //记录路径（或者说记录前驱）

queue <int> q; //一个队列，用STL实现，当然可有手打队列，无所谓

bool vis[N]; //vis[i]=1表示点i在队列中 vis[i]=0表示不在队列中

几乎所有的最短路算法其步骤都可以分为两步

1.初始化

2.松弛操作

初始化： d数组全部赋值为INF（无穷大）；p数组全部赋值为s（即源点），或者赋值为-1，表示还没有知道前驱

然后d[s]=0; 表示源点不用求最短路径，或者说最短路就是0。将源点入队；

　　　　（另外记住在整个算法中有顶点入队了要记得标记vis数组，有顶点出队了记得消除那个标记）

队列+松弛操作

读取队头顶点u，并将队头顶点u出队（记得消除标记）；将与点u相连的所有点v进行松弛操作，如果能更新估计值（即令d[v]变小），那么就更新，另外，如果点v没有在队列中，那么要将点v入队（记得标记），如果已经在队列中了，那么就不用入队

以此循环，直到队空为止就完成了单源最短路的求解

SPFA可以处理负权边

定理: 只要最短路径存在，上述SPFA算法必定能求出最小值。

证明：

　　每次将点放入队尾，都是经过松弛操作达到的。换言之，每次的优化将会有某个点v的最短路径估计值d[v]变小。所以算法的执行会使d越来越小。由于我们假定图中不存在负权回路，所以每个结点都有最短路径值。因此，算法不会无限执行下去，随着d值的逐渐变小，直到到达最短路径值时，算法结束，这时的最短路径估计值就是对应结点的最短路径值。（证毕）

期望的时间复杂度O(ke)，其中k为所有顶点进队的平均次数，可以证明k一般小于等于2。

判断有无负环：

　　如果某个点进入队列的次数超过N次则存在负环（SPFA无法处理带负环的图）

ps：spfa也是引入第三点p，d[s][t]=min(d[s][t],d[s][p]+d[p][t])；

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define MAX 220
 5 vector<pair<int,int> >mp[220];//图的邻接表的偷懒做法，mp[x][y]
 6 int inque[220],dis[220];
 7 int n,m;
 8 
 9 void init(void)
10 {
11     for(int i=0;i<MAX;i++)
12         mp[i].clear();
13     for(int i=0;i<MAX;i++)
14         dis[i]=1e9;
15     memset(inque,0,sizeof(inque));
16 }
17 
18 int main(void)
19 {
20     while(cin>>n>>m)
21     {
22         init();
23         for(int i=0;i<m;i++)
24         {
25             int x,y,z;
26             scanf("%d%d%d",&x,&y,&z);
27             mp[x].push_back(make_pair(y,z));
28             mp[y].push_back(make_pair(x,z));
29         }
30         int a,b;
31         scanf("%d%d",&a,&b);
32         queue<int>q;
33         inque[a]=1,dis[a]=0,q.push(a);
34         while(!q.empty())
35         {
36             int x=q.front();
37             q.pop();
38             inque[x]=0;
39             for(int i=0;i<mp[x].size();i++)
40             {
41                 int v=mp[x][i].first;
42                 if(dis[v]>dis[x]+mp[x][i].second)
43                 {
44                     dis[v]=dis[x]+mp[x][i].second;
45                     if(inque[v]==1)continue;
46                     q.push(v);
47                     inque[v]=0;
48                 }
49             }
50         }
51         if(dis[b]==1e9)
52             printf("%d
",-1);
53         else
54             printf("%d
",dis[b]);
55     }
56 }

View Code

dij算法：

　　dij算法其实就是在spfa的算法上进行了优化，把inque数组删了，改用优先队列。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define MAX 220
 5 vector<pair<int,int> >mp[220];//图的邻接表的偷懒做法，mp[x][y]
 6 int dis[220];
 7 int n,m;
 8 
 9 void init(void)
10 {
11     for(int i=0;i<MAX;i++)
12         mp[i].clear();
13     for(int i=0;i<MAX;i++)
14         dis[i]=1e9;
15 }
16 
17 int main(void)
18 {
19     while(cin>>n>>m)
20     {
21         init();
22         for(int i=0;i<m;i++)
23         {
24             int x,y,z;
25             scanf("%d%d%d",&x,&y,&z);
26             mp[x].push_back(make_pair(y,z));
27             mp[y].push_back(make_pair(x,z));
28         }
29         int a,b;
30         scanf("%d%d",&a,&b);
31         priority_queue<pair<int,int> >q;
32         dis[a]=0;q.push(make_pair(-dis[a],a));
33         while(!q.empty())
34         {
35             int x=q.top().second;
36             q.pop();
37             for(int i=0;i<mp[x].size();i++)
38             {
39                 int v=mp[x][i].first;
40                 if(dis[v]>dis[x]+mp[x][i].second)
41                 {
42                     dis[v]=dis[x]+mp[x][i].second;
43                     q.push(make_pair(-dis[v],v));
44                 }
45             }
46         }
47         if(dis[b]==1e9)
48             printf("%d
",-1);
49         else
50             printf("%d
",dis[b]);
51     }
52 }

View Code