算法设计与分析 课件 10.3.2-综合应用-最短路径问题-迪杰斯特拉算法

信息工程大学算法设计与分析综合应用—最短路径问题迪杰斯特拉算法国家级实验教学示范中心计算机学科组规划教材算法设计与分析Python案例详解微课视频版

给定带权有向图G=(V,E)，其中每条边的权值是非负数，u称为源点；图G的顶点编号为1~n(1≤n≤100)。求从u到G中所有其余顶点的最短路径长度。50102060100301012534uu1u2…uk-1ukuk+1vuu1u2…uk-1ukuk+1uu1uu1u2…最短路径长度递增迪杰斯特拉(Dijkstra)提出：按最短路径长度递增的次序，依次产生每个点的最短路径。最短路径问题满足最优子结构性质：u到v的最短路径包含u到该路径上其它各点的最短路径。边的权值为非负判断题。Dijkstra算法按路径长度递增的次序依次产生源点到各点的最短路径。A.错误

B.正确uu1u2…uk-1ukuk+1vuu1u2…uk-1ukuk+1uu1uu1u2…最短路径长度递增Dijkstra提出：按最短路径长度递增的次序，依次产生每个点的最短路径。进一步可知：第一条最短路径：直达其他：利用已得到最短路径的点，求未知点的最短路径集合集合SS’S中的点表示已找到该点的最短路径S’中的点表示未找到最短路径的点1.将图中点分成两个集合：S和S’;集合集合SS’1.将图中点分成两个集合：S和S’；2.计算从源点u出发，经S中点到S’中各点的最短路径长度；集合集合SS’1.将图中点分成两个集合：S和S’；2.计算从源点u出发，经S中点到S’中各点的最短路径长度；3.从S’中选择距离最短的点v加入S中，并从S’中移除该点，同时更新S’中点的最短距离；集合S集合S’1.将图中点分成两个集合：S和S’；2.计算从源点u出发，经S中点到S’中各点的最短路径长度；3.从S’中选择距离最短的点v加入S中，并从S’中移除该点，同时更新S’中点的最短距离；4.重复第3步，直到S’为空。算法需要的数据结构：1.对各点所处集合的状态进行标记，使用数组s；2.需要存储S’中各点的距离，使用数组dist；3.记录点的前驱，使用数组pre；初始时，先将源点u放入S。对u之外的每个顶点v，令dist[v]为边<u,v>的权或+∞；不断地做贪心选择来扩充S，直到所有顶点均进入S。贪心策略：如果顶点v不属于S，且dist[v]值最小，则优先选择v。当v加入S后，需调整尚未进入S的点的dist和pre。算法结束时，dist[i]就是u到点i的最短距离。迭代Svdist[2]pre[2]dist[3]pre[3]dist[4]pre[4]dist[5]pre[5]初始1101+∞-1301100111,22101602301100121,2,4410150430190431,2,4,3310150430160341,2,4,3,5550102060100301012534迭代Svdist[2]pre[2]dist[3]pre[3]dist[4]pre[4]dist[5]pre[5]初始1101+∞-1301100111,22101602301100121,2,4410150430190431,2,4,3310150430160341,2,4,3,55选择题。根据下表，源点1到点5的最短路径长度和最短路径是（）。A.60,1-5

B.60,1-3-5C.60,1-4-3-5/*graph表示图的邻接矩阵，u表示源点，n表示顶点总数*/voidDijkstra(int**graph,intu,intn){ints[MaxSize],i=0;memset(s,0,sizeof(s));s[u]=1;for(i=1;i<=n;i++){dist[i]=graph[u][i];pre[i]=-1;}i=1;while(i<n){v为

满足s[v]==0&&dist[v]最小的点;s[v]=1;i++;for(对每个相邻于v的顶点k){

if

（(s[k]==0)&&

(dist[v]+graph[v][k]<dist[k])）{

dist[k]=dist[v]+graph[v][k]); pre[k]=v; }}/*endfor*/}/*endwhile*/}时间复杂度：O(n2)/*借助优先队列实现迪杰斯特拉算法*/#include<iostream>#include<cstring>#include<queue>usingnamespacestd;#defineMaxSize101typedefstruct{intno;/*no表示顶点的编号，从1开始*/intdist=0x3f3f3f3f;/*dist表示长度，初值为一个较大的值*/intprev=0;/*prev表示源点到该点的最短路径中该点的前驱顶点的编号*/intflag=0;/*flag=0表示源点到该点的最短路径还未求出*/}vertex;structcomp{/*定义优先队列的排序规则*/booloperator()(vertexa,vertexb){returna.dist>b.dist;}};/*函数功能：dijkstra算法求解单源最短路径*//*参数说明：n表示图中顶点总数，graph表示图的邻接矩阵*//*a存储顶点信息，u表示源点编号*/voiddijsktra(intn,intgraph[][MaxSize],vertexa[],intu){priority_queue<vertex,vector<vertex>,comp>p;/*定义优先队列*/inti=0;a[u].dist=0;/*设置源点到它自身的最短路径长度为0*/p.push(a[u]);/*源点加入优先队列*/intt=0;vertexv;while(!p.empty()){v=p.top();/*取dist最小的顶点*/p.pop();/*dist最小的顶点出队*/t=v.no;a[t].flag=1;/*出队顶点的最短路径已得到*/ ……}借助优先队列优化算法时间复杂度O(|V|log|V|)单选题。

Dijkstra算法求解单源最短路径，适用于（）。 A.权值为非负 B.权值为负 C.权值无要求Q：迪杰斯特拉算法为什么需要“边的权值为非负数”