实验.-贪心法求解单源最短路径问题
————————————————————————————————作者:————————————————————————————————日期:
实验1. 贪心法求解单源最短路径问题
实验内容
本实验要求基于算法设计与分析的一般过程(即待求解问题的描述、算法设计、算法描述、算法正确性证明、算法分析、算法实现与测试)。应用贪心策略求解有向带权图的单源最短路径问题。
实验目的
通过本次实验,掌握算法设计与分析的一般过程,以及每个步骤的基本方法。并应用贪心法求解单源最短路径问题。
环境要求
对于环境没有特别要求。对于算法实现,可以自由选择C, C++, Java,甚至于其他程序设计语言。
实验步骤
步骤1:理解问题,给出问题的描述。
步骤2:算法设计,包括策略与数据结构的选择
步骤3:描述算法。希望采用源代码以外的形式,如伪代码、流程图等;
步骤4:算法的正确性证明。需要这个环节,在理解的基础上对算法的正确性给予证明;
步骤5:算法复杂性分析,包括时间复杂性和空间复杂性;
步骤6:算法实现与测试。附上代码或以附件的形式提交,同时贴上算法运行结果截图;
步骤7:技术上、分析过程中等各种心得体会与备忘,需要言之有物。
说明:步骤1-6在“实验结果”一节中描述,步骤7在“实验总结”一节中描述。
实验结果
1.问题描述
给定一个有向带全图G=(V,E),其中每条边的权是一个非负实数。另外,给定V中的一个顶点,称为源点。现在要计算源点到所有其他各个顶点的最短路径长度,这里的路径长度是指路径上所有经过边的权值之和。这个问题通常称为单源最短路径问题。
2.(1)Dijkstra算法思想
按各个结点与源点之间路径长度的非减次序,生成源点到各个结点的最短路径的方法。
即先求出长度最短的一条路径,再参照它求出长度次短的一条路径。依此类推,直到从源点到其它各结点的最短路径全部求出为止。
1959年提出的,但当时并未发表。因为在那个年代,算法基本上不被当做一种科学研究的问题。
(2)Dijkstra算法设计
集合S与V-S的划分:假定源点为u。集合S中的结点到源点的最短路径的长度已经确定,集合V-S中所包含的结点到源点的最短路径的长度待定。
特殊路径:从源点出发只经过S中的结点到达V-S中的结点的路径。
贪心策略:选择特殊路径长度最短的路径,将其相连的V-S中的结点加入到集合S中。3、描述算法
Dijkstra算法的伪代码:
DIJKSTRA(G, w, s)
INITIALIZE-SINGLE-SOURCE(G, s)
S = Φ
Q = G.V //V-S中的结点按特殊路径长度非减排序
while Q ≠Φ
u = EXTRACT-MIN(Q)
S = S ∪{u}
for each v∈G.Adj[u]
RELAX(u, v, w)
4、Dijkstra算法的求解步骤:
步骤1:设计合适的数据结构。带权邻接矩阵C记录结点之间的权值,数组dist来记录从源点到其它顶点的最短路径长度,数组p来记录最短路径。u为源点;
步骤2:初始化。令集合S={u},对于集合V-S中的所有顶点x,设置dist[x]=C[u][x]。如果顶点x与源点相邻,设置p[x]=u;否则,p[x]=-1;
步骤3:贪心选择结点。在集合V-S中依照贪心策略来寻找使得dist[x]具有最小值的顶点t,t就是集合V-S中距离源点u最近的顶点。
步骤4:更新集合S和V-S。将顶点t加入集合S中,同时更新集合V-S;
步骤5:判断算法是否结束。如果集合V-S为空,算法结束。否则,转步骤6;
步骤6:对相关结点做松弛处理。对集合V-S中的所有与顶点t相邻的顶点x,如dist[x]>dist[t]+C[t][x],则dist[x]=dist[t]+C[t][x]并设置p[x]=t。转步骤3。
5、Dijkstra算法的正确性证明–贪心选择性质:
采用归纳法。当S={s, p}时,则除源结点s之外的所有结点中,结点p到源点s的距离最短。这是显然的。
假设当S={s, p1, …, pk}时,即k个结点p1, …, pk到源点s的距离最短。当S={s, p1, …, pk, pk+1}时,很显然结点pk+1到源点s的距离是最短的。需证明:此时结点p1, …, pk到源点s的距离仍然是最短的。用反证法假设当结点pk+1加入到S后,pi结点经由结点pk+1到源点s的距离更短,即d(s, pk+1) + d(pk+1, pi) < d(s, pi),有d(s, pk+1) < d(s, pi) ,则结点pk+1
应比pi早被选择到S中,与假设相矛盾。证毕。
6、时间复杂性:
EXTRACT-MIN()的时间复杂性为O(logn);
二重循环的执行次数为(n-1)+(n-2)+…+1 = n(n-1)/2,即时间复杂性为O(n2)。
所以,该算法的时间复杂性为O(n2)。
空间复杂性:
优先队列Q的大小为n-1;
所以,该算法的空间复杂性为O(n)。
7、算法实现与测试。
实验总结
Dijkstra算法采用贪心策略,按各个顶点与源点之间路径长度递增的次序,生成源点到各个顶点的最短路径方法。先求出长度最短的一条路径,在参照它求出长度次短的一条路径,以此类推,直到从源点到其他各个顶点的最短路径全部求出。
在构造带权邻接矩阵时候,二维数组在dijkstra算法里采用指针传递参数,结果求得的最短路径为ox652555等等,因为算法按照课本编写所以觉得没有错,就在输出部分困扰了很久,这样告诉我们学习不能生搬硬套,出问题不可怕,仔细分析问题来源并解决才是最重要的。在定义无穷大整数时,程序里是999,输入矩阵时变成10000,结果出来很大的数没有规律。在设置循环变量时,从0到n导致输入数组的时候出错,又写了输出语句还是弄不明白,小小的一个bug浪费了大量的时间,现在要好好的弥补编程知识。利用经典的算法知识可以解决现实生活中的许多问题,利用程序实现充满乐趣和挑战。
Dijkstra算法代码:
#include
using namespace std;
const int intmax=999;
void Dijkstra(int n,int u,int* dist,int* p,int **&c){
bool s[n];
for(int i=1;i<=n;i++){
dist[i]=c[u][i];
s[i]=false;
if(dist[i]==intmax)
p[i]=-1;
else
p[i]=u;
}
dist [u]=0;
s[u]=true;
for(int i=1;i<=n;i++){
int temp=intmax;
int t=u;
for(int j=1;j<=n;j++){
if((!s[j])&&(dist[j] { t=j; temp=dist[i]; } if(t==u) break; s[t]=true; for(j=1;j<=n;j++) if((!s[j])&&(c[t][j] if(dist[j]>(dist[t]+c[t][j])) { dist[j]=dist[t]+c[t][j]; p[j]=t; } } } } int main() { cout<<"输入顶点个数: "; cin>>n; int* dist=new int[n+1]; int* p=new int[n+1]; int** c=new int*[n+1]; for(int i=0;i { c[i]=new int[n+1]; } cout<<"输入邻接矩阵: "< for(int i=0;i { for(int j=0;j { cin>>c[i][j]; } } int u; cout<<"输入源点:"; cin>>u; Dijkstra(n,u,dist,p,c); for(int i=1;i { cout<"< } for(int i=1;i { cout<<"顶点"< } return 0; } /* 0 8 32 999 999 12 0 16 15 999 999 29 0 999 13 999 21 999 0 7 999 999 27 19 0 */