Dijkstra算法模型设计与实现

Dijkstra算法模型设计与实现 一、Dijkstra算法概述 Dijkstra算法是一种点对多点的集中式最短路径算法，即寻找网络中其他所有节点到目的节点的最短路径。 Dijkstra算法通过对路径的长度进行迭代，从而计算出到达目的节点的最短路径。其基本思想是按照路径长度增加的顺序来寻找最短路径，显然有：到达目的节点 的最短路径中最短的肯定是节点的最近节点 所对应的单条链路，最短路径中下一个最短的肯定是节点 的下一个最近的邻节点所对应的单条链路，或者是通过前面选定的节点的最短的由两条链路组成的的路径，依次类推。 二、Dijkstra算法描述 设每个节点 标定的到达目的节点1的最短路径长度估计为 ，如果在迭代的过程中， 已变成一个确定的值，称节点 为永久标定的节点，这些永久标定的节点的集合用 表示。在算法的每一步中，在 以外的节点中，必定是选择与目的节点1最近的节点加入到集合 中。具体算法如下： 1. 初始化，即 ， ， ， 。（若 ，则 ）。 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 #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;id[j]) { i=j; min=d[j]; } } p|=1<=(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;iP%d\n",i+1,path[i]+1); } exit(EXIT_SUCCESS); }