基于最短路径的旅游咨询网站的设计与应用!.pdfVIP

山西电子技术 应用实践 2017年第2期 文章编号：1674—4578(2017)02—0045-04 基于最短路径的旅游咨询网站的设计与应用 董妍汝 (山西大学商务学院信息学院，山西太原030031) 摘要：为了满足旅行者和旅行社对旅游景点最短路径查询的需求，采用Dijkstra算法实现了 四种基本查询方式，满足用户对旅游景点间的最优路径查找，并设计了基于最短路径的旅游咨询网 站。文中首先对所采用的算法进行了简单介绍，然后以山西省的旅游景点为例对网站的查询功能 进行了详细阐述，最后对采用Dijkstra算法后的路径选择性能进行分析。 关键词：最短路径；Dijkstra算法；旅游咨询 中图分类号：TP393文献标识码：A 随着生活节奏的加速和能源的紧缺，无论是对 2．1网站功能的设计 与旅行者还是旅行社而言，旅游路线都是其关注的 该网站主要功能是为用户提供山西省各地区风 重中之重。对于旅行者而言，希望在旅行中能够以 景名胜详细介绍的同时，为网站用户提供最短路径 最小的时间成本和金钱成本满足最大化的消费需 查询，主要包括以下查询方式： 求；对旅行社而言，期望满足客户的同时尽可能地降 1)用户输入起点，可以显示起点到山西各旅游 低成本，从而提高其效益…。因此，本文采用最短 景点的最短旅游线路，供用户对比选择。 路径算法设计并实现旅游咨询网站，将旅游景点之 2)用户输入起点、终点，可以显示这两地之间 间的路线进行定量的分析，使旅行者和旅行社得到 的最短旅游线路。 相对合适的旅游路线，从而合理的安排旅游行程，满 3)用户输入起点、意向旅游的若干景点，可以 足各自的需求。 为用户提供一条包含这些景点的最短旅游线路。 4)用户输入起点、意向旅游的景点、终点，为用 1最短路径算法 户规划一条从起点到终点并途经用户意向旅游景点 考虑到为用户提供最优路径能节省用户的旅行 的最短路线。 时间和经费，也能够间接地节省能源，本文采用经典 以上查询方式不仅实现了任意两个旅游景点间 的Dijkstra算法获取景点问的最短路径旧1。Dijkstra 的最短旅游路线查询，对多个特定旅游景点间的最 算法是贪婪法应用的一个例子，主要用来解决单个 短路径也可进行查询，实现了路径的智能查询HJ。 源点到其它顶点的最短路径。 2．2旅游景点最短路径的算法 Dijkstra算法按照路径“长度”递增的次序产生 以云冈石窟，悬空寺，应县木塔，五台山，晋祠， 最短路径∞j。该算法将图G(V，E)中的顶点分成两 平遥古城这六个旅游景点为例进行各种最短路径的 个集合VA、VB，如果源点S到某一个顶点的最短路 径已经确定，则该顶点属于VA，反之，则属于VB。 初始时，VA中只有源点s，其余的顶点均在VB中，表示这六个旅游景点，即云冈石窟V。，悬空寺V，， 应县木塔V2，五台山V3，晋祠V4，平遥古城V5。根 算法结束时，源点可以直接或间接到达的顶点均属