Dijkstra算法模型设计与实现

Dijkstra 算法模型设计与实现一、Dijkstra算法概述Dijkstra 算法是一种点对多点的集中式最短路径算法，即寻找网络中其他所有节点到目的节点的 最短路径。Dijkstra 算法通过对路径的长度进行迭代，从而计算出到达目的节点的最短路径。其基本思想是 按照路径长度增加的顺序来寻找最短路径，显然有：到达目的节点 v 的最短路径中最短的肯定是节点 的最近节点V所对应的单条链路，最短路径中下一个最短的肯定是节点V的下一个最近的邻节点所对应 的单条链路，或者是通过前面选定的节点的最短的由两条链路组成的的路径，依次类推。二、Dijkstra算法描述设每个节点i标定的到达目的节点1的最短路径长度估计为D，如果在迭代的过程中，D已变成 ii 一个确定的值，称节点i为永久标定的节点，这些永久标定的节点的集合用P表示。在算法的每一步 中，在P以外的节点中，必定是选择与目的节点1最近的节点加入到集合P中。具体算法如下：1.初始化，即 P = 1，D = 0， D = d，丿 1。（若（；1）纟A，则d =）。1 j j 1j 12寻找下一个与目的节点最近的节点，即求使下式成立的i。置厂二尸。如果P包括了所有 的节点，则算法结束。D = min D， i 纟 Pj舒j3更改标定值，即对所有的j纟P，置D = minD ,d + D 返回第2步。j i j ji i三、Dijkstra算法实现根据 Dijkstra 算法描述编写程序进行实现，程序中采用邻接矩阵表示一个有向图，输入为该图的 邻接矩阵以及目的节点，输出为图中各点的邻接关系，依照次邻接关系可得到到达目的节点的最短路 径。程序用C语言编写，GCC环境编译，具体代码见附录。四、运行结果及分析选择一具有 7 个节点的有向图进行实验，其各边权重及拓扑结构如下所示：图 1 实验用图选取节点 1 为目的节点，运行程序：1. 输入表示该图的邻接矩阵，不相邻的节点间链路权值用-1 表示，代表无穷大2. 输入目的节点编号；3. 得到输出结果，如下图所示。图2 程序运行截图1 将输出结果用图表示为：图 3 到达目的节点 1 的最短路由更改目的节点，选取目的节点为节点 5，重新运行程序，得到结果如下目的节点yangmaioMacBoo-k-Pro; pro yanqkaizhis . /dijkstra1nodeInput the weights to 0-12-1 -1 -1 -1Input the weights to4 & -1 -1 -1 -1 -1Input the weigtits5503-19-1Input the weights13404-1-1Input-1 10Input-1 -1Input-1 -1Input更改为5PlP3P2P1P3P4P4P5P5P5P7P5yanguiaoMacBoo-k-Pro: pro yangkaizhis |lhe weights -1602-1 ihe weights -1 3 3 & -1 the weights -1 2 2 & desTinaxiontotototonodenodenodenodenodenodenode图4 程序运行截图2输出结果用图表示为：图5到达目的节点5的最短路由选择不同的目的节点，利用此程序均能得出正确的最短路径，证明了程序的正确性。达到了较好 的效果。附源代码：#include#include#defineN7/*节点个数*/intmain()doubleeNN,dN;int v;/ *目的节点*/inti,j,min,x;longp=0;intpathN;/*节点从0 开始计数*/for(i=0;iN;i+)printf(Inputtheweightstonode%dn,i+1);for(j=0;jN;j+)scanf(%lf,&eij);/*不相邻节点间边权用负数表示*/if(eij0) eij=32767;printf(Inputdestinationnoden);scanf(%d，& v);/ *输入目的节点*/*初始化*/for(i=0;iN;i+)di=eiv;pathi=v;p|=1v;while(1)min=32767;for(j=0;jN;j+)if(p&(1dj)i=j;min=dj;p|=1=(1N)-1)break;for(j=0;jN;j+)if(p&(1j)v-=1;continue;min=32767;for(i=0;idi+eji)min=di+eji;x=i;if(djmin)dj=min;pathj=x;printf(*result:*n);for(i=0;iP%dn,i+1,pathi+1);exit(EXIT_SUCCESS);