Dijkstra算法模型设计与实现Word文档格式.doc
- 文档编号:3956793
- 上传时间:2023-05-02
- 格式:DOC
- 页数:6
- 大小:470KB
Dijkstra算法模型设计与实现Word文档格式.doc
《Dijkstra算法模型设计与实现Word文档格式.doc》由会员分享,可在线阅读,更多相关《Dijkstra算法模型设计与实现Word文档格式.doc(6页珍藏版)》请在冰点文库上搜索。
2.寻找下一个与目的节点最近的节点,即求使下式成立的。
置。
如果包括了所有的节点,则算法结束。
,
3.更改标定值,即对所有的,置,返回第2步。
三、Dijkstra算法实现
根据Dijkstra算法描述编写程序进行实现,程序中采用邻接矩阵表示一个有向图,输入为该图的邻接矩阵以及目的节点,输出为图中各点的邻接关系,依照次邻接关系可得到到达目的节点的最短路径。
程序用C语言编写,GCC环境编译,具体代码见附录。
四、运行结果及分析
选择一具有7个节点的有向图进行实验,其各边权重及拓扑结构如下所示:
图1实验用图
选取节点1为目的节点,运行程序:
1.输入表示该图的邻接矩阵,不相邻的节点间链路权值用-1表示,代表无穷大;
2.输入目的节点编号;
3.得到输出结果,如下图所示。
输出结果
图2程序运行截图1
将输出结果用图表示为:
图3到达目的节点1的最短路由
更改目的节点,选取目的节点为节点5,重新运行程序,得到结果如下:
目的节点更改为5
图4程序运行截图2
输出结果用图表示为:
图5到达目的节点5的最短路由
选择不同的目的节点,利用此程序均能得出正确的最短路径,证明了程序的正确性。
达到了较好的效果。
附源代码:
#include<
stdio.h>
stdlib.h>
#defineN7/*节点个数*/
intmain()
{
doublee[N][N],d[N];
intv;
/*目的节点*/
inti,j,min,x;
longp=0;
intpath[N];
/*节点从0开始计数*/
for(i=0;
i<
N;
i++)
{
printf("
Inputtheweightstonode%d\n"
i+1);
for(j=0;
j<
j++)
{
scanf("
%lf"
&
e[i][j]);
/*不相邻节点间边权用负数表示*/
if(e[i][j]<
0)
e[i][j]=32767;
}
}
printf("
Inputdestinationnode\n"
);
scanf("
%d"
v);
/*输入目的节点*/
v-=1;
/*初始化*/
for(i=0;
i++)
d[i]=e[i][v];
path[i]=v;
p|=1<
<
v;
while
(1)
min=32767;
if(p&
(1<
j))
continue;
if(min>
d[j])
{
i=j;
min=d[j];
}
p|=1<
i;
if(p>
=(1<
N)-1)
break;
min=32767;
for(i=0;
if(min>
d[i]+e[j][i])
{
min=d[i]+e[j][i];
x=i;
}
if(d[j]>
min)
d[j]=min;
path[j]=x;
***result:
***\n"
if(i==v)
continue;
P%d-->
P%d\n"
i+1,path[i]+1);
exit(EXIT_SUCCESS);
}
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- Dijkstra 算法 模型 设计 实现