最短路算法（Dijkstra + SPFA + Floyd）
Dijkstra算法
1.算法基本介绍
Dijkstra算法通常是求解单源最短路中最快的算法，但它无法处理存在负权边的情况（原因在正确性证明中）。Dijkstra本质上是一种贪心算法，通过不断调整每个点的“当前距离”最终得到最优结果，其实后面要讲到的几种算法也大都是采用这种步步逼近的手段。这种不断调整的过程，维基百科上面称为“relax"。以上可能有点抽象，下面是算法的流程。
原题链接：Dijkstra Algorithm - Problems - Eolymp
例题1：
The directed weighted graph is given. Find the shortest path from the vertex s to the vertex f.
Input data
The first line contains three numbers n, s and f (1 ≤ n ≤ 100, 1 ≤ s, f ≤ n), where n is the number of vertices in a graph. Each of the next n lines contains n numbers - the adjacency matrix of the graph, where the number in the i-th line and j-th column corresponds to the edge from i to j: -1 means the absence of the edge between the vertices, and any non-negative number - the presence of the edge of a given weight. The main diagonal of the matrix contains always zeroes.
Output data
Print the required distance or -1 if the path between the given vertices does not exist.
Examples
Input example #1
3 1 2
0 -1 2
3 0 -1
-1 4 0
Output example #1
6
Vector版本：
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
int main()
{
int n, s, f;
cin >> n >> s >> f;
vector<vector<int>> graph(n, vector<int>(n));//定义了一个n行n列的graph向量
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
cin >> graph[i][j];//输入邻接矩阵的权
}
}
/*
dist 向量表示起点 s 到每个节点的最短距离，初始化为无穷大。
visited 向量用于标记每个节点是否被访问过，初始化为 false。
*/
vector<int> dist(n, INF);//初始化dis
vector<bool> visited(n, false);//初始化visited
dist[s-1] = 0; //s到自身的距离为0
for (int i = 0; i < n; i++)
{
int u = -1;//给出一个非法值，判断判断是否已经找到了离起点最近的未访问节点。
//如果 u 的值不是 -1，说明找到了离起点最近的未访问节点.
for (int j = 0; j < n; j++)
{
if (!visited[j] && (u == -1 || dist[j] < dist[u])) //判断当前节点 j 是否为起点 s 的第一个访问节点
{
u = j;
}
}
if (dist[u] == INF)
{
break;//如果 u 的值仍然为 -1，说明没有找到符合条件的未访问节点，此时就需要结束 Dijkstra 算法的迭代
}
visited[u] = true;
for (int v = 0; v < n; v++)
{
if (graph[u][v] != -1)//-1的时候是两点间并未相连 即没有路径可走
{
int alt = dist[u] + graph[u][v];
if (alt < dist[v])
{
dist[v] = alt;
}
}
}
}
if (dist[f-1] == INF)
{
cout << -1 << endl;
}
else
{
cout << dist[f-1] << endl;
}
/*
最后，检查 dist[f-1] 的值，如果为无穷大，则说明起点 s
无法到达终点 f，输出 -1。否则，输出起点 s
*/
return 0;
}
/*
输入：
3 1 2
0 -1 2
3 0 -1
-1 4 0
输出：
6
*/
例题二：
Background
\(\mathrm{A}\) 地区在地震过后，连接所有村庄的公路都造成了损坏而无法通车。政府派人修复这些公路。
Description
给出 \(\mathrm{A}\) 地区的村庄数 \(N\) ，和公路数 \(M\) ，公路是双向的。并告诉你每条公路的连着哪两个村庄，并告诉你什么时候能修完这条公路。问最早什么时候任意两个村庄能够通车，即最早什么时候任意两条村庄都存在至少一条修复完成的道路 (可以由多条公路连成一条道路)。
Input
第 1 行两个正整数 \(N, M\) 。
下面 \(M\) 行，每行 3 个正整数 \(x, y, t\) ，告诉你这条公路连着 \(x, y\) 两个村庄，在时间诗能修复完成这条公路。
Output
如果全部公路修复完毕仍然存在两个村庄无法通车，则输出 -1 ，否则输出最早什么时候任意两个村庄能够通车。
样例输入：
4 4
1 2 6
1 3 4
1 4 5
4 2 3
样例输出
5
朴素版本：
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1010;
const int INF=0x3f3f3f3f;
int graph[N][N];//邻接矩阵
int dis[N];//起点到目标点的距离
int v[N];//判断这个点是否走过
int n,m;
int u,p,w;
void dijkstra()
{
memset(dis,INF,sizeof(dis)); //将起点到各个点的距离初始化为INF
dis[1]=0; //起点到自己的距离为0
for(int i=1;i<=n;i++) //共进行n轮
{
int t=-1; //t为距离起点最近的未访问的点
for(int j=1;j<=n;j++)
{
if(v[j]==0&&(t==-1||dis[t]>dis[j])) //如果j未被访问过且到j的距离更近
{
t=j; //更新t为j
}
}
v[t]=1; //标记t为已访问过
for(int j=1;j<=n;j++)
{
dis[j]=min(dis[j],dis[t]+graph[t][j]); //用t更新起点到j的距离
}
}
cout<<dis[n]<<endl; //输出起点到终点的最短距离
}
int main()
{
cin>>m>>n; //输入边的数量m和点的数量n
memset(graph,INF,sizeof(graph)); //将邻接矩阵初始化为INF
for(int i=1;i<=m;i++) //输入m条边
{
cin>>u>>p>>w;
graph[u][p]=graph[p][u]=min(graph[u][p],w); //将u和p之间的边权设置为w
}
dijkstra(); //运行Dijkstra算法
return 0;
}
例题三：
原题链接：[2387 -- Til the Cows Come Home (poj.org)]
史学长很热爱学习，他打算假期偷偷跑回学校学习，为了多学习他希望可以找最快的路线回到学校。 洛阳市里有N个(2 <= N <= 1000)个地铁站，编号分别为1..N。他的家在1号地铁站旁边，洛阳师范学院站是N号地铁站。地铁站之间共有M (1 <= M <= 2000)条双向路径。 史学长现在在1号地铁站，他希望知道到学校最短要多长时间。可以保证史学长能到达学校。忽略史学长在换乘地铁时需要的等待时间。
Input
* 第一行输入两个整数m和n
* 接下来m行，每行三个整数a、b、c，表示a号地铁站和b号地铁站间要花费时间c（1<=c<=100）.
Sample
Input
5 5
1 2 20
2 3 30
3 4 20
4 5 20
1 5 100
Output
90
代码：
/*
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
*/
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=2010;
const int INF=0x3f3f3f3f;
int v[N],graph[N][N];
int dis[N];
int n,m,a,b,c;
void dijkstra()
{
memset(dis,INF,sizeof(dis));
dis[1]=0;
for(int i=1;i<=n;i++)
{
int t=-1;
for(int j=1;j<=n;j++)
{
if(v[j]==0&&(t==-1||dis[t]>dis[j]))
{
t=j;
}
}
v[t]=1;
for(int j=1;j<=n;j++)
{
if(graph[t][j]!=INF)
dis[j]=min(dis[j],dis[t]+graph[t][j]);
}
}
cout<<dis[n]<<endl;
}
int main()
{
memset(graph,INF,sizeof(graph));
cin>>m>>n;
for(int i=1;i<=m;i++)
{
cin>>a>>b>>c;
graph[a][b]=graph[b][a]=min(graph[a][b],c);
}
dijkstra();
return 0;
}