Dijkstra最短路径算法在超市选址中应用及代码实现.docVIP

Dijkstra最短路径算法在超市选址中应用及代码实现 　　摘 要：图论中的最短路径问题可以解决超市选址等很多实际问题。超市选址的正确与否，直接影响着超市的长期效益和发展前途。本文应用Dijkstra最短路径算法的分析，解决超市的选址问题。 　　关键词：Dijkstra算法；最短路径；超市。 　　中图分类号：F717.6 　　1.背景意义 　　1.1 图论概述 　　图是一种数据结构。在图中的数据元素通常称做顶点（Vertex），V是顶点的有穷非空集合；VR是两个顶点之间的关系的集合。 ，则 表示从v到w的一条弧（Arc），且称v为弧尾或初始端点，称w为弧头或终端点，此时的图为有向图。在有向图中，称顶点v作为边的始点的次数之和为v的出度，称v作为边的终点的次数之和为v的出度。如果图G中任意一条边 上都附有一个数w，则称这样的图G无赋权图，称w为边 上的权。带权有向图，路径上第一个顶点为源点，最后一个顶点为终点。1.2 超市选址最优的意义 　　超市选址在现在社会具有其独特的吸引力。 　　（1）选址具有长期性和稳定性，一经确定就不可轻易改变。这是一项长期性的投资，是不可随着外部环境的变化而随时调整的因素，所以，地址选择的好坏直接影响超市未来的发展前景。 　　（2）选址从来都不是一件轻易可决定的事情，“天时”、“地利”、“人和”三个因素是商家最看中的。可见，选址占绝对优势才可以最大限度地吸引附近的顾客，是影响超市未来经济效益的不可忽视的一大因素。尤其是在现在这个超市遍地开花的时代，超市选址的影响力已经越来越大了。 　　（3）选址是超市制定经营理念的重要依据。超市的选址决定了超市在该地区的经营目标和经营战略，需按照顾客的构成及需求确定最终的促销策略。 　　2.需求分析 　　2.1 可行性分析 　　2.1.1经济可行性分析 　　作为超市这样商业性质的场所，经济持续增长就是其最终目的，经济效益便是其得以生存的全部。 　　2.1.2技术可行性分析 　　技术可行性分析主要分析现有技术条件能否顺利完成开发工作，硬件、软件配置能否满足开发者的需要，各类技术人员的数量，水平，来源等。超市选址问题主要是解决超市在建筑???前地理位置的选址，能否使其附近单位到其的路径最短，超市的效益达到最优。 　　最短路径这样的问题刚好可以用Dijkstra算法得以解决问题。发挥计算机的信息传输速度快、准确度高的优势。计算机硬件和软件技术的飞速发展，为系统的建设提供了技术条件。 　　2.1.3社会可行性分析 　　社会可行性有时也称为操作可行性，主要论证新系统在超市开发和运行的可能性以及运行后可能一起的对超市的影响，即组织内外是否具备接受和使用新系统的条件。避免超市因选址不佳而导致倒闭的现象发生。 　　2.2系统功能需求 　　（1）数据模型（逻辑结构）：带权有向图（权值=距离*人数*相对频率）。 　　（2）核心算法： Dijkstra算法（迪杰斯特拉算法）。（3）开发平台：C-Free 5.0 　　（4）开发语言：C/C++（5）操作系统：Windows 7（6）运行环境：C-Free 5.0或Microsoft Visual C++ 6.0（7）核心问题：求最短路径（超市选址要求超市到各个单位的权值之和最小）。 　　总体思路：如果超市选在某个源点，先用 Dijkstra算法求出从该源点到其余各顶点的最短路径。并且用户只需输入一次数据，便可将所有数据保存在文件中，方便下次使用。系统可以输出有向图的十字链表构造和邻接矩阵，便于验证图的构造是否正确。3.最短路径问题 　　最短路径问题是图论中的一个典范问题。在带权有向图中， 每条边都有一个权值，找出两节点之间总权和最小的路径就是最短路径问题。 　　最短路径问题通常有两类：一类是求取从某一源点到其余各点的最短路径即单源最短路径，包括确定起点的最短路径问题和确定终点的最短路径问题；另一类是求取每一对顶点之间的最短路径。 　　4.Dijkstra算法 　　Dijkstra算法是一个按路径长度递增的次序产生最短路径的算法。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。该算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。算法本身并不是按照我们的思维习惯――求解从原点到第一个点的最短路径，再到第二个点的最短路径，直至最后求解完成到第n个点的最短路径。 　　首先，需要引入一个辅助向量D，它的每个分量D[i]表示当前所找到的从始点v到每个终点 的最短路径的长度。它的初态为：若从v到 有弧，则D[i]为弧上的权值；否则置D[i]为∞。迪杰斯特拉算法的描述如下所示： 　　（1）假设用带权的邻接矩阵arcs来表示带权有向图，arcs[i][j]表示弧 上的权