最短路径问题是图论中常见的问题，因为求最短路径常常采用的是一种贪心或者动态规划的思想，当然也会有其他的。其代表性的算法有迪杰斯特拉算法、弗洛伊德算法和SPFA算法。它们适用于不同的情况比如普通的有权有向图、有权有环图、还有负权有环图等等。问题很大概率上不是符合模板的题目，但是了解这些算法可以让解决问题的过程中多一种思路和方法。
表示图
做图论题怎么能够不知道怎么表示图呢？图中有点、边和权三大要素，表示可以采用邻接矩阵法和邻接表法。
邻接矩阵法
邻接矩阵法在离散数学中就已经讲到了，采用一个矩阵让一个维度的角标代表边的起始点，让另一个维度的角标来代表边的终点，最后将矩阵中对应的位记边的长度。
int graph[10010][10010];
// Provide a two-dimensional array of graph storage.
for (int i = 1; i <= m; i++) {
int u, v, w;
cin >> u >> v >> w;
graph[u][v] = w;
}
邻接表法
邻接矩阵简单直观，但是不管有多少条边都铁定要占掉 $n^{2}$ 的内存空间，这对于较为稀疏的图来说太浪费空间了。如果只记录已经存在的边的数据就能让内存空间大大节省。
// definition of the edge
struct edge {
int v;
int w;
};
// use vector to store graph
vector<edge> graph[10010];
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int u, v, w;
cin >> u >> v >> w;
graph[u].push_back((edge{v, w}));
}
算法解释
了解了图的表示方法就要开始着手解决最短路径的算法问题了，通用的思路是不断地尝试路径，用更短的路径更新答案，知道这个就能够理解下面的算法了。
迪杰斯特拉算法
这个Dijkstra算法能够运算单源最短路也就是将图上一点为起点时到达所有点的最短路径都算出来，但不能够处理负权图。模板题https://www.luogu.com.cn/problem/P4779非常典型，采用优先队列优化过的时间复杂度是 $O(v \log v)$ ，已经是很快的一种解决办法了。通常是把图中的图分成两部分，一部分为已经找到最短路径的点的集合S和没有确定最短路径的点的集合U。每次在U中寻找当前路径最短的点加入到S中，因为它已经是已知最优解了，即如果从其他点间接的到达它时路径已经不是最短了。反复如此操作，当所有点都已经确定则单源最短路查找完毕。
- 贪心
顾名思义就是选择眼前最好的那个而不顾及之后的好坏。这对于人来说不能称得上一种好心态，但是对于问题来说每次选择局部最优解就可能达到全局最优解。
int dis[10010];
bool vis[10010];
struct edge {
int num;
int cost;
bool operator<(const edge& other) const { return cost > other.cost; }
};
vector<edge> graph[10010];
void Dijkstra(int start) {
// initialize shortest path to infinite length
for (int i = 1; i <= n; i++) {
dis[i] = INT_MAX;
}
dis[start] = 0;
priority_queue<edge> que;
que.push((edge){start, dis[start]});
// Update the distance to starting point and add it to the queue. And keep
// traversing the nodes in the queue until all traversal is completed.
while (!que.empty()) {
edge t = que.top();
que.pop();
if (vis[t.num]) continue; // skip points visited
vis[t.num] = 1;
for (int i = 0; i < graph[t.num].size(); i++) {
edge e = graph[t.num][i];
// Traverse the points connected to the point in the graph whether there
// is a shorter path and update the answer.
if (dis[e.num] > dis[t.num] + e.cost) {
dis[e.num] = dis[t.num] + e.cost;
// add points of shorter path
que.push((edge){e.num, dis[e.num]});
}
}
}
}
到这里可能会对更新最短路径的过程有一些疑惑，https://www.luogu.com.cn/problem/P1144这道题将一些操作和更新最短路径操作结合就能够加深印象。还有更加毒瘤的最短路径积的https://www.luogu.com.cn/problem/P2384要巧妙的运用下面的这个公式。
\[\log xy=\log x+\log y\]还有一些图论问题不能够在原图结构上解决，需要去构建虚点虚边来构造新图满足题目的要求，有一道迪杰斯特拉变形题https://codeforces.com/contest/1486/problem/E是这样的。
弗洛伊德算法
Floyd算法是解决图中任意两点间的最短路径的一种算法，它可以解决图中点之间有向图和甚至没有负权回路的负权图的最短路径问题，但是时间复杂度是 $O(v^{3})$ ，不适合解决数据量较大的问题。算法中将问题简化为直接到达和间接到达两种情况，遍历所有的点查看是否存在点使得dis(i,k) + dis(k,j) < dis(i,j)即从i点出发是间接经过k点到j还是直接到达更优。
int dis[10010][10010];
void Init() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j) {
dis[i][j] = 0;
} else {
dis[i][j] = INF;
}
}
}
}
void Floyd() {
for (int k = 0; k < n; k++) {
// If path with k as the mid point is shorter than current path, update.
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
}
}
}
}
因为需要中间点去不断DP更新最短路径，所以很多时候有时候可以将取中间点的操作分开。比如这道题https://www.luogu.com.cn/problem/P1119中将图中的点一个一个加入就可以利用这些点作为中间点去DP更新答案。弗洛伊德算法的思想非常简单但是时间复杂度高，需要结合实际情况使用。
SPFA 算法
这是一种时间复杂度不太稳定的算法，种种原因会造成它最终的时间复杂度退化为 $O(ve)$ 的情况，但是它可以解决负权图图（没有负环）的最短路径的问题。通常采用的是Dijkstra算法来做最短路径，特殊情况用这种算法来解决。
- 广度优先搜索
这种算是采用了BFS的方法去更新最短路径，遍历队首邻接的所有路径，并将原本不在队列中的更短路径点加入队列中。不断找出更短的路径，再从最短路径点进一步松弛最短路径。
struct edge {
int num;
int cost;
};
vector<edge> graph[10010];
int dis[10010];
int vis[10010];
void SPFA(int start) {
for (int i = 1; i <= n; i++) {
dis[i] = INT_MAX;
vis[i] = false;
}
dis[start] = 0;
vis[start] = true;
// add start point to queue
queue<edge> que;
que.push((edge){start, dis[start]});
while (!que.empty()) {
edge t = que.front();
que.pop();
vis[t.num] = false;
for (int i = 0; i < graph[t.num].size(); i++) {
edge e = graph[t.num][i];
// Traverse the neighboring points and update the path length.
if (dis[t.num] + e.cost < dis[e.num]) {
dis[e.num] = dis[t.num] + e.cost;
if (vis[e.num] == false) {
// Let the points with shorter paths join the queue.
que.push(e);
vis[e.num] = true;
}
}
}
}
}
最短路径总结
了解了上面几种最短路径的算法之后可以发现它们都用了三角比较公式来利用中间点缩短路径，尽管它们的方式各不相同但是核心思想却是相同的。Dijkstra算法采用的是优先队列找到最近的点来继续更新路径，而Floyd则是直接暴力遍历用动态规划尝试所有中间点来解决，SPFA算法采用了广度优先搜索的思想去缩短最短路径。
| 名称 | 适用情况 | 复杂度 |
|---|---|---|
| Dijkstra | 正权图 | $O(v \log v)$ |
| Floyd | 无负环图 | $O(v^{3})$ |
| SPFA | 无负环图 | $O(ve)$ |