<学习笔记> 迪克斯彻算法

2017-10-05

Dijkstra是荷兰科学家艾兹格.迪科斯彻发明的。这个算法解决的是有向单源最短路径问题。
这个算法的核心思想是贪心算法。也就是每一步都做出当前看似最好的选择。不从整体上优先考虑，仅作一种局部的最优解。
结合我们的贪心的思想和我们的问题来分析构造我们的算法。
初始时，原点的路径长度值赋值为0，同时把其他顶点的路径长度设置为无穷大(就是很大很大嘛),也就是表示一开始我们并不知道如何
从原点到达其他顶点的路径。当我们计算完成后，一方面得到从起点到终点的最短路径，如果路径不存在的话那么则得到无穷大的答案。
通过贪心选择，如果存在一个中间顶点到另一个中间顶点的路径，那么我们可以通过将这条路径添加到起点到第一个中间顶点的尾部，构成一条
更长的路径，如果这个值比目前已知的路径的长度要小，那么我们就要用新的值来代替旧的值，贪心的选择当前最短的路径。这个操作一直执行到
我们的第二个中间顶点变为终点，那么我们的答案就得到了。

#include<iostream>
#include<cstring>
using namespace std;
const int MAXL = 10000;//假想的无穷大；
const int MAXN=2505;
int co[MAXN][MAXN];
void dkst(int n,int v,int dist[],int prev[],int c[][MAXN]) {
	//dist存储从原点到某个顶点的最短路径；
	//c存储从某个顶点到另一个顶点的权；
	//prev存储从原点到到顶点的最短路径上的前一个顶点；
	//s为了区分两个集合；
	//初始化；
	bool s[MAXN];//区分集合；
	for (int i = 1; i <= n; i++) {
		dist[i] = c[v][i];//从起点到顶点i的最短路径初始化；
		s[i] = false;//添加入未计算过集合；
		if (dist[i] == MAXL) {
			prev[i] = 0;//如果从原点到某顶点没有直接路径；
							//前顶点初始化为0；
		}
		else {
			prev[i] = v;//前顶点初始化为原点；
		}
	}
	dist[v] = 0;//从原点到原点长度为0啊；
	s[v] = true;//将原点放入已计算顶点集；
	for (int i = 1; i < n; i++) {
		int t = MAXL;//先初始化为无穷大；
		int u = v;
		for (int j = 1; j <= n; j++) {
			if ((!s[j]) && (dist[j] < t)) {//如果顶点j未计算且找到了到顶点j的更短的路径；
				u = j;
				t = dist[j];//到顶点j的距离更新;
			}
		}
        s[u] = true;//将顶点u放入已计算顶点集；
		for (int j = 1; j <= n; j++) {
			if ((!s[j]) && (c[u][j] < MAXL)) {
				int newdist = dist[u] + c[u][j];
				if (newdist < dist[j]) {//更新最短路径长度；
					dist[j] = newdist;
					prev[j] = u;
				}
			}
		}
	}
}
int main() {
	int t, c, ts, te;
	cin >> t >> c >> ts >> te;
    memset(co,MAXL,sizeof(co));
	for (int i = 1; i <= c; i++) {
		int rs, re, ci;
    cin>>rs>>re>>ci;
		co[rs][re] = ci;
    co[re][rs] = ci;//双向道路就要这么初始化；
	}
	int dist[MAXN];
	int prev[MAXN];
	dkst(t,ts,dist,prev,co);
	cout << dist[te] << endl;
	return 0;
}