《讨鬼传》素材入手方法Dijkstra算法-寻找有向图中最短路径.doc
Dijkstra算法-寻找有向图中最短路径
Dijkstra算法是由荷兰计算机科学家艾兹格?迪科斯彻发现的。算法解决的是有向图中最短路径问题。
举例来说,如果图中的顶点表示城市,而边上的权重表示著城市间开车行经的距离。 Dijkstra算法可以用来找到两个城市之间的最短路径。
Dijkstra算法的输入包含了一个有权重的有向图,以及G中的一个来源顶点。 GS我们以V表示G中所有顶点的集合。图中的每一个边,都是两个顶点所形成的有序元素对。(u,v)表示从顶点u到v有路径...
Dijkstra算法-寻找有向图中最短路径.doc
Dijkstra算法-寻找有向图中最短路径
Dijkstra算法是由荷兰计算机科学家艾兹格?迪科斯彻发现的。算法解决的是有向图中最短路径问题。
举例来说,如果图中的顶点
示城市,而边上的权重表示著城市间开车行经的距离。 Dijkstra算法可以用来找到两个城市之间的最短路径。
Dijkstra算法的输入包含了一个有权重的有向图,以及G中的一个来源顶点。 GS我们以V表示G中所有顶点的集合。图中的每一个边,都是两个顶点所形成的有序元素对。(u,v)表示从顶点u到v有路径相连。 假设E为所有边的集合,而边的权重则由权重函数w: E ? [0, ?]定义。 因此,w(u,v)就是从顶点u到顶点v的非负花费值(cost)。 边的花费可以想像成两个顶点之间的距离。任两点间路径的花费值,就是该路径上所有边的花费值总和。 已知有V中有顶点s及,Dijkstra算法可以找到到的最低花费路径(i.e. 最短路径)。 这个算法tst
也可以在一个图中,找到从一个顶点s到任何其他顶点的最短路径。
算法描述
这个算法是通过为每个顶点v保留目前为止所找到的从s到v的最短路径来工作的。初始时,源点s的路径长度值被赋为0(d[s]=0), 同时把所有其他顶点的路径长度设为无穷大,即表示我们不知道任何通向这些顶点的路径(对于V中所有顶点v除s外d[v]= ?)。当算法结束时,d[v]中储存的便是从s到v的最短路径,或者是无穷大(如果路径不存在的话)。
Dijstra算法的基础操作是边的拓展:如果存在一条从u到v的边,那么从s到v的最短路径可以通过将边(u,v)添加到s到u的尾部来拓展。这条路径的长度是d[u]+w(u,v)。如果这个值比目前已知的d[v]的值要小,我们可以用新值来替代当前d[v]中的值。拓展边的操作一直执行到所有的d[v]都代表从s到v最短路径的花费。这个算法经过适当的组织因而当d[u]达到它最终的值的时候,每条边(u,v)都只被拓展一次。
算法维护两个顶点集S和Q。集合S保留了我们已知的所有d[v]的值已经是最短路径的值顶点,而集合Q则保留其他所有顶点。集合S初始状态为空,而后每一步都有一个顶点从Q移动到S。这个被选择的顶点是Q中拥有最小的d[u]值的顶点。当一个顶点u从Q中转移到了S中,算法对每条外接边(u,v)进行拓展。
算法思想
设S为最短距离已确定的顶点集(看作红点集),V-S是最短距离尚未确定的顶点集(看作蓝点集)。
?初始化
初始化时,只有源点s的最短距离是已知的(SD(s)=0),故红点集S={s},蓝点集为空。
?重复以下工作,按路径长度递增次序产生各顶点最短路径
在当前蓝点集中选择一个最短距离最小的蓝点来扩充红点集,以保证按路径权重递增的次序来产生各顶点的最短路径。
当蓝点集中仅剩下最短距离为?的蓝点,或者所有蓝点已扩充到红点集时,s到所有顶点的最短路径就求出来了。
注意:
?若从源点到蓝点的路径不存在,则可假设该蓝点的最短路径是一条长度为无穷大的虚拟路径。
?从源点s到终点v的最短路径简称为v的最短路径;s到v的最短路径长度简称为v的最短距离,并记为SD(v)。
(3)在蓝点集中选择一个最短距离最小的蓝点k来扩充红点集
根据按长度递增序产生最短路径的思想,当前最短距离最小的蓝点k的最短路径是:
源点,红点1,红点2,…,红点n,蓝点k
距离为:源点到红点n最短距离+<红点n,蓝点k>边长
为求解方便,设置一个向量D[0((n-1],对于每个蓝点v? V-S,用D[v]
从源点s到达v且除v外中间不经过任何蓝点(若有中间点,则必为红点)的"最短"路径长度(简称估计距离)。
若k是蓝点集中估计距离最小的顶点,则k的估计距离就是最短距离,即若D[k]=min{D[i] i?V-S},则D[k]=SD(k)。
初始时,每个蓝点v的D[c]值应为权w
,且从s到v的路径上没有中间点,因为该路径仅含一条边。
注意:
在蓝点集中选择一个最短距离最小的蓝点k来扩充红点集是Dijkstra算法的关键
(4)k扩充红点集s后,蓝点集估计距离的修改
将k扩充到红点后,剩余蓝点集的估计距离可能由于增加了新红点k而减小,此时必须调整相应蓝点的估计距离。
对于任意的蓝点j,若k由蓝变红后使D[j]变小,则必定是由于存在一条从s到j且包含新红点k的更短路径:P=。且D [j]减小的新路径P只可能是由于路径和边组成。
所以,当length(P)=D[k]+w小于D[j]时,应该用P的长度来修改D[j]的值。
(5)Dijkstra算法
Dijkstra(G,D,s){
//用Dijkstra算法求有向网G的源点s到各顶点的最短路径长度
//以下是初始化操作
S={s};D[s]=0; //设置初始的红点集及最短距离
for( all i? V-S )do //对蓝点集中每个顶点i
D[i]=G[s][i]; //设置i初始的估计距离为w
//以下是扩充红点集
for(i=0;iD[k]+G[k][j])
//新红点k使原D[j]值变小时,用新路径的长度修改D[j],
//使j离s更近。
D[j]=D[k]+G[k][j];
}
}
已经利用优先队列实现了查找最短路径长度的dijkstra算法,怎么回溯出最短距离路线上经过的点呢,
2011-5-25 20:47
提问者:帝星卡卡浏览次数:次 22 | 291
//此程序成功找到了邻接矩阵中两点的最短距离长度,但是没有实现路径中经过的点的显示
#include
#include
#include
using namespace std;
#define INF 200 //最大距离表示节点之间不通
#define MAXN 1100
struct way //放入优先队列Q中的结构体
{
int s;//v->s=d
int d;//distance
bool operator <(const way k)const
{
return k.dQ;
bool flag[MAXN]={false};//flag[i]==1 means it is in the end point set
way temp,now;
now.s=v; //初始化way的实例now,并将节点加入队列
now.d=0;
Q.push(now);
point[v][v]=0; //初始化最短距离
//prev[v]=0;
while(!Q.empty())
{
now=Q.top(); //队列重排列
Q.pop();//使用优先队列的pop功能使已找到的最短距离节点出队列
if(flag[now.s])
continue;
flag[now.s]=1;
for(int i=1;i<=n;i++)
{
if(!flag[i]&&map[now.s][i]!=INF&&point[v][i]>point[v][now.s]+map[now.s][i]) //
修改经过now.s到集合任意点上可达的最短距离
{
temp.s=i;
temp.d=point[v][now.s]+map[now.s][i];
point[v][i]=temp.d;
prev[v]=temp.s;
Q.push(temp);
}
}
}
}
void init()//初始化
{
int i,j;
int a,b,c;
prev = (int *)malloc(sizeof(int)*n);
cout<<"请输入邻接矩阵,权值间以空格分隔"<
#include
#include
using namespace std;
#define INF 200 //最大距离表示节点之间不通
#define MAXN 1100
struct way //放入优先队列Q中的结构体
{
int s;//v->s=d
int d;//distance
bool operator <(const way k)const
{
return k.dQ;
bool flag[MAXN]={false};//flag[i]==1 means it is in the end point set
way temp,now;
now.s=v; //初始化way的实例now,并将节点加入队列
now.d=0;
Q.push(now);
point[v][v]=0; //初始化最短距离
//prev[v]=0;
while(!Q.empty())
{
now=Q.top(); //队列重排列
Q.pop();//使用优先队列的pop功能使已找到的最短距离节点出队列
if(flag[now.s])
continue;
flag[now.s]=1;
for(int i=1;i<=n;i++)
{
if(!flag[i]&&map[now.s][i]!=INF&&point[v][i]>point[v][now.s]+map[now.s][i]) //修改经过
now.s到集合任意点上可达的最短距离
{
temp.s=i;
temp.d=point[v][now.s]+map[now.s][i];
point[v][i]=temp.d;
prev[v]=temp.s;
Q.push(temp);
}
}
}
}
void init()//初始化
{
int i,j;
int a,b,c;
prev = (int *)malloc(sizeof(int)*n);
cout<<"请输入邻接矩阵,权值间以空格分隔"<边长
为求解方便,设置一个向量D[0((n-1],对于每个蓝点v? V-S,用D[v]记录从源点s到达v且除v外中间不经过任何蓝点(若有中间点,则必为红点)的"最短"路径长度(简称估计距离)。
若k是蓝点集中估计距离最小的顶点,则k的估计距离就是最短距离,即若D[k]=min{D[i] i?V-S},则D[k]=SD(k)。
初始时,每个蓝点v的D[c]值应为权w,且从s到v的路径上没有中间点,因为该路径仅含一条边。
注意:
在蓝点集中选择一个最短距离最小的蓝点k来扩充红点集是Dijkstra算法的关键
(4)k扩充红点集s后,蓝点集估计距离的修改
将k扩充到红点后,剩余蓝点集的估计距离可能由于增加了新红点k而减小,此时必须调整相应蓝点的估计距离。
对于任意的蓝点j,若k由蓝变红后使D[j]变小,则必定是由于存在一条从s到j且包含新红点k的更短路径:P=。且D [j]减小的新路径P只可能是由于路径和边组成。
所以,当length(P)=D[k]+w小于D[j]时,应该用P的长度来修改D[j]的值。
(5)Dijkstra算法
Dijkstra(G,D,s){
//用Dijkstra算法求有向网G的源点s到各顶点的最短路径长度
//以下是初始化操作
S={s};D[s]=0; //设置初始的红点集及最短距离
for( all i? V-S )do //对蓝点集中每个顶点i
D[i]=G[s][i]; //设置i初始的估计距离为w
//以下是扩充红点集
for(i=0;iD[k]+G[k][j])
//新红点k使原D[j]值变小时,用新路径的长度修改D[j],
//使j离s更近。
D[j]=D[k]+G[k][j]; }
}
本文档为【《讨鬼传》素材入手方法】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑,
图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。