logo资料库

旅游导游系统问题课程设计.doc

发布时间：2022-06-03 发布人：admin 分类：说明书 资料大小：0.15M 资料格式：doc 举报 版权申诉
第1页 / 共14页
第2页 / 共14页
第3页 / 共14页
第4页 / 共14页
第5页 / 共14页
第6页 / 共14页
第7页 / 共14页
第8页 / 共14页
资料共14页，剩余部分请下载后查看
    一、问题描述：旅游导游系统问题 二、基本要求：假设一个旅游景区由 n 个不同的景点组成（有向网），并用带权邻接矩 阵表示，权值表示两个景点间的步行时间，试编写程序求任意两个景 点间的最短步行时间。 三、软件模块结构图： 图 的 邻 接 矩阵存储 结 果 显 示 主程序 迪 杰 斯 特 拉 算 法 求 最短路径 保存记录 退 出 四、程序设计思想 （1） 邻接矩阵 用两个数组分别存储数据元素（顶点）的信息和数据元素之间的关 系（边或弧）的信息。邻接矩阵 是表示顶点之间相邻关系的矩阵。设 G=（V，E）是具有 n 个顶点的图，顶点序号依次为 0,1,2,…..，n-1,则 G 的邻接矩阵是具有如下定义的 n 阶方阵 A： A[i][j]=1 对于有向图，∈E(G) 或 A[i][j]=0 其它 此时，邻接矩阵定义如下： Int adjmatrix=ARRAY[n][n]; 若 G 是网，则邻接矩阵可定义为： A[i][j]=Wi,j 若（vi,vj）或∈E(G) 或 A[i][j]=0 或∞ 其他
    此时，邻接矩阵定义如下： Int adjnetwork[n][n]; /*n 为顶点个数*/ 为了反映一个图的全面信息，可以采用以下结构： #define MAXV 100 typedef struct {int adj; int time; }AdjMatrix[MAXV][MAXV]; typedef struct { AdjMatrix arc; /*存储边的信息*/ /*存储步行时间*/ int vexnum,arcnum; /*结构体嵌套*/ /*定义顶点数和边数*/ } MGraph; /*************************************************************************/ 注：因本程序只用到邻接矩阵表示法，故邻接表、邻接多重表、十字链表介绍略。 （2） 图的最短路径 (2).1 从某个源点到其余各顶点的最短路径 先计论单源点的最短路径问题：给定带权有向图 D 和源点 v，求从 v 到 D 中其余各 顶占的最短路径。 例如，图 1-2 所示带权有向图 D1 中从 v0 到其余各顶点之间的确最短路径。 0 1 100 60 5 30 4 10 5 10 20 3 50 2 图 1-2 如下表 1-2 所示。从图中可见，从 v0 到 v3 有两条不同的路径：（v0,v2,v3）和(v0,v4,v3)，
    前者长度为 60，而后者长度为 50。因此，后者是从 v0 到 v3 的最短路径；而从 v0 到 v1 没有路径。 始点 V0 终点 v1 V2 V3 V4 V5 最短路径 无 (v0,v2) (v0,v4,v3) (v0,v4) (v0,v4,v3,v5) 表 1-2 路径长度 10 50 30 60 为求得这些路径迪杰斯特拉（Dijkstra）提出了一个按路径长度递增的次序产生最短路 径的算法。 首先，引进一个辅助向量 dist，它的每个分量 dist[i]表示当前所找到的从始点 v 到每个 终点 vi 的最短路径的长度。它的初态为：若从 v 到 vi 有弧，则 dist[i]为弧上的权值，否则 置 dist[i]为∞。显然，长度为 Dist[j]=Min{dist[i]|vi∈V} 的路径就是从 v 出发的长度最短的一条最短路径。此路径为(v,vj)。 那么，下一条长度次短的最短路径是哪一条呢？假设该次短路径的终点是 vk，则可 想而知，这条路径或者是(v,vk)，或者是(v,vj,vk)。它的长度或者是从 v 到 vk 的弧上的权值， 或者是 disti]和从 vj 到 vk 的弧上的权值之和。 一般情况下，假设 S 为已求得最短路径的终点的集合，则可证明：下一条最短路么（设 其终点为 x）或者是弧（v,x），或者是中间只经过 S 中的顶点而最后到达顶点 x 的路径。这 可用反证法来证明。假设此路径上有一个顶点不在 S 中，则说明存在一条终点不在 S 而长 度比此路径短的路径。 但是，这是不可能的。因为我们是按路径长度递增的次序来产生各最短路径的，故长 度比此路短的所有路径均已产生，它们的终点必定在 S 中，即假设不成立。 因此，在一般情况下，下一条长度次短的最短路径的长度必是 Dist [j]=Min{dist[i]|vi∈V-S} 其中，dist[i]或者是弧（v,vi）上的权值，或者是 dist[k]vi∈V-S 和弧(vk,vi)上的权值之和。 根据以上分析，可以得到如下描述的算法： （1） 假设用带权的邻接矩阵 cost 来表示带权有向图,cost[i,j]表示弧（vi,vj）上 的权值。若不存在，则置 cost[i,j]为∞。S 为已找到从 v 出发的最 短路径的终点的集合。它的初始状态为空集。那么，从 v 出发到图上其 余各顶点（终点）vi 可能达到的最短路径长度的初值为： dist[i]=cost[ORDINAL(V),i] vi∈V∈V
    （2） 选择 vj，使得 Dist[j]=Min{dist[i]|vi∈V-S∈V-S} Vj 就是当前求得的一条从 v 出发的最短路径的终点。令 S=S∪{j} （3） （4） 修改从 v 出发到集合 V-S 上任一顶点 vk 可达的最短路径长度。如果 则修改 dist[k]为 Dist[j]+cost[j,k]
    解决然这个问题的一个办法是：每次以一个顶点为源点，重复执行迪杰斯特拉算法 n 次。这样，便可求得每一对顶点之间的最短路径。总的执行时间为 O(n3)。 这里用弗洛伊德算法时间复杂度也是 O(n3)，但形式上简音些。 弗洛伊德算法仍从图的带权邻接矩阵 cost 出发，其基本思想是： 假设求从顶点 vi 到 vj 的最短路径。如果从 vi 到 vj 有弧，则从 vj 到 vj 存在一条长度为 cost[i,j]的路径，该路径不一定是最短路径，尚需进行 n 次试探。 首先考虑路径(vi,v1,vj)是否存在（即判别弧（vi,v1）和(v1,vj)是否存在）。如果存在，则 比较（vi,vj）和(vi,1,vj)的路径长度取长度较短者为从 vi 到 vj 的中间顶点的序号不大于是的 最短路径。 假如在路径上再增加一个顶点 v2，也就是说，如果（v1,……..v2）和（v2,…..vj）分别 是当前找到的中间顶点的序号不大于是 1 的最短路径，那么（vi,…v2,…,vj）就有可能是从 vi 到 vj 的中间顶点的序号不大于 2 的最短路径。将它和已经得到的从 vi 到 vj 中间顶点序号 不大于 1 的最短路径相比较，从中选出中间顶点的序号不大于 2 的最短路径之后，再增加一 个顶点 v3，继续进行试探，依次类推。在一般情况下，若（vi,…..vk）和（vk,….vj）分别 是从 vi 到 vk 和从 vk 到 vj 的中间顶点的序号不大于 k-1 的最短路径相比较，其长度较短者 便是从 vi 到 vj 的中间顶点的序号不大于 k 的最短路径。 这样，在经过 n 次比较后,最后求得的必是从 vi 到 vj 的最短路径，按此方法可以同时求 得各对顶点间的最短路径。（本程序没有使用弗洛伊德算法，故算法略） 六、程序流程图 开始 i <=G.arcnum 输入 m,n 输 入 i++ i=1 i <= G.vexnum
    j=1 j<= G.vexnum 输出 G.arc[i][j].adj j++ 输出回车 i++ While(1) 输入 v Dijkstra() i=1 i<= G.vexnum 初始化数组 i++
    s[v0]=1;path[v0]=0 ; i=1 i<= G.vexnum mindis=MAX j=1 j<= G.vexnum s[j]==0&&dist[j]
    G.arc[u][j].adj #include #define MAXV 100 #define MAX 32767 typedef struct /*存储边的信息*/ {int adj; int time; /*存储步行时间*/ }AdjMatrix[MAXV][MAXV]; typedef struct { AdjMatrix arc; int vexnum,arcnum; } MGraph; MGraph G; /*结构体嵌套*/ /*定义顶点数和边数*/
    分享到：
    赞 收藏

    相关推荐

    资料库

    行业

    共收录7266份资料，累计15个分类，关注成员有19位，主要包括：物流,旅游,餐饮零售,网络游戏,咨询,金融,电子政务,外包,教育,制造,医疗,嵌入式,互联网,交通,电信

    热门标签

    物流 旅游 餐饮零售 网络游戏 咨询 金融 电子政务 外包 教育 制造 医疗 嵌入式 互联网 交通 电信

    最新资料