之前对最短路的认识不是很充分，结合之前的博客来重新总结一下最短路的问题的解法。

Floyd算法——小数据杀手

相信最先接触的最短路算法就是Floyd算法了，因为他精简的代码实在是最短路的一股清流，但是 \(n^{3}\) 的时间复杂度甚至不用刻意去卡，只要数据大于500，那基本Floyd是过不去了。
Floyd是一种可以求多源最短路的一种算法，他的核心代码就是三重循环和一个if，一开始把任意两个点之间的距离设为正无穷，然后自己到自己赋为0，然后把题目给出的，直接相连的边的长度存起来，，枚举两个点之间可能间接连接的点，对其进行松弛操作。
luogu P2910

#include<bits/stdc++.h>
using namespace std;
int n,m,ans=0;
int dis[110][110],a[10010];
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	  cin>>a[i];
	for(int i=1;i<=n;i++)
	  for(int j=1;j<=n;j++)
	    cin>>dis[i][j];
	for(int k=1;k<=n;k++)
	  for(int i=1;i<=n;i++)
	    for(int j=1;j<=n;j++)
	      dis[i][j]=min(dis[i][k]+dis[k][j],dis[i][j]);
	for(int i=2;i<=m;i++)
	  ans+=dis[a[i-1]][a[i]];
	cout<<ans<<endl;
	return 0;
}

Dijkstra算法——最常用的最短路算法

Dijkstra是解决单源最短路的一种算法，是我们在做题的时候最常用的一种算法。

从起点到一个点的最短路径一定会经过至少一个“中转点”（例如下图1到5的最短路径，中转点是2。特殊地，我们认为起点1也是一个“中转点”）。显而易见，如果我们想求出起点到一个点的最短路径，那我们必然要先求出中转点的最短路径（例如我们必须先求出点2 的最短路径后，才能求出从起点到5的最短路径）。换句话说，如果起点1到某一点V0的最短路径要经过中转点Vi，那么中转点Vi一定是先于V0被确定了最短路径的点。

我们把点分为两类，一类是已确定最短路径的点，称为“白点”，另一类是未确定最短路径的点，称为“蓝点”。如果我们要求出一个点的最短路径，就是把这个点由蓝点变为白点。从起点到蓝点的最短路径上的中转点在这个时刻只能是白点。
Dijkstra的算法思想，就是一开始将起点到起点的距离标记为0，而后进行n次循环，每次找出一个到起点距离dis[u]最短的点u，将它从蓝点变为白点。随后枚举所有的蓝点vi，如果以此白点为中转到达蓝点vi的路径dis[u]+w[u][vi]更短的话，这将它作为vi的“更短路径”dis[vi]（此时还不确定是不是vi的最短路径）。
就这样，我们每找到一个白点，就尝试着用它修改其他所有的蓝点。中转点先于终点变成白点，故每一个终点一定能够被它的最后一个中转点所修改，而求得最短路径。
算法开始时，作为起点的dis[1] = 0，其他的点dis[i] = 0x7fffffff。

这时dis[2]，dis[3]，dis[4]被它的最后一个中转点1修改为了最短路径。

这时dis[3]，dis[5]被它们的最后一个中转点2修改为了最短路径。

接下来的两轮循环将4、5也变成白点。N轮循环结束后，所有的点的最短路径即能求出。