Dijkstra算法模型设计与实现

Dijkstra算法模型设计与实现

一、Dijkstra算法概述

Dijkstra算法是一种点对多点的集中式最短路径算法，即寻找网络中其他所有节点到目的节点的最短路径.

Dijkstra算法通过对路径的长度进行迭代，从而计算出到达目的节点的最短路径。其基本思想是按照路径长度增加的顺序来寻找最短路径，显然有:到达目的节点v的最短路径中最短的肯定是节点的最近节点v所对应的单条链路,最短路径中下一个最短的肯定是节点v的下一个最近的邻节点所对应的单条链路,或者是通过前面选定的节点的最短的由两条链路组成的的路径,依次类推。

二、Dijkstra算法描述

设每个节点i标定的到达目的节点1的最短路径长度估计为Di,如果在迭代的过程中,Di已变成一个确定的值,称节点i为永久标定的节点,这些永久标定的节点的集合用P表示。在算法的每一步中，在P以外的节点中,必定是选择与目的节点1最近的节点加入到集合P中.具体算法如下：

1。 初始化，即P={1}，D1=0,Dj=dj1，j¹1.(若(j,1)ÏA，则。 dj1=¥）

2。 寻找下一个与目的节点最近的节点，即求使下式成立的i。置

。如果P包括了所有的节点，则算法结束。

Di=minDj，iÏP

jÏP

3。 更改标定值，即对所有的jÏP，置Dj=minéëDj,dji+Diùû，

i返回第2步.

三、Dijkstra算法实现

根据Dijkstra算法描述编写程序进行实现，程序中采用邻接矩阵表示一个有向图，输入为该图的邻接矩阵以及目的节点，输出为图中各点的邻接关系，依照次邻接关系可得到到达目的节点的最短路径。

程序用C语言编写，GCC环境编译，具体代码见附录。

四、运行结果及分析

选择一具有7个节点的有向图进行实验，其各边权重及拓扑结构如下所示：

图1 实验用图

选取节点1为目的节点,运行程序：

1。 输入表示该图的邻接矩阵，不相邻的节点间链路权值用-1表示，代表无穷大;

2。 输入目的节点编号； 3. 得到输出结果，如下图所示。

输出结果 图2 程序运行截图1

将输出结果用图表示为：

图3 到达目的节点1的最短路由

更改目的节点,选取目的节点为节点5,重新运行程序,得到结果如下：

目的节点更改为5 图4 程序运行截图2

输出结果用图表示为：

图5 到达目的节点5的最短路由

选择不同的目的节点,利用此程序均能得出正确的最短路径，证明了程序的正确性。达到了较好的效果。

附源代码：

＃include ＃include #define N 7 /＊节点个数*/ int main() {

double e[N］[N］，d[N]; int v； /*目的节点＊/ int i,j，min,x； long p=0；

int path[N］;

/*节点从0开始计数＊/ for(i=0；iprintf（”Input the weights to node ％

d\\n\"，i+1)；

for（j=0;j｛

scanf(”%lf”，&e［i]［j］）; /*

不相邻节点间边权用负数表示＊/

if（e［i]［j]〈0) e［i]［j］=32767；

｝

｝

printf（”Input destination node\\n”）; scanf(”％d\＆v）； /*输入目的节点＊/ v-=1； /＊初始化＊/ for（i=0;i〈N；i++） ｛

d［i］=e[i］[v];

path[i]=v;

}

p｜=1〈〈v； while（1) { min=32767;

for（j=0；j〈N;j++）

｛

if（p&(1〈continue；

if（min>d［j］)

｛ i=j;

min=d［j]; ｝

}

p｜=1<if（p>=(1<if(p＆（1〈d[i]+e［j］［i］） {

min=d［i]+e[j]［i]; x=i；

｝

if（d[j]>min） {

d[j]=min；

path［j]=x;

}

｝

}

printf（\"＊*＊result：*＊*\\n”)； for（i=0；i〈N；i++) ｛ if（i==v) continue;

printf(\"P%d-—>P％d\\n”，i+1,path[i］

+1); ｝

exit（EXIT_SUCCESS);

｝