Dijkstra算法模型设计与实现

1、Dijkstra算法模型设计与实现一、Dijkstra算法概述Dijkstra算法是一种点对多点的集中式最短路径算法，即 寻找网 络中其他所有节点到目的节点的最短路径。Dijkstra算法通过对路径的长度进行迭代，从而计算出到达目的节点的最短路径。其基本思想是按照路径长 度增加的顺序来寻找最 短路径，显然有：到达目的节点v的最短路径中最短的肯定是 节点的 最近节点v所对应的单条链路，最短路径中下一个最短的肯定是 节点 v的下一个最近的邻节点所对应的单条链路，或者是通过前面选定的 节点的最短的由两条 链路组成的的路径，依次类推。二、Dijkstra算法描述设每个节点i标定的到达目的节点1的最短路

2、径长度估计为Di， 如果在迭代的过程中，Di已变成一个确定的值，称节点i为永久标定 的节点，这些永久标定的节点的集合用P表示。在算法的每一步中， 在P以外的节点中，必定是选择与目的节点1最近的节点加入到集合 P中。具体算法如下：1. 初始化，即 P r 门，Di = 0，Dj = dji，j = 1。（若 j,1 A，则 dji：）。2. 寻找下一个与目的节点最近的节点，即求使下式成立的i。置 丨。如果P包括了所有的节点，则算法结束。Di 二 mn D i p3. 更改标定值，即对所有的j P，置Dj二min Dj,dji D,，返 回第2步。三、Dijkstra算法实现根据Dijkstra算

3、法描述编写程序进行实现，程序中采用邻接矩阵 表示一个有向图，输入为该图的邻接矩阵以及目的节点，输出为图中 各点的邻接关系，依照次邻接关系可得到到达目的 节点的最短路径。程序用C语言编写，GCC环境编译，具体代码见附录。四、运行结果及分析选择一具有7个节点的有向图进行实验，其各边权重及拓扑结选取节点1为目的节点，运行程序：1. 输入表示该图的邻接矩阵，不相邻的节点间链路权值用-1表 示，代表无穷大；2. 输入目的节点编号；3得到输出结果，如下图所示。jsro bdsh Efix25yang(naxoMacBook-Pro:pro yangkaizhis ./dijkstraInput the w

4、eights to node 1 0-12-1 -1 -1 -1Input the weights to Aode 2 40-1-1 -1 -1 -1Tn put the weights to node 35603-19-1Input the weights to node 413404-1-1Input the weights to node 5-1 1 -1 S e 2 JInput me weights to nodp 6-3 0 7Input tfie weighTs to node 1T -1-1-1220Input destination node1输出结果resu li; *P2

5、 *?1PdAPlP4?2/P5?&P&P4P7P6yuilyrid luMdihuuk-Prg: pro yangkaizhis图2程序运行截图1将输出结果用图表示为:更改目的节点，选取目的节点为节点5，重新运行程序，得到结果如下:匚i pro bAh 68x25/yang(natoMacBook-Pro:pro yangkaizhii ./dijkstra3Input the weights to node 1 0-12-1 -1 -1 -1Input the weights to node 2 40-1-1 -1 -1 -1In put the weights to node 35603

6、-19-1Input the weights to node 4-13404-1-1Input the weights to node 5-1 10 -1 S 0 2 -1Input The weights to nodn 6-1-1-1339 -1Input tfie weights to node 1T T 112 2 0L-i.目的节点更改为5：5*=*result;米桂P1*P3P2P1P3?4P4?5P&P5 P7?5 yangmaToMacBaok-Pro:pro yangkaizhi J图4程序运行截图2输出结果用图表示为：选择不同的目的节点，利用此程序均能得出正确的最短路径，证

7、明了程序的正确性。达到了较好的效果。附源代码:#inelude #inelude #define N 7 /* 节点个数 */int main()double eNN,dN;int v; /*目的节点*/int i,j,min,x;long p=0;int pathN;/*节点从0开始计数*/for(i=0;iN;i+)printf(Input the weights to node %dn,i+1);for(j=0;jN;j+)scan f(%lf, &eij);/* 不相邻节点间边权用负数表示*/if(eij0) eij=32767;printf(Input destination noden); scanf(%d，&v); /*输入目的节点*/ v-=1;/*初始化*/for(i=0;iN;i+)di=eiv; pathi=v;p|=1vvv;while(1)min=32767;for(j=0;j dj)i=j;mi n=dj; p|=1=(1vN)-1)break;for(j=0;jN;j+)if(P&(1 di+eji)min=di+eji; x=i; if(djmi n) dj=mi n;p