最短路系列—Dijkstra算法

• 单源最短路，一个定点到另一个顶点的最短路径算法
• 所有边权都是正数
• 适用于稠密图。（边数较多的图 m = n^2 其中， n为顶点，m为边数）
• 稠密图适合邻接矩阵来存储，稀疏图适合用邻接表存储。
• 最短路问题通常只用考虑有向图（无向图可以用有向图来实现）。

• 使用数组dist存储源点到其他点的距离。
• 数组s存储当前已经确定的最短距离的点。
• 初始化，dist[0] = 0，其余dist[i] = INT_MAX (一个较大的值即可)
• 循环处理。
  1. 找到不在s中的距离最近的点t
  2. t加入到s中。
  3. 用t更新其他所有点的距离x。 如果dist[x] > dist[t] + g[t][x],则dist[x] = dist[t] + g[t][x]
  4. 重复以上循环。

849 Dijkstra求最短路 I

• n个点m条边有向图，图中可能存在重边和自环，所有边权为正值。
• 求1号点到n号点的最短距离，无法从1到n，输出-1.

• 第一行 整数n m。
• 接下来m行，每行x, y,z, 表示存在从x到y的边长为z的有向边。

• 输出一个整数，表示从1到n的最短距离。
• 如果路径不存在，输出-1。

1 1 1 ⩽ leqslant ⩽ n ⩽ leqslant ⩽ 500
1 1 1 ⩽ leqslant ⩽ m ⩽ leqslant ⩽ 1 0 5 10^5 105
所涉及边长不超过10000.

3 3
1 2 2
2 3 1
1 3 4

3

#include 
#include 
#include 

using namespace std;

const int N = 510;

int n, m;
int g[N][N];  //存储输入数据，稠密图，用二维矩阵存储
int dist[N];  //存储源点到其他点的最短距离
bool st[N]; //每个点的最短路是否确定

int dijkstra() {
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    
    for (int i = 0; i < n; i ++) { 
    	int t = -1;
    	for (int j = 1; j <= n; j ++) {
    		if (!st[j] && (t == -1 || dist[j] < dist[t])) // 找到不在st中的距离最近的点j
    			t = j;
    	}
    	st[t] = true;  //t加入到st中
    	for (int j = 1; j <= n; j ++)
    		dist[j] = min(dist[j], dist[t] + g[t][j]); //用t更新其他所有点的距离
    }
    if (dist[n] == 0x3f3f3f3f) return -1; // 说明1到n不连通
    
    return dist[n];
}

int main() {
	scanf("%d%d", &n, &m);
    
	memset(g, 0x3f, sizeof g);  //初始化为无穷大
	while (m --) {
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		g[a][b] = min(g[a][b], c);  //去除重边和自环的影响
	}
    
    printf("%dn", dijkstra());
    
    return 0;
}

acwing评测器已提交AC。另外想自己测试验证重边，自环等问题验证一下。
C++在线工具 测试了几组数据，符合预期。

• 自环边
  输入：
  
  输出：
  
• 重边
  输入：
  
  输出：
  

同样还是上述题目，将其数据范围调整，变为稀疏图。朴素版本Dijkstra算法的时间复杂度为O(n^2)，很容易爆掉。

以下考虑如何优化。

• 查找最近距离的过程可以用堆来实现（手写堆或者STL里面优先队列），可以将每次查找的时间复杂度降低到O(1)，n次查找，时间复杂度为O(n)。
• t加入到s中。时间吧复杂度不变O(n)。
• 更新过程。每次更新当前点的所有边。n次更新的边数即为总边数m。时间复杂度为O(m)。堆中每次修改一个数的时间复杂度是O(logn)，总时间复杂度O(mlogn)。
• 整体时间复杂度取最大值O(mlogn)。

850. Dijkstra求最短路 II
上述题目不变，仅修改数据范围。

1 1 1 ⩽ leqslant ⩽n, m ⩽ leqslant ⩽ 1.5 ∗ 1 0 5 1.5 * 10^5 1.5∗105
图中涉及边长均不小于 0 ，且不超过 10000。
数据保证：如果最短路存在，则最短路的长度不超过 109。

#include 
#include 
#include 
#include 

using namespace std;

const int N = 1000010;

int n, m;
int h[N], w[N], e[N], ne[N];  //优化版本是稀疏图 存储方式采用邻接表
int dist[N];  //存储源点到其他点的最短距离
bool st[N]; //每个点的最短路是否确定
int idx;

typedef pair PII;

//邻接表建立过程（带权重）
void add(int a, int b, int c) {
	e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}

int dijkstra() {
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    // 优先队列维护距离
    priority_queue, greater> heap;
    heap.push({0, 1});
    
    while (heap.size()) {
    	auto t = heap.top();
    	heap.pop();
    	int ver = t.second, distance = t.first;
    	if (st[ver]) continue;
    	
    	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; // 说明1到n不连通
    
    return dist[n];
}

int main() {
	scanf("%d%d", &n, &m);
    
	memset(h, -1, sizeof h);
	
	while (m --) {
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		add(a, b, c);
	}
    
    printf("%dn", dijkstra());
    
    return 0;
}

1. 朴素Dijkstra算法
2. 搜索与图论(二)
3. 关于memset函数和赋值0x3f，2021-5-5