最短路：（n 表示点数，m 表示边数）

朴素 Dijkstra 算法

算法分析

Dijkstra算法运行演示

Dijkstra 算法运行演示：（找到 a，b 之间的最短路），本算法每次取出未访问节点中距离最小的，用该节点更新其他节点的距离。在演示过程中访问过的节点会被标为红色。

步骤：

1
2
3
4
5
6
7
初始化：
	清除所有点的标号;
	设dist[1] = 0，其他dist[i] = INF;	// INF是一个很大的值，用来替代正无穷
循环n - 1次：
    在所有未标号结点中，选出dist值最小的结点 x;
    给结点x标记;
    对于从x出发的所有边(x,y)，更新dist[y] = min(dist[y], dist[x] + w(x,y))

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int w[N][N];	// 存储每条边
int dist[N];	// 存储1号点到每个点的最短距离，为了方便，从下标1开始记录
bool st[N];	// 存储每个点的最短距离是否已经确定

// 从1号点到n号点的最短距离，如果不存在则返回-1
int dijkstra() {
    memset(dist, 0x3f, sizeof dist);
    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;
        
        st[t] = true;
        
        // 用t更新其他其他点的距离
        for(int j = 1; j <= n; j++)
            dist[j] = min(dist[j], dist[t] + w[t][j]);
    }
    
    if(dist[n] == 0x3f3f3f3f)	return -1;
    return dist[n];
}

堆优化 Dijkstra 算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
typedef pair<int, int> PII;

int n;	// 点的数量
int e[N], ne[N], w[N], h[N], idx;	// 邻接表
int dist[N];	// 最短距离
bool st[N];	// 存储每个点的最短距离是否已经确定

// 求1号点到n号点的最短距离，如果不存在，则返回-1
int dijkstra() {
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    priority_queue<PII, vector<PII>, greator<PII>> heap;
    heap.push({0, 1});	// first存储距离，second存储节点编号
    
    while(heap.size()) {
        auto t = heap.top();
        heap.pop();
        
        int distance = t.first, ver = t.second;
        st[ver] = true;
        
        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];
}

Bellman-Ford 算法

算法分析

为什么 Dijkstra 不能使用在含负权的图中

如图所示：

  • 使用 Dijkstra 算法得出的最短路为 1 -> 2 -> 4 （每次选择离源点最短距离的点更新其他点）

  • 但实际上是 1-> 2 -> 3 -> 4

什么是 bellman - ford 算法

​ Bellman - ford 算法是求含负权图的单源最短路径的一种算法。其原理为连续进行松弛，在每次松弛时把每条边都更新一下，若在 n - 1 次松弛后还能更新，则说明图中有负环，因此无法得出结果，否则就完成。
​ (通俗的来讲就是：假设 1 号点到 n 号点是可达的，每一个点同时向指向的方向出发，更新相邻的点的最短距离，通过循环 n - 1 次操作，若图中不存在负环，则 1 号点一定会到达 n 号点，若图中存在负环，则在 n - 1 次松弛后一定还会更新)

​ bellman - ford 算法擅长解决有边数限制的最短路问题

步骤

1
2
3
循环n次
	循环遍历所有边
		dist[y] = min(dist[y], dist[x] + w)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int n, m;	// n, N：点数，m, M：边数
int dist[N];

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;
            dist[b] = min(dist[b], dist[a] + w);
        }
    }
    
    // 0x3f3f3f3f是一个确定的值，并非真正的无穷大，会随着其他数值而受到影响
    if(dist[n] > 0x3f3f3f3f / 2)	return -1;
    return dist[n];
}

SPFA 算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
int n;	// 点的数量
int e[N], ne[N], w[N], h[N], idx;	// 邻接表
int dist[N];	// 最短距离
bool st[N];	// 存储每个点是否在队列中

// 求1号点到n号点的最短路距离，如果从1号点无法走到n号点则返回-1
int spfa() {
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    
    queue<int> q;
    q.push(1);
    st[1] = true;
    
    while(q.size()) {
        auto t = q.front();
        q.pop();
        
        st[t] = false;
        
        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] = true;
                }
            }
        }
    }
    
    if(dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

Floyd 算法

1
2
3
4
5
6
7
8
9
10
11
12
13
// 初始化
for(int i = 1; i <= n; i++)
    for(int j = 1; j <= n; j++)
        if(i == j) d[i][j] = 0;
		else d[i][j] = INF;

// 算法结束后，d[a][b]表示a到b的最短距离
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]);
}