[C++知识库]Dijkstra求单源最短路径C++代码模板

在写出具体函数之前，需要先定义MAXV为最大顶点数、INF为一个很大的数字：

const int MAXV = 1000;//最大顶点数
const int INF = 1000000000;//设INF是一个很大的数

邻接矩阵版

int n, G[MAXV][MAXV];//n为顶点数，MAXV为最大顶点数
int d[MAXV];//起点到达各点的最短路径长度
bool vis[MAXV] = { false };//标记数组，vis[i]=true表示已访问。初值均为false

void Dijkstra(int s) {//s为起点
	fill(d, d + MAXV, INF);//fill函数将整个数组d赋为INF
	d[s] = 0;//起点s到达自身的距离为0
	for (int i = 0; i < n; i++) {//循环n次
		int u = -1, MIN = INF;//u使d[u]最小，MIN存放该最小的d[u]
		for (int j = 0; j < n; j++) {//找到未访问的顶点中d[]最小的
			if (vis[j] == false && d[j] < MIN) {
				MIN = d[j];
				u = j;
			}
		}
		//找不到小于INF的d[u]，说明剩下的顶点和起点s不连通
		if (u == -1) return;
		vis[u] = true;//标记u已访问
		for (int v = 0; v < n; v++) {
			//如果v未访问&&u能到达v&&以u为中介点可以使d[v]更优
			if (vis[v] == false && G[u][v] != INF && d[u] + G[u][v] < d[v]) {
				d[v] = d[u] + G[u][v];//优化d[v]
			}
		}
	}
}

从复杂度来看，主要是外层循环$O(V)$（V就是顶点个数n）与内层循环（寻找最小的d[u]需要$O(V)$、枚举v需要$O(V)$产生的，总复杂度为$O(V?(V+V))=O(V^2)$。

邻接表版

struct Node
{
	int v, dis;//v为边的目标顶点，dis为边权
};

vector<Node> Adj[MAXV];//图G，Adj[u]存放从顶点u出发可以到达的所有顶点，MAXV为最大顶点数
int n;//n为顶点数
int d[MAXV];//起点到达各点的最短路径长度
bool vis[MAXV] = { false };//标记数组，vis[i]=true表示已访问。初值均为false

void Dijkstra(int s) {//s为起点
	fill(d, d + MAXV, INF);//fill函数将整个数组d赋为INF
	d[s] = 0;//起点s到达自身的距离为0
	for (int i = 0; i < n; i++) {//循环n次
		int u = -1, MIN = INF;//u使d[u]最小，MIN存放该最小的d[u]
		for (int j = 0; j < n; j++) {//找到未访问的顶点中d[]最小的
			if (vis[j] == false && d[j] < MIN) {
				MIN = d[j];
				u = j;
			}
		}
		//找不到小于INF的d[u]，说明剩下的顶点和起点s不连通
		if (u == -1) return;
		vis[u] = true;//标记u已访问
		//只有下面这个for与邻接矩阵的写法不同
		for (int j = 0; j < Adj[u].size(); j++) {
			int v = Adj[u][j].v;//通过邻接表直接获得u能到达的顶点v
			//如果v未访问&&以u为中介点可以使d[v]更优
			if (vis[v] == false && d[u] + Adj[u][v].dis < d[v]) {
				d[v] = d[u] + Adj[u][v].dis;//优化d[v]
			}
		}
	}
}

从复杂度来看，主要是外层循环$O(V)$与内层循环（寻找最小的d[u]需要$O(V)$、枚举v需要$O(Adj[u].size)$产生的。又由于对整个程序来说，枚举v的次数总共为$O(E)$，因此总复杂度为$O(V^2+E)$。