参考资料：
《算法竞赛进阶指南》
《算法竞赛从入门到进阶》
浙江大学《数据结构（第二版）》
例题：
前置知识：使用邻接矩阵，邻接表存储和访问图（特别是有权图）。
简略复习一下，邻接表可以链表，数组，STL中的vector来实现。用数组的方法又称链式前向星存图。我们使用一个表头数组head记录了从每个节点出发的第一条边在ver和edge数组中的存储位置，使用边集数组ver和edge记录了每条边的终点和边权，使用数组Next模拟了链表中的指针，表示从相同起点出发的下一条边在ver和edge数组中的存储位置。核心代码如下：
//加入有向边(x, y), 权值为z
void add(int x, int y, int z) {
ver[++tot] = y, edge[tot] = z;
Next[tot] = head[x], head[x] = tot;
}
//访问从x出发的所有边
for (int i = head[x]; i != -1; i = next[i]) {
int y = ver[i], z = edge[i];
//找到了一条有向边(x, y), 权值为z
}
单源最短路径问题是说，给定一张有向图（无向图可以视为特殊的有向图）G = (V, E), V是点集, E是边集, |V| = n, |E| = m。给定一个起点s，求长度为n的数组dist，其中dist[i]表示从起点s到节点i的最短路径长度。
数据结构和算法动态可视化
Dijkstra算法只适用于所有边的长度（权值）都是非负数的图，用于求解单源最短路径问题。
#include <bits/stdc++.h>
using namespace std;
const int N = 105, M = 20010;
int tot, ver[M], Next[M], head[N], edge[M];
int dist[N];
bool vis[N];
void addedge(int x, int y, int z) {
ver[++tot] = y, edge[tot] = z;
Next[tot] = head[x], head[x] = tot;
}
void dijkstra(int s, int n) {
memset(dist, 0x3f, sizeof(dist));
memset(vis, false, sizeof(vis));
dist[s] = 0;
int x = 0;
for (int i = 0; i < n; i++) {
x = 0;
for (int j = 1; j <= n; j++) {
if (!vis[j] && (x == 0 || dist[j] < dist[x])) x = j;
}
vis[x] = true;
for (int j = head[x]; j; j = Next[j]) {
int y = ver[j], z = edge[j];
if (dist[y] > dist[x] + z) dist[y] = dist[x] + z;
}
}
}
int main() {
int n, m, s, x, y, z;
while (~scanf("%d %d %d", &n, &m, &s)) {
memset(head, -1, sizeof(head));
tot = -1;
for (int i = 0; i < m; i++) {
scanf("%d %d %d", &x, &y, &z);
addedge(x, y, z);
}
dijkstra(s, n);
for (int i = 1; i <= n; i++) {
printf("%d%c", dist[i], i == n ? ‘\n‘ : ‘ ‘);
}
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
const int N = 105;
const int M = 2e4 + 10;
struct node {
int x, y, z;
} e[M];
int dist[N];
void Bellman(int s, int n, int m) {
memset(dist, 0x3f, sizeof(dist));
dist[s] = 0;
for (int i = 1; i < n; i++) {
for (int j = 0; j < m; j++) {
int x = e[j].x, y = e[j].y, z = e[j].z;
if (dist[y] > dist[x] + z) dist[y] = dist[x] + z;
}
}
}
int main() {
int n, m, s, x, y, z, cnt;
while (~scanf("%d %d %d", &n, &m, &s)) {
cnt = 0;
for (int i = 0; i < m; i++) {
scanf("%d %d %d", &x, &y, &z);
e[cnt++] = {x, y, z};
}
Bellman(s, n, cnt);
for (int i = 1; i <= n; i++) {
printf("%d%c", dist[i], i == n ? ‘\n‘ : ‘ ‘);
}
}
return 0;
}
SPFA算法通称为“队列优化的 Bellman-Ford算法”，只在中国大陆流行“SPFA算法”的称谓。
代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 105;
const int M = 2e4 + 10;
int head[N], ver[M], edge[M], Next[M], tot;
int dist[N];
bool vis[N];
void addedge(int x, int y, int z) {
ver[++tot] = y, edge[tot] = z;
Next[tot] = head[x], head[x] = tot;
}
void spfa(int s) {
memset(dist, 0x3f, sizeof(dist));
memset(vis, false, sizeof(vis));
dist[s] = 0, vis[s] = true;
queue<int> Q;
Q.push(s);
while (!Q.empty()) {
int x = Q.front();
Q.pop();
vis[x] = false;
for (int i = head[x]; i; i = Next[i]) {
int y = ver[i], z = edge[i];
if (dist[y] > dist[x] + z) {
dist[y] = dist[x] + z;
if (!vis[y]) Q.push(y), vis[y] = true;
}
}
}
}
int main() {
int n, m, s, x, y, z;
while (~scanf("%d %d %d", &n, &m, &s)) {
memset(head, 0, sizeof(head)), tot = 0;
for (int i = 0; i < m; i++) {
scanf("%d %d %d", &x, &y, &z);
addedge(x, y, z);
}
spfa(s);
for (int i = 1; i <= n; i++) {
printf("%d%c", dist[i], i == n ? ‘\n‘ : ‘ ‘);
}
}
return 0;
}
为了求出图中任意两点间的最短路径，当然可以把每一个点当做起点求解N次单源最短路径问题。不过对于该类问题，使用Floyd算法可以用非常简单的程序解决。
设D[k, i, j] 表示 “经过若干个编号不超过 k 的结点” 从 i 到 j 的最短路长度。该问题可以划分为两个子问题，经过编号不超过 k - 1 的节点从 i 到 j，或者从 i 先到 k 再到 j。于是：
D[k, i, j] = min(D[k - 1, i, j], D[k - 1, i, k] + D[k - 1, k, j]);
初值为 D[0, i, j] = A[i, j]，其中A为邻接矩阵。可以发现，Floyd算法的本质是动态规划。其中k是阶段，我们可以通过D[0, i, j]求出D[1, i, j]，再由D[1, i, j]求出D[2, i, j]，直至求出D[n, i, j]，算法结束。
#include <bits/stdc++.h>
using namespace std;
const int N = 105;
const int INF = 0x3f3f3f3f;
int dist[N][N];
void Floyd(int n) {
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
if (dist[i][k] != INF)
for (int j = 1; j <= n; j++)
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
int main() {
int n, m, x, y, z;
while (~scanf("%d %d", &n, &m)) {
memset(dist, 0x3f, sizeof(dist));
for (int i = 0; i <= n; i++) dist[i][i] = 0;
for (int i = 0; i < m; i++) {
scanf("%d %d %d", &x, &y, &z);
dist[x][y] = min(dist[x][y], z);
}
Floyd(n);
for(int i=1; i<=n; i++) {
for(int j=1; j<=n; j++) {
printf("%d%c", dist[i][j], j==n?‘\n‘:‘ ‘);
}
}
}
return 0;
}
原文：https://www.cnblogs.com/sdutzxr/p/12986721.html