开放最短路径优先协议(ospf)路径选择算法

1、课 程 设 计 说 明 书课程名称： 数据结构设计题目： 开放最短路径优先协议(ospf)路径选择算法 院 系： 计算机科学与信息工程系 学生姓名： 王振锋 学 号： 200803030022 专业班级： 网络一班 指导教师：2010 年 6 月 19 日课 程 设 计 任 务 书- 2 -开放最短路径优先协议(ospf)路径选择算法Dijkstra摘要：OSPF采用SPF（Shortest Path First）算法（也叫做Dijkstra算法），SPF算法是链路状态型算法，链路状态型算法对自己以及其它路由器产生的链路状态信息进行汇总，在本地生成一个链路状态数据库，来对此数据库进行运算，从而

2、得到一张以自己为根的、到达其它各目的节点最近的一张路径图，根据算法和协议特点，这张图是无环路的。本次课程设计是模拟最短路径优先协议(ospf)路径选择算法，使用邻接矩阵存储图的有关信息，用迪杰斯特拉(Dijkstra)算法得出最短路径，并附有弗洛伊德(Floyd)算法加以比较。另为了更好的对Dijkstra算法和Floyd算法有更好的理解在对其又做了改进-使其能生成多源结点到多结点的最短路径及相应的最短路径的权值。关键词：C语言 最短路径优先协议(ospf) 迪杰斯特拉（Dijkstra）弗洛伊德（Floyd） 最短路径 算法 图 邻接矩阵 最短路径长度 权值（cost）- 3 -目 录1.

3、课程设计背景 . 61.2课程设计要求 . 62.设计方案 . 82.1最短路径算法的分类 . 82.2 DIJKSTRA算法的基本原理 . 82.3 DIJKSTRA算法的步骤 . 93.方案实施 . 113.1实验程序的整体框架 . 113.2算法核心代码实现 . 113.2.1 Dijkstra算法的实现 . 113.2.2弗洛伊德（Floyd）算法实现 . 143.2.3邻接矩阵的的创建 . 154. 结果与结论 . 214.1设计内容 . 214.2课程设计程序源程序 . 214.3程序输出图 . 344.3.1程序主界面 . 344.3.2用迪杰斯特拉（Dijkstra）算法处理已

4、储存的路由图 . 354.3.3用Floyd算法处理已储存的路由图结果 . 36- 4 -4.3.4设计结果分析 . 374.3.5课程设计总结 . 375. 收获与致谢 . 376. 参考文献 . 387. 附 件 . 38- 5 -1. 课程设计背景1.1课程设计目的本次课程设计我门要在VC+环境的最短路径，常用得有Dijkstra算法和Floyd算法等，这次主要应用Dijkstra算法并附有Floyd算法加以比较完成课程设计。Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Di

5、jkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。Dijkstra算法是很有代表性的最短路算法，在很多专业课程中都作为基本内容有详细的介绍，如通信有原理，图论，运筹学等等。通过本次通过这次课程设计，我们要对上课所学得知识进行巩固，掌握图、子图、结点的度数、有向图、无向图、多重图、完全图、补图、生成子图、图的同构、路、回路、连通图、弱连通、强连通等概念及其性质；掌握图的矩阵表示，给定图的邻接矩阵会求任一结点的入度、出度和度数；一个结点到另一个结点长度为k的路径的条数；该图的可达性矩阵。对最小生成树、最短路径、Dijkstra算法，最短路由有了更深得理解。本次课程实验

6、，要了解最短得路由得算法，掌握Dijkstra算法，Floyd-Warshall算法等算法得概念，基本原理和思想。加深对数据结构这门课程的理解，并且在VC+环境下进行运行，得到输出结果图，并对图进行结果与分析。1.2课程设计要求根据所学数据结构基础知识，使用迪杰斯特拉（Dijkstra）算法，编写一C程序，它能根据读入得带权有向图G的数据，构造并输出图G的顶点Vi到其它每个顶点的最短路径及长度，并输出其最短路径。并附有弗洛伊德（Floyd）算法和迪杰斯特拉（Dijkstra）算法相比较，两算法有何不同？设计具体要求：实现以下几个功能：（1）、实现图的建立；（2）、用邻接矩阵存储图的信息；（3）

7、、用不同的算法实现在已建图中最短路径的选择（4）、输出最短路径的权值和相应的路径。- 6 -1.3运行环境该程序的运行环境为Windows XP系统，Microsoft Visual C+6.0版本。- 7 -2.设计方案2.1最短路径算法的分类所谓最短路径（shortest path）问题指的是：如果从图中某顶点出发（此点称为源点），经图的边到达另一顶点（称为终点）的路径不止一条，如何找到一条路径使沿此路径上各边的权值之和为最小。设一有向网络G =（V,E），已知各边的权值，并设每边的权均大于零，以某指定V0为源点，求从V0到图的其余各点的最短路径。用于解决最短路径问题的算法被称做“最短路径

8、算法”， 有时被简称作“路径算法”。 最常用的路径算法有： (1)Dijkstra算法(2)A*算法(3)SPFA算法(4)Bellman-Ford算法(5)Floyd-Warshall算法(6)Johnson算法2.2 Dijkstra算法的基本原理Dijkstra算法是由荷兰计算机科学家艾兹格·迪科斯彻发现的。算法解决的是有向图中最短路径问题。 举例来说，如果图中的顶点表示城市，而边上的权重表示著城市间开车行经的距离。 Dijkstra算法可以用来找到两个城市之间的最短路径。 这个算法是通过为每个顶点v保留目前为止所找到的从s到v的最短路径来工作的。 初始时，源点s的路径长度值被

9、赋为0（ds=0），同时把所有其他顶点的路径长度设为无穷大，即表示我们不知道任何通向这些顶点的路径（对于V中所有 顶点v除s外dv= ）。当算法结束时，dv中储存的便是从s到v的最短路径，或者如果路径不存在的话是无穷大。Dijstra算法的基础操作是边的拓展：如果存在一条从u到v的边，那么从s到u的最短路径可以通过将边(u,v)添加到尾部来拓展一条从s到v的路 径。这条路径的长度是du+w(u,v)。如果这个值比目前已知的dv的值要小，我们可以用新值来- 8 -替代当前dv中的值。拓展边的操作一直执行 到所有的dv都代表从s到v最短路径的花费。这个算法经过组织因而当du达到它最终的值的时候每条

10、边(u,v)都只被拓展一次。 算法维护两个顶点集S和Q。集合S保留了我们已知的所有dv的值已经是最短路径的值顶点，而集合Q则保留其他所有顶点。集合S初始状态为空，而后每一步 都有一个顶点从Q移动到S。这个被选择的顶点是Q中拥有最小的du值的顶点。当一个顶点u从Q中转移到了S中，算法对每条外接边(u,v)进行拓展。2.3 Dijkstra算法的步骤Dijkstra算法的基本思路是：假设每个点都有一对标号 (dj, pj)，其中dj是从起源点s到点j的最短路径的长度 (从顶点到其本身的最短路径是零路(没有弧的路)，其长度等于零)；pj则是从s到j的最短路径中j点的前一点。求解从起源点s到点j的最短

11、路径算法的基本过程如下：(1)初始化。起源点设置为： ds=0, ps为空;所有其他点: di=, pi=?;标记起源点s，记k=s,其他所有点设为未标记的。(2)检验从所有已标记的点k到其直接连接的未标记的点j的距离，并设置 lkj是从点k到j的直接连接距离。(3)选取下一个点。从所有未标记的结点中，选取dj 中最小的一个i：di=mindj, 所有未标记的点j点i就被选为最短路径中的一点，并设为已标记的。(4)找到点i的前一点。从已标记的点中找到直接连接到点i的点j*，作为前一点,设置：i=j*(5)标记点i。如果所有点已标记，则算法完全推出，否则记k=i，转到2) 再继续。具体流程图如图

12、1所示- 9 -图1 Dijkstra算法流程图- 10 -3.方案实施3.1实验程序的整体框架本次实验的具体结构框架安排如下：(1)“Dijkstra.h”模块此模块功能是实现Dijksta算法选择最短路径，用函数void ShortestPath_DIJ( Node a ,Status i ,Status v0 ,Status *D ,Status *pre )计算图a中所有顶点的最短路径，另外并用函数void Show(Status *D , Status *pre ,int i ,int v0)显示最短路径长度及相应的最短路径。(2).”Floyd.h”模块此模块的主要功能是实现Flo

13、yd算法选择最短路径，用函数void floyd1(Node g, int num,path &p,dist d)计算图g中所有顶点的最短路径，另外并用函数void output_pd(Node g,int num,path p,dist d)显示最短路径长度及相应的最短路径。(3).”main.cpp”模块此模块主要实现邻接矩阵的创建，从输入的图中提取信息并将其存储到创建的邻接矩阵中，并在此模块中用main()函数控制程序的运行及相关函数的调用。3.2算法核心代码实现3.2.1 Dijkstra算法的实现从上面可以看出，在按标记法实现Dijkstra算法的过程中，核心步骤就是从未标记

14、的点中选择一个权值最小的弧段。这是一个循环比较的过程，如果不采用任何技巧，未标记点将以无序的形式存放在一个链表或数组中。那么要选择一个权值最小的弧段就必须把所有的点都扫描一遍，在大数据量的情况下，这无疑是一个制约计算速度的瓶颈。要解决这个问题，最有效的做法就是将这些要扫描的点按其所在边的权值进行顺序排列，这样每循环一次即可取到符合条件的点，可大大提高算法的执行效率。另外，GIS中的数据 (如道路、管网、线路等)要进行最短路径的计- 11 -算，就必须首先将其按结点和边的关系抽象为图的结构，这在GIS中称为构建网络的拓扑关系 (由于这里的计算与面无关，所以拓扑关系中只记录了线与结点的关系而无线与

15、面的关系，是不完备的拓扑关系)。如果用一个矩阵来表示这个网络，不但所需空间巨大，而且效率会很低。下面主要就如何用一个简洁高效的结构表示网的拓扑关系以及快速搜索技术的实现进行讨论。网络在数学和计算机领域中被抽象为图，所以其基础是图的存储表示。一般而言，无向图可以用邻接矩阵和邻接多重表来表示，而有向图则可以用邻接表和十字链表示。图1带权有向图具体的实现代码如下：void ShortestPath_DIJ( Node a ,Status i ,Status v0 ,Status *D ,Status *pre )/a是传进的矩阵，i是结点数，v0是最短路径的源结点int v,w,j,l=1;Stat

16、us *final;/设置int 指针Status min;final=(Status *)malloc( sizeof(Status)*i );/分配空间for(v=0;v<i;v+)/初始化finalv=FALSE; prev=FALSE; Dv=av0v;- 12 - if(Dv<10000)/找到头结点 prev=v0;for(v=0;v<i;v+) if( av0v>=10000 ) l+;if(l>i)printf("n从路由%d出发没有最短路径到其他端点!n",v0+1); exit(0);/v0是一个孤立的顶点 Dv0=0;fi

17、nalv0=TRUE;for( j=0 ; j<i ; +j ) min=MaxNum; for( w=0 ; w<i ; w+) if( !finalw )/判断是否已被最短路径路过 if( Dw<min ) v=w; min=Dw; /找出最短的路径finalv=TRUE;- 13 -for( w=0 ; w<i ; w+ ) if( !finalw && ( (min+avw)<Dw) ) Dw=min+avw; prew=v;3.2.2弗洛伊德（Floyd）算法实现洛伊德算法仍然使用图的邻接矩阵arcsn+1n+1来存储带权有向图。算法的基

18、本思想是:设置一个n x n的矩阵A(k)，其中除对角线的元素都等于0外，其它元素a(k)ij表示顶点i到顶点j的路径长度，K表示运算步骤。开始时，以任意两个顶点之间的有向边的权值作为路径长度，没有有向边时，路径长度为，当K=0时, A (0)ij=arcsij，以后逐步尝试在原路径中加入其它顶点作为中间顶点，如果增加中间顶点后，得到的路径比原来的路径长度减少了，则以此新路径代替原路径，修改矩阵元素。具体代码如下：void floyd1(Node g, int num,path &p,dist d)long i,j,k,l,b;/*初始化*/for (i=0;i<num;i+)f

19、or (j=0;j<num;j+)dij=gij;if (i!=j && dij<FINITY ) /i与之间有路径可通- 14 - l=0; pijl+=i; pijl+=j; pijl+=-1; else pij0=-1;for (k=0;k<num;k+) /递推求解每一对顶点间的最短距离for (i=0;i<num;i+)for (j=0;j<num;j+)if (dij>dik+dkj)路pijl=pikl;/把i,k 间的路径赋给i,j间的路径 dij=dik+dkj;/刷新距离 for(l=0;pikl!=-1;l+)/pikl

20、!=-1表示i,k间有通for(b=1;pkjb!=-1;b+)pijl+=pkjb;/把k,j间的路径给i,j间的路径pijl=-1;/刷新路径3.2.3邻接矩阵的的创建 图的数组表示也称图的邻接矩阵存储，它的基本思想是，将图的顶点存放在一维数组里，我们称这个一维数组为顶点向量；用二维数组存储顶点之间的关系，这个二维数组即是邻接矩阵，邻接矩阵存储的是边或弧的信息。用邻接矩阵表示图的- 15 -优点是，容易判断任意两个顶点间是否有边或弧相连，并容易求得各个顶点的度。具体建立步骤如下：（1）声明结构typedef Status * Node;用以存放图的信息（2）用函数a=(Node) mall

21、oc( num * sizeof (Status *);开辟一个一维数组空间（3）用函数ai=(Status *) malloc( num * sizeof (Status);开辟一个二维数组的空间用以存放边的权值具体的实现函数如下（1）Node Build (Status num )函数储存自己建立的图的信息Node Build (Status num )int i,j,k;Node a;a=(Node) malloc( num * sizeof (Status *);printf("n请输入各路由边线的cost的权值 ，如果不存在真接连接请输入10000n");for(

22、i=0;i<num;i+)ai=(Status *) malloc( num * sizeof (Status);for(j=0;j<num;j+)aij=MaxNum;- 16 -for(i=0;i<num;i+)for(j=0;j<num;j+)if(i!=j) printf("请输入第%d个结点到第个%d结点到的权值",i+1,j+1);scanf("%d",&k); /*if( i>=num | j>=num ) printf("无效的输入!请重新输入!"); exit(1); */

23、 aij=k; else aij=10000;return a;- 17 -（2）用Node Build1 (Status num )函数建立邻接矩阵用以存放已建立图的信息Node Build1 (Status num )int i,j,k=0;Node a;a=(Node) malloc( num * sizeof (Status *);for(i=0;i<num;i+)ai=(Status *) malloc( num * sizeof (Status);for(j=0;j<num;j+)aij=MaxNum;a00=10000;a01=2; a02=3; a03=10000

24、; a04=10000 ; a05=10000; a06=10000 ;a10=2; a11=10000 ; a12=4 ; a13=5 ; a14=6 ; a15=10000 ; a16=10000 ;a20=3 ; a21=4 ; a22=10000 ; a23=10000 ; a24=10000 ; a25=4 ; a26=3 ;a30=10000 ; a31=5 ; a32=10000 ; a33=10000 ; a34=10000 ; a35=10000 ; a36=5 ;- 18 -a40=10000 ; a41=6 ; a42=10000; a43=10000; a44=1000

25、0 ; a45=7; a46=10000;a50=10000 ; a51=10000 ; a52=4; a53=10000 ; a54=7 ; a55=10000 ; a56=10000 ;a60=10000; a61=10000 ; a62=3 ; a63=5 ; a64=10000; a65=10000; a66=4 ;printf("已建立路由拓扑:n");for(i=0;i<6;i+)for(j=0;j<6;j+)if(i!=j)if(aij>=10000)printf("【%d】->【%d】无直连elseprintf("

26、【%d】->【%d】 = =%d ",i+1,j+1,aij); k+;if(k%4=0)printf("n");/if- 19 - ",i+1,j+1);/for /forprintf("n"); return a; /end- 20 -4. 结果与结论4.1设计内容Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。所以根据Dijkstra算法能得出最短路径的最优解。最短路径问题的求解还不止这一种算法，比如还有分枝定界

27、等等，而且大家也可以创造出各种各样的新算法来。不同的最短路径问题到底用哪种算法，以及还需要对该种算法作什么改动，是非常重要的，这种能力往往是很多同学所欠缺的，这需要大家在平常的训练中多做这类题目，还要多总结，以达到熟能生巧的境界。4.2课程设计程序源程序（1）”Dijkstra.h”文件程序#ifndef DIJKSTRA_H#define DIJKSTRA_H#include<stdio.h>#include<stdlib.h>typedef int Status;typedef Status * Node;/node指针的指针#define MaxNum 10000

28、;/设置10000为无穷#define FALSE 0;#define TRUE 1;/创建结点矩阵void ShortestPath_DIJ( Node a ,Status i ,Status v0 ,Status *D ,Status *pre )/a是传进的矩阵，i是结点数，v0是最短路径的源结点int v,w,j,l=1; Status *final;/设置int 指针- 21 -Status min; final=(Status *)malloc( sizeof(Status)*i );/分配空间 for(v=0;v<i;v+)/初始化 for(v=0;v<i;v+) i

29、f( av0v>=10000 ) finalv=FALSE; prev=FALSE; Dv=av0v; if(Dv<10000)/找到头结点 prev=v0; l+; if(l>i) printf("n从路由%d出发没有最短路径到其他端点!n",v0+1); exit(0); /v0是一个孤立的顶点 Dv0=0; finalv0=TRUE; for( j=0 ; j<i ; +j ) min=MaxNum; for( w=0 ; w<i ; w+) if( !finalw )/判断是否已被最短路径路过 if( Dw<min )- 22 -

30、 v=w; min=Dw; /找出最短的路径finalv=TRUE;void Show(Status *D , Status *pre ,int i ,int v0)/D是最短路径长度，PRE是最短路径经过的结点，I是结点数，V0是源结点int j,k,m,n; int *temp; temp=(int *)malloc(sizeof(int)*i); for(j=0;j<i;j+) if(j!=v0) printf("n路由【%d】到路由【%d】的最短路径长度为:%3d for( w=0 ; w<i ; w+ ) if( !finalw && ( (mi

31、n+avw)<Dw) ) Dw=min+avw; prew=v; " ,v0+1,j+1,Dj);n=j;- 23 -if(Dj!=10000)/判断是不是有可达路径 for(k=0;k<i;k+) if( k=0&&Dj!=10000&&Dj!=0 )/当是源点时 if( k!=0 &&Dj!=10000&&Dj!=0)/不是源点时 if(Dj=10000)/没有路径 if(Dj=0) - 24 - tempk=pren; if(tempk!=v0)/判断是不是源点自身 n=tempk; else /(te

32、mpk=v0)/是源点跳出 break; printf("路由【%d】->路由【%d】",v0+1,j+1); for(m=k;m>=0;m-) printf("路由【%d】",j+1); printf("路由【%d】->",tempm+1); printf("从路由【%d】出发没有最短路径到路由【%d】!",v0+1,j+1); printf("路由【%d】",v0); /printf("n");#endif（2）”floyd.h“文件代码#ifndef

33、FLOYD_H#define FLOYD_H#include <stdio.h>#include <stdlib.h>#include <string.h>#define FINITY 10000 /此处用此数表示无穷大typedef Status * Node;/node指针的指针#define MaxNum 10000;/设置10000为无穷#define FALSE 0;#define TRUE 1;#define m 50 /最大顶点数typedef int distmm; /* 距离向量类型*/typedef int pathmm40; /* 路径

34、类型*/*-Floyd所有顶点对间的最短路径算法-*/ void floyd1(Node g, int num,path &p,dist d)/*初始化*/for (i=0;i<num;i+)for (j=0;j<num;j+)- 25 - long i,j,k,l,b;dij=gij;if (i!=j && dij<FINITY ) /i与之间有路径可通 l=0; pijl+=i; pijl+=j; pijl+=-1; else pij0=-1;for (k=0;k<num;k+) /递推求解每一对顶点间的最短距离for (i=0;i<n

35、um;i+)for (j=0;j<num;j+)if (dij>dik+dkj) dij=dik+dkj;/刷新距离 for(l=0;pikl!=-1;l+)/pikl!=-1表示i,k间有通路 pijl=pikl;/把i,k 间的路径赋给i,j间的路径 for(b=1;pkjb!=-1;b+)pijl+=pkjb;/把k,j间的路径给i,j间的路径 pijl=-1;/刷新路径void output_pd(Node g,int num,path p,dist d)/*输出有向图的最短路径*/ long i,j,l; void PutString(char a); for(i=0;i

36、<num;i+) for(j=0;j<num;j+)- 26 - if(pij0=-1) printf("路由【%d】到路由【%d】的最短路径不存在,请从新输入。n",i,j); else printf("路由【%d】与路由【%d】之间的最短距离 break; 是 %dn",i+1,j+1,dij);printf("路由【%d】到路由【%d】的最短路径是：路由【%d】",i+1,j+1,i+1);#endif（3）”main.cpp”文件源代码#include<stdio.h>#include "Di

37、jkstra.h"#include "floyd.h"typedef int distmm; /* 距离向量类型*/typedef int pathmm40; /* 路径类型*/typedef Status * Node;/node指针的指针- 27 - for(l=1;pijl!=-1;l+) printf("->路由【%d】n",j+1); printf("->路由【%d】",pijl);#define MaxNum 10000;/设置10000为无穷#define FALSE 0;#define TRUE

38、1;/*自己建立邻接矩阵*Node Build (Status num )int i,j,k;Node a;a=(Node) malloc( num * sizeof (Status *);printf("n请输入各路由边线的cost的权值 ，如果不存在真接连接请输入10000n");for(i=0;i<num;i+)ai=(Status *) malloc( num * sizeof (Status); for(j=0;j<num;j+) aij=MaxNum; for(i=0;i<num;i+)for(j=0;j<num;j+) if(i!=j)

39、 printf("请输入第%d个结点到第个%d结点到的权值",i+1,j+1); scanf("%d",&k); /*if( i>=num | j>=num )- 28 -printf("无效的输入!请重新输入!");exit(1);*/aij=k;elseaij=10000;return a;/*储存已有的矩阵*Node Build1 (Status num )int i,j,k=0;Node a;a=(Node) malloc( num * sizeof (Status *);for(i=0;i<num;

40、i+)ai=(Status *) malloc( num * sizeof (Status);for(j=0;j<num;j+)aij=MaxNum;a00=10000;a01=2; a02=3; a03=10000 ; a04=10000 ; a05=10000; a06=10000 ;- 29 -a10=2; a11=10000 ; a12=4 ; a13=5 ; a14=6 ; a15=10000 ; a16=10000 ;a20=3 ; a21=4 ; a22=10000 ; a23=10000 ; a24=10000 ; a25=4 ; a26=3 ;a30=10000 ; a

41、31=5 ; a32=10000 ; a33=10000 ; a34=10000 ; a35=10000 ; a36=5 ;a40=10000 ; a41=6 ; a42=10000; a43=10000; a44=10000 ; a45=7; a46=10000;a50=10000 ; a51=10000 ; a52=4; a53=10000 ; a54=7 ; a55=10000 ; a56=10000 ;a60=10000; a61=10000 ; a62=3 ; a63=5 ; a64=10000; a65=10000; a66=4 ;printf("已建立路由拓扑:n&qu

42、ot;); for(i=0;i<6;i+) for(j=0;j<6;j+) if(i!=j) if(aij>=10000) printf("【%d】->【%d】无直连 ",i+1,j+1); else printf("【%d】->【%d】 = =%d ",i+1,j+1,aij); k+; if(k%4=0) printf("n"); /if /for- 30 -/for printf("n"); return a;/endvoid main()int i,v0,choice; int

43、 w; path p; /* 路径向量 */dist d; /* 最短路径向量 */Node a; Status *D,*pre; while(1) start1:printf("/*n");printf("* printf("n 请选择：n"); printf(" 1.自己制作路由拓补图nn"); printf(" 2.使用已做好的路由拓补图nn"); printf(" 3.退出!nn"); *nn");printf("请输入你的选择："); scanf

44、("%d",&choice); if(choice=3) break;- 31 -else if(choice>3|choice<0|choice%1!=0) switch(choice) case 1: printf("ERROR!请重新选择n"); goto start1;start:printf("请输入网络拓补中路由器总数:"); scanf("%d",&i); if(i<=0| i%1 !=0) /printf("input the arcs:");

45、/scanf("%d",&j); D=(Status *)malloc(sizeof(Status)*i);/用于存放最短路径长度 pre=(Status *)malloc(sizeof(Status)*i);/用于存放最短路径经过printf("你输入的路由器的个数有误，请重新输入n"); goto start; 的结点a=Build(i); /printf("please input the start node: "); /scanf("%d",&v0); /*if(v0>i) prin

46、tf("input errors!not excite this node!"); exit(1); */ break;- 32 -case 2: i=7; a=Build1(7); D=(Status *)malloc(sizeof(Status)*i);/用于存放最短路径长度 pre=(Status *)malloc(sizeof(Status)*i);/用于存放最短路径经过的结点/*printf("please input the start node: "); scanf("%d",&v0); if(v0>8)

47、printf("input errors!not excite this node!"); exit(1); */ break; /witchloop:printf("*n");printf("* printf(" 请选择算法：nn"); printf(" 1.选用Dijkstra.h算法。nn"); printf(" 2.选用Floyd算法。nn"); *n");printf("请选择："); scanf("%d",&choice); if(choice!=1&&choice!=2) printf("ERROR,please input againn");- 33 - goto loop; switch(choice) case 1: for(v0=1;v0<=i;v0+) break; ShortestPath_DIJ( a ,i ,v0-1 ,D , pre ); Show( D, pre, i, v0-1 ); case 2: printf("nn你是否还想再尝试一次?是请输入1,不想请输入0结束！nfloyd1