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

课课 程程 设设 计计 说说 明明 书书 课程名称： 数据结构数据结构 设计题目： 开放最短路径优先协议开放最短路径优先协议(ospf)路径选择算路径选择算 法法 院 系： 计算机科学与信息工程系计算机科学与信息工程系 学生姓名： 王振锋王振锋 学 号： 200803030022 专业班级： 网络一班网络一班 指导教师： 李爱玲李爱玲 2010 年 6 月 19 日 - 2 - 课课 程程 设设 计计 任任 务务 书书 设计题目开放最短路径开放最短路径优优先先协议协议(ospf)路径路径选择选择算法算法 学生姓名王振锋王振锋所在院系 计算机科学与计算机科学与 信息工程系信息工程系 专业、年级、 班 0808 网络工程一班网络工程一班 设计要求：实现以下几个功能 1 1、实现图的建立；、实现图的建立； 2 2、用邻接矩阵存储图的信息；、用邻接矩阵存储图的信息； 3 3、用不同的算法实现在已建图中最短路径的选择；、用不同的算法实现在已建图中最短路径的选择； 4 4、输出最短路径的权值和相应的路径。、输出最短路径的权值和相应的路径。 学生应完成的工作： （1 1）根据课程设计要求，分析思路并构建模型，划分子模块、完善其功能；根据课程设计要求，分析思路并构建模型，划分子模块、完善其功能； （2 2）根据各模块的功能设计并编写程序段、连接各程序段使之形成一个有机的整体；根据各模块的功能设计并编写程序段、连接各程序段使之形成一个有机的整体； （3 3）调试、运行程序进而得到正确的结果；调试、运行程序进而得到正确的结果； （4） 根据实验设计运行过程，写出实验论文并总结实验教训。根据实验设计运行过程，写出实验论文并总结实验教训。 参考文献阅读： 数据结构程序设计（苏仕华等，机械工业出版社）数据结构程序设计（苏仕华等，机械工业出版社） ； 数据结构（吴伟民等数据结构（吴伟民等 c c 语言版，清华大学出版社）语言版，清华大学出版社） ； C+C+程序设计导学程序设计导学 （李春葆等（李春葆等 清华大学出版社）清华大学出版社）; ; TCP/IP 协议原理与应用协议原理与应用(第第 3 版版) 查普尔查普尔(Laura A.Chappell) (美国美国)蒂特尔蒂特尔(Ed Title) 译者译者:张长富张长富 出版社出版社:清华大学出版社清华大学出版社 TCP/IPTCP/IP 协议详解（三卷本）协议详解（三卷本）(W.Richard(W.Richard Stevens).Stevens). 工作计划：（1 1）2010.6.72010.6.7 9 9 分析课程题目设计要求，构建模型，划分子模块进行分工合作；分析课程题目设计要求，构建模型，划分子模块进行分工合作； （2 2）2010.6.102010.6.10 1313 根据设计要求和模块写出各部分相应的程序代码；根据设计要求和模块写出各部分相应的程序代码； （3 3）2010.6.142010.6.14 1515 组合并调试程序，得到相应的实验结果；组合并调试程序，得到相应的实验结果； （4 4）2010.6.162010.6.16 -19-19 根据设计过程写出实验论文并总结根据设计过程写出实验论文并总结 任务下达日期： 2010 年 6 月 5 日 任务完成日期： 2010 年 6 月 5 日 指导教师（签名）： 学生（签名）： - 3 - 开放最短路径开放最短路径优优先先协议协议(ospf)路径路径 选择选择算法算法Dijkstra 摘要：摘要： OSPF 采用采用 SPF（Shortest Path First）算法（也叫做）算法（也叫做 Dijkstra 算法）算法） ，SPF 算算 法是链路状态型算法，链路状态型算法对自己以及其它路由器产生的链路状态信息法是链路状态型算法，链路状态型算法对自己以及其它路由器产生的链路状态信息 进行汇总，在本地生成一个链路状态数据库，来对此数据库进行运算，从而得到一进行汇总，在本地生成一个链路状态数据库，来对此数据库进行运算，从而得到一 张以自己为根的、到达其它各目的节点最近的一张路径图，根据算法和协议特点，张以自己为根的、到达其它各目的节点最近的一张路径图，根据算法和协议特点， 这张图是无环路的。这张图是无环路的。 本次课程设计是模拟最短路径优先协议本次课程设计是模拟最短路径优先协议(ospf)(ospf)路径选择算法，使用邻接矩阵路径选择算法，使用邻接矩阵 存储图的有关信息，用迪杰斯特拉存储图的有关信息，用迪杰斯特拉(Dijkstra)(Dijkstra)算法得出最短路径，并附有弗洛伊德算法得出最短路径，并附有弗洛伊德 (Floyd)(Floyd)算法加以比较。另为了更好的对算法加以比较。另为了更好的对 DijkstraDijkstra 算法和算法和 FloydFloyd 算法有更好的理解算法有更好的理解 在对其又做了改进在对其又做了改进-使其能生成多源结点到多结点的最短路径及相应的最短路使其能生成多源结点到多结点的最短路径及相应的最短路 径的权值。径的权值。 关键词：关键词： C C 语言语言 最短路径优先协议最短路径优先协议(ospf)(ospf) 迪杰斯特拉（迪杰斯特拉（Dijkstra） 弗洛伊德（弗洛伊德（FloydFloyd） 最短路径最短路径 算法算法 图图 邻接矩阵邻接矩阵 最短路径长度最短路径长度 权值（权值（costcost） - 4 - 目目 录录 1. 课程设计背景.6 1.2 课程设计要求.6 2.设计方案.8 2.1 最短路径算法的分类.8 2.2 DIJKSTRA算法的基本原理.8 2.3 DIJKSTRA算法的步骤 .9 3.方案实施.11 3.1 实验程序的整体框架.11 3.2 算法核心代码实现.11 3.2.1 Dijkstra 算法的实现.11 3.2.2 弗洛伊德（Floyd）算法实现.14 3.2.3 邻接矩阵的的创建.15 4. 结果与结论.21 4.1 设计内容.21 4.2 课程设计程序源程序.21 4.3 程序输出图.34 4.3.1 程序主界面.34 4.3.2 用迪杰斯特拉（Dijkstra）算法处理已储存的路由图.35 4.3.3 用 Floyd 算法处理已储存的路由图结果.36 - 5 - 4.3.4 设计结果分析.37 4.3.5 课程设计总结.37 5. 收获与致谢.37 6. 参考文献.38 7. 附 件.38 - 6 - 1.1. 课程设计背景课程设计背景 1.11.1 课程设计目的课程设计目的 本次课程设计我门要在 VC+环境的最短路径，常用得有 Dijkstra 算法和 Floyd 算法等，这次主要应用 Dijkstra 算法并附有 Floyd 算法加以比较完成课程 设计。Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法，用于计算一个节 点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到 扩展到终点为止。Dijkstra 算法能得出最短路径的最优解，但由于它遍历计算的 节点很多，所以效率低。Dijkstra 算法是很有代表性的最短路算法，在很多专业 课程中都作为基本内容有详细的介绍，如通信有原理，图论，运筹学等等。 通过本次通过这次课程设计，我们要对上课所学得知识进行巩固，掌握图、 子图、结点的度数、有向图、无向图、多重图、完全图、补图、生成子图、图的 同构、路、回路、连通图、弱连通、强连通等概念及其性质；掌握图的矩阵表示， 给定图的邻接矩阵会求任一结点的入度、出度和度数；一个结点到另一个结点长 度为 k 的路径的条数；该图的可达性矩阵。 对最小生成树、最短路径、Dijkstra 算法，最短路由有了更深得理解。本次 课程实验，要了解最短得路由得算法，掌握 Dijkstra 算法，Floyd-Warshall 算 法等算法得概念，基本原理和思想。加深对数据结构这门课程的理解，并且在 VC+环境下进行运行，得到输出结果图，并对图进行结果与分析。 1.21.2 课程设计要求课程设计要求 根据所学数据结构基础知识，使用迪杰斯特拉（DijkstraDijkstra）算法，编写一 C 程序，它能根据读入得带权有向图 G 的数据，构造并输出图 G 的顶点 Vi 到其它每 个顶点的最短路径及长度，并输出其最短路径。并附有弗洛伊德（Floyd）算法和 迪杰斯特拉（DijkstraDijkstra）算法相比较，两算法有何不同？ 设计具体要求：实现以下几个功能： （1） 、实现图的建立； （2） 、用邻接矩阵存储图的信息； （3） 、用不同的算法实现在已建图中最短路径的选择 （4） 、输出最短路径的权值和相应的路径。 - 7 - 1.31.3 运行环境运行环境 该程序的运行环境为 Windows XP 系统，Microsoft Visual C+6.0 版本。 - 8 - 2.2.设计方案设计方案 2.12.1 最短路径算法的分类最短路径算法的分类 所谓最短路径（shortest path）问题指的是：如果从图中某顶点出发（此 点称为源点），经图的边到达另一顶点（称为终点）的路径不止一条，如何找到一 条路径使沿此路径上各边的权值之和为最小。设一有向网络 G =（V,E），已知各 边的权值，并设每边的权均大于零，以某指定 V0 为源点，求从 V0 到图的其余各点 的最短路径。用于解决最短路径问题的算法被称做“最短路径算法”， 有时被简 称作“路径算法”。 最常用的路径算法有： (1)Dijkstra 算法 (2)A*算法 (3)SPFA 算法 (4)Bellman-Ford 算法 (5)Floyd-Warshall 算法 (6)Johnson 算法 2.2 Dijkstra 算法的基本原理算法的基本原理 Dijkstra 算法是由荷兰计算机科学家艾兹格迪科斯彻发现的。算法解决的是 有向图中最短路径问题。 举例来说，如果图中的顶点表示城市，而边上的权重表 示著城市间开车行经的距离。 Dijkstra 算法可以用来找到两个城市之间的最短路径。 这个算法是通过为每个顶点 v 保留目前为止所找到的从 s 到 v 的最短路径来工作 的。 初始时，源点 s 的路径长度值被赋为 0（ds=0），同时把所有其他顶点的路 径长度设为无穷大，即表示我们不知道任何通向这些顶点的路径（对于 V 中所有 顶点 v 除 s 外 dv= ）。当算法结束时，dv中储存的便是从 s 到 v 的最短路径， 或者如果路径不存在的话是无穷大。 Dijstra 算法的基础操作是边的拓展：如果存在一条从 u 到 v 的边，那么从 s 到 u 的最短路径可以通过将边(u,v)添加到尾部来拓展一条从 s 到 v 的路 径。这条 路径的长度是 du+w(u,v)。如果这个值比目前已知的 dv的值要小，我们可以用新 - 9 - 值来替代当前 dv中的值。拓展边的操作一直执行 到所有的 dv都代表从 s 到 v 最短路径的花费。这个算法经过组织因而当 du达到它最终的值的时候每条边(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 的最短路径算法的基本过程如下： (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) 再继 续。 具体流程图如图 1 所示 - 10 - 图图 1 1 DijkstraDijkstra 算法流程图算法流程图 - 11 - 3.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”模块 此模块的主要功能是实现 Floyd 算法选择最短路径，用函数 void floyd1(Node g, int num,path Status *final;/设置 int 指针 Status min; final=(Status *)malloc( sizeof(Status)*i );/分配空间 for(v=0;vi;v+)/初始化 finalv=FALSE; prev=FALSE; Dv=av0v; - 13 - if(Dvi) printf(n 从路由%d 出发没有最短路径到其他端点!n,v0+1); exit(0); /v0 是一个孤立的顶点 Dv0=0; finalv0=TRUE; for( j=0 ; ji ; +j ) min=MaxNum; for( w=0 ; wi ; w+) if( !finalw )/判断是否已被最短路径路过 if( Dwmin ) v=w; min=Dw; /找出最短的路径 finalv=TRUE; - 14 - for( w=0 ; wi ; w+ ) if( !finalw prew=v; 3.2.2 弗洛伊德（弗洛伊德（FloydFloyd）算法实现）算法实现 洛伊德算法仍然使用图的邻接矩阵 arcsn+1n+1来存储带权有向图。算法的 基本思想是:设置一个 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 /*初始化*/ for (i=0;inum;i+) for (j=0;jnum;j+) dij=gij; if (i!=j pijl+=i; pijl+=j; pijl+=-1; else pij0=-1; for (k=0;knum;k+) /递推求解每一对顶点间的最短距离 for (i=0;inum;i+) for (j=0;jdik+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;/刷新路径 3.2.33.2.3 邻接矩阵的的创建邻接矩阵的的创建 图的数组表示也称图的邻接矩阵存储，它的基本思想是，将图的顶点存放在一 维数组里，我们称这个一维数组为顶点向量；用二维数组存储顶点之间的关系，这 个二维数组即是邻接矩阵，邻接矩阵存储的是边或弧的信息。用邻接矩阵表示图的 - 16 - 优点是，容易判断任意两个顶点间是否有边或弧相连，并容易求得各个顶点的度。 具体建立步骤如下： （1）声明结构 typedef Status * Node;用以存放图的信息 （2）用函数 a=(Node) malloc( 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(i=0;inum;i+) ai=(Status *) malloc( num * sizeof (Status); for(j=0;jnum;j+) aij=MaxNum; - 17 - for(i=0;i=num ) printf(无效的输入!请重新输入!); exit(1); */ aij=k; else aij=10000; return a; - 18 - （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;inum;i+) ai=(Status *) malloc( num * sizeof (Status); for(j=0;jnum;j+) aij=MaxNum; a00=10000;a01=2; a02=3; a03=10000 ; 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 ; - 19 - 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); for(i=0;i【%d】无直连 ,i+1,j+1); else printf(【%d】-【%d】 = =%d ,i+1,j+1,aij); k+; if(k%4=0) printf(n); /if - 20 - /for /for printf(n); return a; /end - 21 - 4. 结果与结论 4.1 设计内容设计内容 Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法，用于计算一个节点到其 他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展 到终点为止。所以根据 Dijkstra 算法能得出最短路径的最优解。 最短路径问题的求解还不止这一种算法，比如还有分枝定界等等，而且大家也 可以创造出各种各样的新算法来。不同的最短路径问题到底用哪种算法，以及还需 要对该种算法作什么改动，是非常重要的，这种能力往往是很多同学所欠缺的，这 需要大家在平常的训练中多做这类题目，还要多总结，以达到熟能生巧的境界。 4.2 课程设计程序源程序课程设计程序源程序 （1 1） ”Dijkstra.h”Dijkstra.h”文件程序文件程序 #ifndef DIJKSTRA_H #define DIJKSTRA_H #include #include typedef int Status; typedef Status * Node;/node 指针的指针 #define MaxNum 10000;/设置 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 指针 - 22 - Status min; final=(Status *)malloc( sizeof(Status)*i );/分配空间 for(v=0;vi;v+)/初始化 finalv=FALSE; prev=FALSE; Dv=av0v; if(Dvi) printf(n 从路由%d 出发没有最短路径到其他端点!n,v0+1); exit(0); /v0 是一个孤立的顶点 Dv0=0; finalv0=TRUE; for( j=0 ; ji ; +j ) min=MaxNum; for( w=0 ; wi ; w+) if( !finalw )/判断是否已被最短路径路过 if( Dwmin ) - 23 - v=w; min=Dw; /找出最短的路径 finalv=TRUE; for( w=0 ; wi ; w+ ) if( !finalw prew=v; 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=0;m-) printf(路由【%d】-,tempm+1); printf(路由【%d】,j+1); if(Dj=10000)/没有路径 printf(从路由【%d】出发没有最短路径到路由【%d】! ,v0+1,j+1); if(Dj=0) printf(路由【%d】,v0); - 25 - /printf(n); #endif （2） ”floyd.h“”floyd.h“文件代码文件代码 #ifndef FLOYD_H #define FLOYD_H #include #include #include #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; /* 路径类型*/ /*-Floyd 所有顶点对间的最短路径算法-*/ void floyd1(Node g, int num,path /*初始化*/ for (i=0;inum;i+) for (j=0;jnum;j+) - 26 - dij=gij; if (i!=j pijl+=i; pijl+=j; pijl+=-1; else pij0=-1; for (k=0;knum;k+) /递推求解每一对顶点间的最短距离 for (i=0;inum;i+) for (j=0;jdik+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路由【%d】n,j+1); #endif （3） ”main.cpp”文件源代码 #include #include Dijkstra.h #include floyd.h typedef int distmm; /* 距离向量类型*/ typedef int pathmm40; /* 路径类型*/ - 28 - typedef Status * Node;/node 指针的指针 #define MaxNum 10000;/设置 10000 为无穷 #define FALSE 0; #define TRUE 1; /*自己建立邻接矩阵* Node Build (Status num ) int i,j,k; Node a; a=(Node) malloc( num * sizeof (Status *); printf(n 请输入各路由边线的 cost 的权值 ，如果不存在真接连接请输入 10000n); for(i=0;inum;i+) ai=(Status *) malloc( num * sizeof (Status); for(j=0;jnum;j+) aij=MaxNum; for(i=0;i=num ) printf(无效的输入!请重新输入!); exit(1); */ aij=k; else aij=10000; return a; /*储存已有的矩阵* Node Build1 (Status num ) int i,j,k=0; Node a; a=(Node) malloc( num * sizeof (Status *); for(i=0;inum;i+) ai=(Status *) malloc( num * sizeof (Status); for(j=0;jnum;j+) aij=MaxNum; a00=10000;a01=2; a02=3; a03=10000 ; a04=10000 ; - 30 - 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 ; 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); for(i=0;i【%d】无直连 ,i+1,j+1); else printf(【%d】-【%d】 = =%d ,i+1,j+1,aij); k+; if(k%4=0) printf(n); /if - 31 - /for /for printf(n); return a; /end void main() int i,v0,choice; int w; path p; /* 路径向量 */ dist d; /* 最短路径向量 */ Node a; Status *D,*pre; while(1) start1: printf(/* *n); printf(n 请选择：n); printf( 1.自己制作路由拓补图nn); printf( 2.使用已做好的路由拓补图nn); printf( 3.退出!nn); printf(* *nn); printf(请输入你的选择：); scanf(%d, if(choice=3) - 32 - break; else if(choice3|choice8) printf(input errors!not excite this node!); exit(1); */ break; /witch loop: printf(* *n); printf( 请选择算法：nn); printf( 1.选用 Dijkstra.h 算法。nn); printf( 2.选用 Floyd 算法。nn); printf(* *n); printf(请选择：); scanf(%d, if(choice!=1 goto loop; switch(choice) case 1: for(v0=1;v0=i;v0+) ShortestPath_DIJ( a ,i ,v0-1 ,D , pre ); Show( D, pre, i, v0-1 ); break; case 2: floyd1(a,i,p,d); output_pd(a,i,p,d); break; printf(nn 你是否还想再尝试一次?是请输入 1,不想请输入 0 结束！n 请选择：); scanf(%d, if(w!=1) break; /while 4.3 程序输出图程序输出图 - 35 - 4.3.1 程序主界面程序主界面 4.3.24.3.2 用迪杰斯特拉（用迪杰斯特拉（DijkstraDijkstra）算法处理已储存的路由图）算法处理已储存的路由图 （1 1）已储存的路由图结构如下）已储存的路由图结构如下 V1 V2