定义：
简称Floyed(弗洛伊德)算法，是最简单的最短路径算法，可以计算图中任意两点间的最短路径。Floyed的时间复杂度是O (N3)，适用于出现负边权的情况。
算法描述：
ps：以下没有特别说明的话：dis[u][v] 表示从 u 到 v 最短路径长度。w[u][v] 表示连接 u，v 的边的长度。
?初始化：点u、v如果有边相连，则dis[u][v]=w[u][v]。
?如果不相连则dis[u][v]=0x7fffffff
For (k = 1; k <= n; k++)
For (i = 1; i <= n; i++)
For (j = 1; j <= n; j++)
If (dis[i][j] >dis[i][k] + dis[k][j])
dis[i][j] = dis[i][k] + dis[k][j];
?
算法&思想：
?三层循环，第一层循环中间点k，第二第三层循环起点终点i、j，算法的思想很容易理解：如果点i到点k的距离加上点k到点j的距离小于原先点i到点j的距离，那么就用这个更短的路径长度来更新原先点i到点j的距离。
? 在上图中，因为dis[1][3]+dis[3][2]<dis[1][2]，所以就用dis[1][3]+dis[3][2]来更新原先1到2的距离。
? 我们在初始化时，把不相连的点之间的距离设为一个很大的数，不妨可以看作这两点相隔很远很远，如果两者之间有最短路径的话，就会更新成最短路径的长度。Floyed算法的时间复杂度是O(N3)。
定义：
用来计算从一个点到其他所有点的最短路径的算法，是一种单源最短路径算法。也就是说，只能计算起点只有一个的情况。
思路：
算法分析&思想讲解：
从起点到一个点的最短路径一定会经过至少一个“中转点”（例如下图1到5的最短路径，中转点是2，特殊地，我们认为起点1也是一个“中转点”）。
显而易见，如果我们想求出起点到一个点的最短路径，那我们必然要先求出中转点的最短路径（例如我们必须先求出点2 的最短路径后，才能求出从起点到5的最短路径）。
我们把点分为两类，一类是已确定最短路径的点，称为“白点”，另一类是未确定最短路径的点，称为“蓝点”。如果我们要求出一个点的最短路径，就是把这个点由蓝点变为白点。从起点到蓝点的最短路径上的中转点在这个时刻只能是白点。
Dijkstra的算法思想，就是一开始将起点到起点的距离标记为0，而后进行n次循环，每次找出一个到起点距离dis[u]最短的点u，将它从蓝点变为白点。随后枚举所有的蓝点vi，如果以此白点为中转到达蓝点vi的路径dis[u]+w[u][vi]更短的话，这将它作为vi的“更短路径”dis[vi]（此时还不确定是不是vi的最短路径）。
就这样，我们每找到一个白点，就尝试着用它修改其他所有的蓝点。中转点先于终点变成白点，故每一个终点一定能够被它的最后一个中转点所修改，而求得最短路径。
实现
（1）朴素算法
给出代码：
void dij(int st){
for(re int i=1;i<=n;i++) vis[i]=0,dis[i]=INF;
for(re int i=head[st];i;i=e[i].nxt) dis[e[i].v]=e[i].w;
dis[st]=0,now=st;
while(vis[now]==0){
vis[now]=1,minn=INF;
for(re int i=head[now],w,v;i;i=e[i].nxt){
v=e[i].v;
w=e[i].w;
if(!vis[v]&&dis[v]>dis[now]+w){
dis[v]=dis[now]+w;
}
}
for(re int i=1;i<=n;i++){
if(!vis[i]&&dis[i]<minn){
minn=dis[i];
now=i;
}
}
}
}（2）堆优化
我们通过学习朴素Dij算法，明白Dij算法的实现需要从头到尾扫一遍点找出最小的点然后进行松弛。这个扫描操作就是坑害朴素DIJ算法时间复杂度的罪魁祸首。
所以我们使用小根堆，用优先队列来维护这个“最小的点”。从而大大减少Dij算法的时间复杂度。
前置芝士：
1.pair
pair是C++自带的二元组。我们可以把它理解成一个有两个元素的结构体。
更刺激的是，这个二元组有自带的排序方式：以第一关键字为关键字，再以第二关键字为关键字进行排序。
所以，我们用二元组的first位存距离，second位存编号即可。
typedef pair<int,int> pai;
priority_queue<pai,vector<pai>,greater<pai> >q;定义一个按pair排好的小根堆；
2.怎么往pair类型的优先队列里加元素
q.push(make_pair(first,second))//完事实现：
我们需要往优先队列中push最短路长度，但是它一旦入队，就会被优先队列自动维护离开原来的位置，换言之，我们无法再把它与它原来的点对应上，也就是说没有办法形成点的编号到点权的映射。
我们用pair解决这个问题，参考前置芝士。
代码：
void dijkstra(){
for(int i=1;i<=n;i++)
{
dis[i]=INF;
}
dis[s]=0;
q.push(make_pair(0,s));
while(!q.empty())
{
int k=q.top().first;
int u=q.top().second;
q.pop();
if(vis[u]) continue;
vis[u]=1;
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].v;
if(dis[v]>dis[u]+e[i].w)
{
dis[v]=dis[u]+e[i].w;
q.push(make_pair(dis[v],v));
}
}
}
}
原文：https://www.cnblogs.com/BlackDan/p/15184864.html