最短路径
朴素$Dijkstra$算法，时间复杂是$O(n^2+m)$，$n$表示点数，$m$表示边数：
//dijkstra 算法
int g[N][N]; // 存储每条边
int dist[N]; // 存储 1 号点到每个点的最短距离
int st[N]; // 存储每个点的最短路是否已经确定
// 求 1 号点到 n 号点的最短路，如果不存在则返回-1
int dijkstra(){
memset(dist, 0x3f, sizeof(dist));
memset(st, 0, sizeof(st));
dist[1] = 0;
for(int i = 0; i < n - 1; i ++ ){
int t = -1; // 在还未确定最短路的点中，寻找距离最小的点
for(int j = 1; j <= n; j++ ){
if (!st[j] && (t == -1 || dist[t] > dist[j])){
t = j;
}
}
// 用 t 更新其他点的距离
for(int j = 1; j <= n; j ++ ){
dist[j] = min(dist[j], dist[t] + g[t][j]);
}
st[t] = 1;
}
if(dist[n] == 0x3f3f3f3f){
return -1;
}
return dist[n];
}
堆优化版$Dijkstra$算法，时间复杂度$O(mlogn)$，$n$表示点数，$m$表示边数：
//堆优化 dijkstra
typedef pair<int, int> PII;
int n; // 点的数量
int h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边
int dist[N]; // 存储所有点到 1 号点的距离
int st[N]; // 存储每个点的最短路是否已经确定
// 求 1 号点到 n 号点的最短距离，如果不存在，则返回-1
int dijkstra(){
memset(dist, 0x3f, sizeof dist);
memset(st, 0, sizeof(st));
dist[1] = 0;
priority_queue<PII, vector<PII>, greater<PII>> heap;
heap.push({0, 1}); // first 存储距离，second 存储节点编号
while(heap.size()){
auto t = heap.top();
heap.pop();
int ver = t.second, distance = t.first;
if(st[ver]){
continue;
}
st[ver] = 1;
for(int i = h[ver]; i != -1; i = ne[i]){
int j = e[i];
if(dist[j] > distance + w[i]){
dist[j] = distance + w[i];
heap.push({dist[j], j});
}
}
}
if(dist[n] == 0x3f3f3f3f){
return -1;
}
return dist[n];
}
算法思想是不断进行松弛操作，其中第$k$轮的$dist[i]$意为起点到点$i$不超过$k$条边的最短路径，可以据此证明是否存在负回路。时间复杂度$O(nm)$，$n$表示点数，$m$表示边数：
//Bellman-Ford
int n, m; // n 表示点数，m 表示边数
int dist[N]; // dist[x]存储 1 到 x 的最短路距离
struct Edge{ // 边，a 表示出点，b 表示入点，w 表示边的权重
int a, b, w;
}edges[M];
// 求 1 到 n 的最短路距离，如果无法从 1 走到 n，则返回-1。
int bellman_ford(){
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
// 如果第 n 次迭代仍然会松弛三角不等式，就说明存在一条长度是 n+1 的最短路径
//由抽屉原理，路径中至少存在两个相同的点，说明图中存在负权回路。
for(int i = 0; i < n; i ++ ){
for(int j = 0; j < m; j ++ ){
int a = edges[j].a, b = edges[j].b, w = edges[j].w;
if (dist[b] > dist[a] + w){
dist[b] = dist[a] + w;
}
}
}
//由于负权边存在故可能导致溢出
if(dist[n] > 0x3f3f3f3f / 2){
return -1;
}
return dist[n];
}
本质上是对$Bellman$-$Ford$算法的改进，主要改进在下一轮调整的边的前驱一定是上一轮被调整过的，否则不需要进行调整。时间复杂度平均情况下$O(m)$，最坏情况下 O(nm)$，$n$表示点数，$m$表示边数：
//SPFA
int n; // 总点数
int h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边
int dist[N]; // 存储每个点到 1 号点的最短距离
int st[N]; // 存储每个点是否在队列中
// 求 1 号点到 n 号点的最短路距离，如果从 1 号点无法走到 n 号点则返回-1
int spfa(){
memset(dist, 0x3f, sizeof dist);
memset(st, 0, sizeof(st));
dist[1] = 0;
queue<int> q;
q.push(1);
st[1] = 1;
while(q.size()){
auto t = q.front();
q.pop();
st[t] = 0;
for(int i = h[t]; i != -1; i = ne[i]){
int j = e[i];
if(dist[j] > dist[t] + w[i]){
dist[j] = dist[t] + w[i];
if(!st[j]){ // 如果队列中已存在 j，则不需要将 j 重复插入
q.push(j);
st[j] = 1;
}
}
}
}
if(dist[n] == 0x3f3f3f3f){
return -1;
}
return dist[n];
}
$SPFA$判断负环的思路，$dist[]$记录最短边长度、$cont[]$记录最短边边数；其中$cont[x]=cont[t]+1$，在某次更新$cont[x]$时$cont[x]=n$则说明负环存在。
时间复杂度$O(n^3)$，$n$表示点数：
//Floyd
void floyd(){
for(int k = 1; k <= n; k++ ){
for(int i = 1; i <= n; i++ ){
for(int j = 1; j <= n; j++ ){
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
}
}
}
关键路径
以顶点表示事件、以有向边表示活动、以边上的权值表示完成该活动的开销的带权有向图，称之为用边表示活动的网络，即 AOE 网。
$AOE$网和$AOV$网都是有向无环图，不同之处：
（1）$AOE$网使用边表示活动；$AOV$网使用顶点表示活动；
（2）$AOE$网中的边有权值；$AOV$网中的边无权值，仅表示顶点之间的前后关系。
$AOE$网具有以下两个性质：
（1）只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始；
（2）只有在进入某顶点的各有向边所代表的活动都已结束时，该顶点所代表的事件才能发生。
在$AOE$网中仅有一个入度为 0 的顶点，称为开始顶点或源点，该顶点表示整个工程的开始；在$AOE$网中也仅有一个出度为 0 的顶点，称为结束顶点或汇点，该顶点表示整个工程的结束。
在$AOE$网中，有些活动是可以并行进行的。从源点到汇点的有向路径可能有多条，并且这些路径长度可能不同。完成不同路径上的活动所需的时间虽然不同，但是只有所有路径上的活动都已完成，整个工程才能算结束。
从源点到汇点的所有路径中，具有最大路径长度的路径称为关键路径，而把关键路径上的活动称为关键活动。完成整个工程的最短时间就是关键路径的长度，即关键路径上各活动花费开销的总和。这是因为关键活动影响了整个工程的时间，即若关键活动不能按时完成，则整个工程的完成时间就会延长。因此，只要找到了关键活动，就找到了关键路径，也就可以得出最短完成时间。以下是在寻找关键活动时所用到的 5 个量：
（1）事件$v_k$的最早发生时间$ve(k)$：它是指从源点$v_1$到顶点$v_k$的最长路径长度。事件$v_k$的最早发生时间决定了所有从$v_k$开始的活动能够开工的最早时间。
（2）事件$v_k$的最迟发生时间$vl(k)$：它是指在不推迟整个工程完成的前提下，即保证它的后继事件$v_j$在其最迟发生时间$vl(j)$能够发生时，该事件最迟必须发生的时间。
（3）活动$a_i$的最早开始时间$e(i)$：它是指该活动弧的起点所表示的事件的最早发生时间。
（4）活动$a_i$的最迟开始时间$l(i)$：它是指该活动弧的终点所表示事件的最迟发生时间与该活动所需时间之差。
（5）一个活动$a_i$的最迟开始时间$l(i)$和其最早开始时间$e(i)$的差额$d(i)=l(i)-e(i)$：它是指该活动完成的时间余量，即在不增加完成整个工程所需总时间的情况下，活动$a_i$可以拖延的时间。若一个活动的时间余量为零，则说明该活动必须要如期完成，否则就会拖延整个工程的进度，所以称$l(i)-e(i)=0$，即$l(i)=e(i)$的活动$a_i$是关键活动。
对于关键路径，需要注意以下 2 点：
1）关键路径上的所有活动都是关键活动，它是决定整个工程的关键因素，因此可通过加快关键活动来缩短整个工程的工期。但也不能任意缩短关键活动，因为一旦缩短到一定的程度，该关键活动就可能会变成非关键活动。
2）网中的关键路径并不唯一，且对于有多条关键路径的网，只提高一条关键路径上的关键活动速度并不能缩短整个工程的工期，只有加快那些包括在所有关键路径上的关键活动才能达到缩短工期的目的。
