稠密图用邻接矩阵，稀疏图用邻接表

  判断方法：边数m是点n的n^2级别的话就是稠密图，m是n级别的就是稀疏图

一：单源最短路——所有边权均为正数

1.朴素dijkstra算法O(n^2)：

  适用于单源最短路所有边权均为正数（可以有环，但是不能有负权边）的稠密图（点数n很小，边数m很大）

  思路：

　　集合S为已经确定最短路径的点集。
　　1. 初始化距离
　　　　一号结点的距离为零，其他结点的距离设为无穷大（看具体的题）。
　　2. 循环n次，每一次将集合S之外距离最短X的点加入到S中去（这里的距离最短指的是距离1号点最近。点X的路径一定最短，基于贪心）。

　　　然后用点X更新X邻接点的距离。

 1 #include 
 2 #include 
 3 #include 
 4 using namespace std;
 5 
 6 int n,m;
 7 const int N=510;
 8 int dist[N];    //dist[i]表示从1走到i的目前最短距离 
 9 int g[N][N];    //g[a][b]表示有向边a-->b的权重
10 bool st[N];        //记录是否找到了源点到该节点的最短距离 
11 
12 int dijkstra()
13 {
14     memset(dist,0x3f,sizeof dist);
15     dist[1]=0;        //将点1的距离为0，其余均为正无穷 
16     
17     for(int i=2;i<=n;i++)    //点1已经确定最短路距离为0，不需要下面的步骤 
18     {
19         int t=-1;        //t表示在还未确定最短路的点中找距离最近的点
20         
21         for(int j=1;j<=n;j++)//在还未确定最短路的点中找距离最近的点
22         {
23             if(!st[j]&&(t==-1||dist[t]>dist[j])) t=j;
24         }
25         
26         for(int k=1;k<=n;k++)    //通过更改的t来进一步求其他点的最短路 
27         {
28             dist[k]=min(dist[k],dist[t]+g[t][k]);
29         }
30         
31         st[t]=1;
32 
33     }
34     
35     if(dist[n]==0x3f3f3f3f)return -1;
36     else return dist[n];
37     
38 }
39 
40 int main()
41 {
42     scanf("%d%d",&n,&m);
43     
44     memset(g,0x3f,sizeof g);
45     while(m--)
46     {
47         int x,y,z;
48         scanf("%d%d%d",&x,&y,&z);
49         g[x][y]=min(g[x][y],z);        //存在重边，取最短的距离 
50     }
51     
52     
53     printf("%d",dijkstra());
54     
55     
56     
57     return 0;
58 }

2.堆优化版dijkstra算法O(mlogn):

  适用于单源最短路所有边权均为正数（可以有环，但是不能有负权边）的稀疏图

  思路：

　　堆优化版的dijkstra是对朴素版dijkstra进行了优化，在朴素版dijkstra中时间复杂度最高的寻找距离最短的点O(n^2)可以使用最小堆优化。
　　1. 一号点的距离初始化为零，其他点初始化成无穷大。
　　2. 将一号点放入堆中。
　　3. 不断循环，直到堆空。每一次循环中执行的操作为：
　　　　弹出堆顶（与朴素版diijkstra找到S外距离最短的点相同，并标记该点的最短路径已经确定）。
　　　　用该点更新临界点的距离，若更新成功就加入到堆中。

 1 #include 
 2 #include 
 3 #include 
 4 using namespace std;
 5 
 6 typedef pair<int,int> pii;
 7 const int N=1e6+10;
 8 
 9 int n,m;
10 int e[N],ne[N],h[N],idx,w[N];
11 int dist[N];
12 bool st[N];
13 
14 
15 void add(int x,int y,int z)
16 {
17     e[idx]=y;ne[idx]=h[x];h[x]=idx++;
18     w[idx]=z;
19     //有重边也不要紧
20     //假设1->2有权重为2和3的边，再遍历到点1的时候2号点的距离会更新两次放入堆中
21     //这样堆中会有很多冗余的点
22     //但是在弹出的时候还是会弹出最小值2+x（x为之前确定的最短路径）
23     //标记st为1，所以下一次弹出3+x会continue不会向下执行。
24 }
25 
26 int dijkstra()
27 {
28     memset(dist,0x3f,sizeof dist);
29     dist[1]=0;
30     priority_queue,greater> heap;
31     //first为距离，second为点的编号 
32     heap.push({0,1});
33     
34     while(heap.size())
35     {
36         auto t=heap.top();
37         heap.pop();
38         int ver = t.second, distance = t.first;
39         //ver表示在没有找到最短路的点中距离最近的点的编号
40         //distance表示1到这个点的距离 
41     
42         if(st[ver])continue;
43         //因为st数组就是判断这个点的最短路是否已经被确定了
44         //如果是true说明这个点已经确定了，没必要再进行下去了（重边情况）
45         
46         
47         st[ver]=1;
48         
49         for(int i=h[ver];i!=-1;i=ne[i])
50         {
51             int j=e[i];        //i只是个下标idx，e中在存的是i这个下标对应的点
52             if(dist[j]>distance+w[i])
53             {
54                 dist[j]=distance+w[i];
55                 heap.push({dist[j],j});    //把更新后的点放入堆中 
56             }
57             
58         }
59     }
60     
61     if(dist[n]==0x3f3f3f3f)return -1;
62     return dist[n];
63 }
64 
65 int main()
66 {
67     scanf("%d%d",&n,&m);
68     
69     memset(h,-1,sizeof h);
70     memset(w,0x3f,sizeof w);
71     while(m--)
72     {
73         int x,y,z;
74         scanf("%d%d%d",&x,&y,&z);
75         add(x,y,z);
76     }
77     
78     printf("%d",dijkstra());
79     
80     
81     return 0;
82 }

二：单源最短路——边权有负数存在

3.bellman-ford算法O(mn):

　　用处：当题中要求从 1">1 号点到 n">n 号点的最多经过 k">k 条边时，再用bellman_ford算法

 1 #include 
 2 #include 
 3 using namespace std;
 4 
 5 const int N=510,M=1e4+10;
 6 int dist[N],last[N];　　// dist[x]存储1到x的最短路距离
 7 int n,m,k;
 8 
 9 struct Edge
10 {
11     int a,b,w;
12 }edgs[M];
13 
14 void bellman_ford()
15 {
16     memset(dist,0x3f,sizeof dist);
17     dist[1]=0;
18     //题中要求从 1 号点到 n 号点的最多经过 k 条边
19     //也正是因为这个要求，所以才要用bellman 
20     for(int i=1;i<=k;i++)        
21     {
22         memcpy(last,dist,sizeof dist);    
23         //保留上一次迭代的dist的副本，防止跨层数更新
24         for(int j=0;j)
25         {
26             auto e = edgs[j];
27             dist[e.b] = min(dist[e.b], last[e.a] + e.w);
28         }
29     }
30 }
31 
32 int main()
33 {
34     scanf("%d%d%d",&n,&m,&k);
35     
36     for(int i=0;i)
37     {
38         int x,y,z;
39         scanf("%d%d%d",&x,&y,&z);
40         edgs[i]={x,y,z};
41     }
42     
43     bellman_ford();
44     
45     if(dist[n]>=0x3f3f3f3f/2)puts("impossible");
46     //因为有负边，可能最后是正无穷-2 
47     else printf("%d\n",dist[n]);
48     
49     
50     
51     
52     return 0;
53 }

4.spfa算法平均情况下 O(m)O(m)，最坏情况下  O(nm):

　　spfa不可存在负权回路，不可以求最多经过k条边

　　spfa是bellman的优化。Bellman_ford算法会遍历所有的边，但是有很多的边遍历了其实没有什么意义，我们只用遍历那些到源点距离变小的点所连接的边即可，只有当一个点的前驱结点更新了，该节点才会得到更新；因此考虑到这一点，我们将创建一个队列每一次加入距离被更新的结点。

　　spfa和dijkstra的区别：

1] Dijkstra算法中的st数组保存的是当前确定了到源点距离最小的点，且一旦确定了最小那么就不可逆了(不可标记为true后改变为false)；SPFA算法中的st数组仅仅只是表示的当前发生过更新的点，且spfa中的st数组可逆(可以在标记为true之后又标记为false)。顺带一提的是BFS中的st数组记录的是当前已经被遍历过的点。
2] Dijkstra算法里使用的是优先队列保存的是当前未确定最小距离的点，目的是快速的取出当前到源点距离最小的点；SPFA算法中使用的是队列(你也可以使用别的数据结构),目的只是记录一下当前发生过更新的点。

　　bellman与spfa最后判断条件的区别：

Bellman_ford算法里最后的判断条件写的是dist[n]>0x3f3f3f3f/2;而spfa算法写的是dist[n]==0x3f3f3f3f;其原因在于Bellman_ford算法会遍历所有的边，因此不管是不是和源点连通的边它都会得到更新；但是SPFA算法不一样，它相当于采用了BFS，因此遍历到的结点都是与源点连通的，因此如果你要求的n和源点不连通，它不会得到更新，还是保持的0x3f3f3f3f。

　　spfa不可存在负权回路，bellman可以：

Bellman_ford算法可以存在负权回路，是因为其循环的次数是有限制的因此最终不会发生死循环；但是SPFA算法不可以，由于用了队列来存储，只要发生了更新就会不断的入队，因此假如有负权回路请你不要用SPFA否则会死循环。

　　求负环一般用spfa：

方法是用一个cnt数组记录每个点到源点的边数，一个点被更新一次就+1，一旦有点的边数达到了n那就证明存在了负环。

 1 #include 
 2 #include 
 3 #include 
 4 using namespace std;
 5 
 6 const int N=1e5+10;
 7 int n,m;
 8 int dist[N];
 9 int h[N],ne[N],e[N],idx,w[N];
10 bool st[N];         
11 
12 void add(int x,int y,int z)
13 {
14     e[idx]=y;ne[idx]=h[x];w[idx]=z;h[x]=idx++;
15 }
16 
17 void spfa()
18 {
19     queue<int>q;
20     memset(dist,0x3f,sizeof dist);
21     dist[1]=0;
22     q.push(1);
23     while(q.size())
24     {
25         int t=q.front();
26         q.pop();
27         st[t]=0;    //代表之后该节点如果发生更新可再次入队 
28         for(int i=h[t];i!=-1;i=ne[i])
29         {
30             int j=e[i];
31             if(dist[j]>dist[t]+w[i])
32             {
33                 dist[j]=dist[t]+w[i];
34                 if(!st[j])    //当前已经加入队列的结点，无需再次加入队列
35                             //即便发生了更新也只用更新数值即可，重复添加降低效率 
36                 {            
37                     st[j]=1;
38                     q.push(j);
39                 }
40             }
41         }
42     }
43 }
44 
45 int main()
46 {
47     scanf("%d%d",&n,&m);
48     memset(h,-1,sizeof h);
49     for(int i=1;i<=m;i++)
50     {
51         int x,y,z;
52         scanf("%d%d%d",&x,&y,&z);
53         add(x,y,z);
54     }
55     
56     spfa();
57     if(dist[n]==0x3f3f3f3f)puts("impossible");
58     else printf("%d\n",dist[n]);
59     
60     
61     
62     
63     return 0;
64 }

判断负环的代码：

 1 #include 
 2 #include 
 3 #include 
 4 using namespace std;
 5 
 6 const int N=1e5+10;
 7 int n,m;
 8 int dist[N],cnt[N];
 9 int h[N],ne[N],e[N],idx,w[N];
10 bool st[N];         
11 
12 void add(int x,int y,int z)
13 {
14     e[idx]=y;ne[idx]=h[x];w[idx]=z;h[x]=idx++;
15 }
16 
17 bool spfa()
18 {
19     queue<int>q;
20     //不用初始化dist,如果存在负环,那么dist不管初始化为多少,都会被更新
21     
22     for(int i=1;i<=n;i++)    
23     //不仅仅是1了， 因为点1可能到不了有负环的点， 因此把所有点都加入队列
24     {
25         q.push(i);
26         st[i]=1;
27     }
28     
29 
30     while(q.size())
31     {
32         int t=q.front();
33         q.pop();
34         st[t]=0;    //代表之后该节点如果发生更新可再次入队 
35         for(int i=h[t];i!=-1;i=ne[i])
36         {
37             int j=e[i];
38             if(dist[j]>dist[t]+w[i])
39             {
40                 dist[j]=dist[t]+w[i];
41                 cnt[j]=cnt[t]+1;
42                 if(cnt[j]>n)return 0;
43                 if(!st[j])    //当前已经加入队列的结点，无需再次加入队列
44                             //即便发生了更新也只用更新数值即可，重复添加降低效率 
45                 {            
46                     st[j]=1;
47                     q.push(j);
48                 }
49             }
50         }
51     }
52     return 1;
53 }
54 
55 int main()
56 {
57     scanf("%d%d",&n,&m);
58     memset(h,-1,sizeof h);
59     for(int i=1;i<=m;i++)
60     {
61         int x,y,z;
62         scanf("%d%d%d",&x,&y,&z);
63         add(x,y,z);
64     }
65     
66     if(spfa())puts("No");
67     else puts("Yes");
68     
69     
70     
71     
72     return 0;
73 }

三：多源汇最短路

5.floyd算法O(n^3):

　　多源汇最短路只能用floyd

 1 #include 
 2 
 3 using namespace std;
 4 
 5 const int N=210,INF=1e9;
 6 int n,m,k;
 7 int d[N][N];
 8 
 9 void floyd()
10 {
11     for(int c=1;c<=n;c++)
12         for(int i=1;i<=n;i++)
13             for(int j=1;j<=n;j++)
14                 d[i][j]=min(d[i][j],d[i][c]+d[c][j]);
15         
16     
17 }
18 
19 int main()
20 {
21     scanf("%d%d%d",&n,&m,&k);
22     
23     for(int i=1;i<=n;i++)
24         for(int j=1;j<=n;j++)
25         {
26             if(i==j)d[i][j]=0;
27             else d[i][j]=INF;
28         }
29     
30     for(int i=1;i<=m;i++)
31     {
32         int x,y,z;
33         scanf("%d%d%d",&x,&y,&z);
34         d[x][y]=min(d[x][y],z);
35     }
36     
37     floyd();
38     
39     while(k--)
40     {
41         int x,y;
42         scanf("%d%d",&x,&y);
43         if(d[x][y]>=INF/2)puts("impossible");
44         else printf("%d\n",d[x][y]);
45     }
46     
47     
48     
49 }

最最最最后的总结：

1.Dijkstra-朴素  O(n2)：

　　1.初始化距离数组, dist[1] = 0, dist[i] = inf;
　　2.for n次循环 每次循环确定一个min加入S集合中，n次之后就得出所有的最短距离
　　3.将不在S中dist_min的点->t
　　4.t->S加入最短路集合
　　5.用t更新到其他点的距离

2.Dijkstra-堆优化  O(mlogm)：

　　1.利用邻接表，优先队列
　　2.在priority_queue,greater> heap;中将返回堆顶
　　3.利用堆顶来更新其他点，并加入堆中类似宽搜

3.Bellman_ford O(nm)O(nm)
　　1.注意连锁想象需要备份, struct Edge{int a,b,c} Edge[M];
　　2.初始化dist, 松弛 dist[x.b] = min(dist[x.b], backup[x.a]+x.w);
　　3.松弛k次，每次访问m条边

4.Spfa O(n)～O(nm)O(n)～O(nm)
　　1.利用队列优化仅加入修改过的地方
　　2.for k次
　　3.for 所有边利用宽搜模型去优化bellman_ford算法
　　4.更新队列中当前点的所有出边

5.Floyd O(n3)O(n3)
　　1.初始化d
　　2.k, i, j 去更新d