1.Floyd
Floyd是先枚举转接点，从而达到更新最小值的目的。到后期好像O(n^3) 像闹着玩一样，但在一些n<=100的环境下还是很好用的。。。
1 inline void Floyd(int x){
2 memset(dis,88,sizeof(dis));
3 for(register int i=1,x,y;i<=m;++i){
4 scanf("%d%d",&x,&y);
5 scanf("%d",dis[x][y]);dis[y][x]=dis[x][y];
6 }
7 for(register int i=1;i<=n;++i) dis[i][i]=0;
8 for(register int k=1;k<=n;++k){
9 for(register int i=1;in;++i){
10 for(register int j=1;jn;++j){
11 if(dis[i][k]+dis[k][j]<dis[i][j]) dis[i][j]=dis[i][k]+dis[k][j];
12 }
13 }
14 }
15 }
2.Dijkstra
Dijkstra在图论问题中主要的优点是较稳定，不会被特殊设计的测试点卡掉，还可以记录路径（噩梦。。。）下面为堆优化的代码。
1 inline void dijkstra(int x) {
2 priority_queue<node> q;
3 q.push_back(node{0, s});
4 for(register int i=1;i<=n;++i) dis[i]=100000000;
5 dis[x]=0;
6 memset(judge,0,sizeof(judge));
7 while(!q.empty()){
8 node xx=q.top(); q.pop();
9 int to=xx.to;
10 if(judge[to]) continue;//如果这个点已经被提出过了，直接抛弃 （适用于那种松弛之后重复放入队列的点）
11 judge[to]=true;
12 for(register int i=0;i<q[to].size();++i){
13 Edge& e = edges(q[to][i]);
14 if(e.dist+dis[to]<dis[e.to]&&dis[to]<100000000) {
15 dis[e.to]=e.dist+dis[to];
16 p[e.to]=G[to][i]; //记录路径
17 q.push_back(Edge(dis[e.to], e.to));//把松弛过后点的d值重新放入队列
18 }
19 }
20 }
21 }
3.Spfa
Spfa是笔者比较青睐的算法。Spfa可以在压队的过程中判断是否存在环，还可以处理负环。
1 inline void Spfa(int x){
2 queue<int> q;
3 memset(dis,88,sizeof(dis));
4 memset(judge,0,sizeof(judge);
5 dis[x]=0;
6 q.push(x);
7 while(q.size()){
8 int xx=q.front(); q.pop;
9 for(register int i=first[xx];i;i=a[i].next){
10 int to=a[i].to;
11 if(dis[to]+a[i].w<dis[xx]){
12 dis[xx]=dis[to]+a[i].w;
13 if(!judge[to]){
14 q.push(to); judge[to]=1;
15 nums[y]++;//记录加入次数
16 if(nums[y]>n) return 0;
17 //如果这个点加入超过n次，说明存在负圈，直接返回
18 }
19 }
20 }
21 }
22 }