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

; 给定带权有向图G=(V,E)，其中每条边的权值是非负数，u称为源点；图G的顶点编号为1~n(1≤n≤100)。

求从u到G中所有其余顶点的最短路径长度。;u;判断题。

Dijkstra算法按路径长度递增的次序依次产生源点到各点的最短路径。

A.错误

B.正确

;u;;;;;算法需要的数据结构：

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的最短距离。;迭代;/*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(in){

v为满足s[v]==0dist[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*/

};/*借助优先队列实现迪杰斯特拉算法*/

#includeiostream

#includecstring

#includequeue

usingnamespacestd;

#defineMaxSize101

typedefstruct{

intno;/*no表示顶点的编号，从1开始*/

intdist=0x3f3f3f3f;/*dist表示长度，初值为一个较大的值*/

intprev=0;/*prev表示源点到该点的最短路径中该点的前驱顶点的编号*/

intflag=0;/*flag=0表示源点到该点的最短路径还未求出*/

}vertex;

structcomp{/*定义优先队列的排序规则*/

booloperator()(vertexa,vertexb){

returna.distb.dist;

}

};;/*函数功能：dijkstra算法求解单源最短路径*/

/*参数说明：n表示图中顶点总数，graph表示图的邻接矩阵*/

/*a存储顶点信息，u表示源点编号*/

voiddijsktra(intn,intgraph[][MaxSize],vertexa[],intu){

priority_queuevertex,vectorvertex,compp;/*定义优先队列*/

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;/*出队顶点的最短路径已得到*/

……

};单选题。

Dijkstra算法求解单源最短路径，适用于（）。

A.权值为非负

B.权值为负

C.权值无要求

;Q：迪杰斯特拉算法为什么需要“边的权值为非负数”？;图中有负值环时，不存在最短路径；

图中无负值环但存在负值边时，不能使用Dijkstra。