算法分析与设计-作业2-Dijkstra算法求最短路径

1.问题

对于下图使用Dijkstra算法求由顶点a到顶点h的最短路径。

2.解析

Dijkstra算法的核心思想是贪心算法的思想。贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。
Dijkstra算法即从初始点开始，选择距离最近的点，计算路径长度，若发现距离更近就更新，逐渐扩散至全局。
步骤如下：
1.选定起始点a；

2.a点只能到达b点，所以a->b的minPath=1；

3.b点只能到达d点，所以a->d的minPath=1+2=3；

4.由于c点只能回到a点，所以只能选择f点，所以a->f的minPath=1+2+8=11；

5.f点只能到达e点，所以a->e的minPath=1+2+8+2=13；

6.e点有两条路，但由于d点已经被选择过，所以只能选择g点，a->g的minPath=1+2+8+2+2=15；

7.g点有两条路，但由于f点已经被选择过，所以只能选择h点，a->h的minPath=1+2+8+2+2+3=18；

3.设计

void Dijkstra()
{
	int t,k,min;				//标记最小距离
	for (i = 1; i <= n; ++i){
		min = 100000;
		for (j = 1; j <= n; ++j){
			if (vis[j] == 0 && dis[j] < min){
				min = dis[j];
				t = j;
			}
		}
		vis[t] = 1;
		for (k = 1; k <= n; k++){
			if (vis[k] == 0 && dis[k] > dis[t] + map[t][k] && map[t][k] < 100000){
				dis[k] = dis[t] + map[t][k];
			}
		}
	}
}

4.分析

核心代码是由双重循环构成，所以算法复杂度为O(n^2)

5.源码

https://github.com/chainessss/Algorithm-