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

一、Floyd算法

1.问题

在一个带权图中，找出各点到途中任意一点的最短路径。

2.解析

如图所示有向图，将每一个点作为任意两点的中转点，即可找到各点至任意一点的最短距离。

步骤：

将图用矩阵表示（Inf表示无线大，即不可直接到达）；

可以发现有三条路径的距离变了（用黄色标出）；

可以发现有一条路径的距离变了（用蓝色标出）；

可以发现有两条路径的距离变了（用橙色标出）；

以发现有两条路径的距离变了（用粉色色标出）；
至此所有顶点都已作为中转点遍历所有路径，此时表中的距离就是各点到任意一点的最短距离。

3.设计

int** Floyd(int** matrix，int s){   //s表示顶点个数,用二级指针传入二位列表地址
	for(i;i<s;i++){   //i用来记比中转点      
		for(j;j<s;j++){
			for(k;k<s;k++){
				如果matrix[j][k]>matrix[j][i]+matrix[i][k];   //若通过中转点距离更短，则更新
			}
		}
	}
	return matrix；
}

4.分析

时间复杂度：O(n^3)

5.源码

https://github.com/RussellWu728/Algorithm_Homework/blob/master/%E4%BD%9C%E4%B8%9A2%E2%80%94Floyd/Floyd.cpp

二、Dijkstra算法

1.问题

在一个带权图中找出两点间最短路径。

2.分析

如图所示带权有向图，给定起点与终点，建立数组用来记录从起点到任意顶点的距离，通过标记不断找到最近顶点的距离，来更新存储的数组存储的距离，知道直到所有顶点都被标记。

例：计算从a到h的最短距离

步骤：
将起点顶点a标记，并建立两个数组分别用来记录距离和标记

顶点a只能直接到达顶点b，且距离为1，所以到其他顶点的距离为Inf（无穷大）并将顶点a标记；

将已标记顶点可以直接到达的顶点标记，所以标记与a连接的顶点b，由于顶点b可到达顶点d，ab+bd<ad,所以更新距离列表顶点a到d的距离（由Inf更新为3）

标记顶点d，再次更新列表；

标记顶点d可到达的顶点c、顶点f，并更新列表；

标记顶点e，更新列表；

标记顶点g，更新列表；

标记h，更新列表，此时顶点以全部标记，此时列表中的距离即为顶点a到各点的最短距离。

3.设计

int Dijkstra(int**num,int s,int start,int finals){  
//二级指针num指向邻接表，s为顶点个数，start为起点，finals为终点
	建立数组 visited,lenth;
	while(没有被全部标记){	
		for(遍历所有已标记的点){
			for(遍历所有已标记的点连接的并且未标记的点){	
				标记此点；
				if(到此点的新距离小于已经存储的距离){
					更新列表
				}
			}
		}
	}
	return lenth[finals];   //返回起点到终点的距离;
}

4.源码

https://github.com/RussellWu728/Algorithm_Homework/blob/master/%E4%BD%9C%E4%B8%9A2%E2%80%94Dijkstra/Dijkstra.cpp