【原】最短路径问题Dijkstra算法实现

仅考虑输出最短距离

思路：在所有不在s中的节点里寻找dist值最小的节点u，将u加入s并更新dist表。

const int maxN = 501;    //最大节点数
const int maxDist = 99999;    //最大距离
int c[maxN][maxN];    //邻接矩阵
int dist[maxN];    //距离表
int N;    //实际输入的节点数

//v是出发点
void Dijkstra(int v) {
	bool s[maxN];	//判断是否已存入该点到s集合中
	//初始化dist表和s表
	for (int i = 0; i < N; i++) {
		dist[i] = c[v][i];
		s[i] = false;
	}
	dist[v] = 0;
	s[v] = true;
	
	// 依次将未放入S集合的结点中，取dist[]最小值的结点，放入结合S中
	// 一旦S包含了所有V中顶点，dist就记录了从源点到所有其他顶点之间的最短路径长度
	for (int i = 1; i < N; i++) {
		//找dist表中最小的
		int tmp = maxDist;
		int u = v;
		for (int j = 0; j < N; j++) {
			if (!s[j] && dist[j] < tmp) {
				u = j;
				tmp = dist[j];
			}
		}
		s[u] = true;	//将找到的u放入s集合
		//更新dist
		for (int i = 0; i < N; i++) {
			if (!s[i] && c[u][i] < maxDist) {
				int newDist = dist[u] + c[u][i];
				if (newDist < dist[i]) {
					dist[i] = newDist;
				}
			}
		}
	}
}

若需要找出最短路径

思路：准备一个prev表记录每个节点的前一个节点。在getPath方法中，从终点u开始，不断访问上一个节点，直到访问到出发起点。

const int maxN = 501;    //最大节点数
const int maxDist = 99999;    //最大距离
int c[maxN][maxN];    //邻接矩阵
int dist[maxN];    //距离表
int pre[maxN];    //记录当前点的前一个节点
int N;    //实际输入的节点数


 //v是出发点
void Dijkstra(int v) {
	bool s[maxN];	//判断是否已存入该点到s集合中
	//初始化dist表、s表和prev表
	for (int i = 0; i <= N; i++) {
		dist[i] = c[v][i];
		s[i] = false;
		if (dist[i] == maxDist) {
			pre[i] = -1;
		}
		else {
			pre[i] = v;
		}
	}
	dist[v] = 0;
	s[v] = true;
	
	// 依次将未放入S集合的结点中，取dist[]最小值的结点，放入结合S中
	// 一旦S包含了所有V中顶点，dist就记录了从源点到所有其他顶点之间的最短路径长度
	for (int i = 1; i <= N; i++) {
		//找dist表中最小的
		int tmp = maxDist;
		int u = v;
		for (int j = 0; j <= N; j++) {
			if (!s[j] && dist[j] < tmp) {
				u = j;
				tmp = dist[j];
			}
		}
		s[u] = true;	//将找到的u放入s集合
		//更新dist
		for (int i = 0; i <= N; i++) {
			if (!s[i] && c[u][i] < maxDist) {
				int newDist = dist[u] + c[u][i];
				if (newDist < dist[i]) {
					dist[i] = newDist;
					pre[i] = u; //记录前一个为u
				}
			}
		}
	}
}

//v是出发点，u是目的点
void getPath(int v,int u) {
	int q[maxN];
	int count = 0;
	q[count] = u;
	count++;
	int tmp = pre[u];
	while (tmp != v) {
		q[count] = tmp;
		count++;
		tmp = pre[tmp];
	}
	q[count] = v;
	for (int i = count; i >= 0; i--) {
		if (i != 0) {
			cout << q[i] << "->";
		}
		else {
			cout << q[i] << endl;
		}
	}
}