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-Free5.0

（4）开发语言：C/C++（5）操作系统：Windows7（6）运行环境：C-Free5.0或MicrosoftVisualC++6.0（7）核心问题：求最短路径（超市选址要求超市到各个单位的权值之和最小）.

总体思路：如果超市选在某个源点,先用Dijkstra算法求出从该源点到其余各顶点的最短路径.并且用户只需输入一次数据,便可将所有数据保存在文件中,方便下次使用.系统可以输出有向图的十字链表构造和邻接矩阵,便于验证图的构造是否正确.3.最短路径问题

最短路径问题是图论中的一个典范问题.在带权有向图中,每条边都有一个权值,找出两节点之间总权和最小的路径就是最短路径问题.

最短路径问题通常有两类：一类是求取从某一源点到其余各点的最短路径即单源最短路径,包括确定起点的最短路径问题和确定终点的最短路径问题；另一类是求取每一对顶点之间的最短路径.

4.Dijkstra算法

Dijkstra算法是一个按路径长度递增的次序产生最短路径的算法.主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止.该算法能得出最短路径的最优解,但由于它遍历计算的节点很多,所以效率低.算法本身并不是按照我们的思维习惯――求解从原点到第一个点的最短路径,再到第二个点的最短路径,直至最后求解完成到第n个点的最短路径.

首先,需要引入一个辅助向量D,它的每个分量D[i]表示当前所找到的从始点v到每个终点的最短路径的长度.它的初态为：若从v到有弧,则D[i]为弧上的权值；否则置D[i]为∞.迪杰斯特拉算法的描述如下所示：

（1）检测设用带权的邻接矩阵arcs来表示带权有向图,arcs[i][j]表示弧上的权值.若不存在,则置arcs[i][j]为∞（在计算机上可用允许的最大值代替）.S为已找到从v出发的最短路径的重点的集合,它的初始状态为空集.那么从v出发到图上其余各顶点（终点）可能达到的最短路径长度的初值为：

D[i]等于arcs[LocateVex（G,v）[i]

（2）选择,使得

就是当前求得的一条从v出发的最短路径的终点.令

（3）修改从v出发到集合上的任一顶点可达到的最短路径长度.如果

则修改D[k]为

（4）重复操作（2）、（3）共n-1次.由此求得从v到图上其余个顶点的最短路径是依路径长度递增的序列.

Dijkstra算法的流程图如图2-2所示.

5.Dijkstra算法在超市选址中的应用

5.1问题描述某城市的开发区要建立一个大型超市,该开发区的示意图如图1所示,其中A,B,C,D,等,H表示开发区中8个重点消费单位.考虑到交通路况,部分单位之间往返的距离不完全相同,分析超市选址问题.其中各个单位的人去超市的相对频率（每周去超市的次数）如下所示：A地区和D地区是1,B地区和F地区是3,其他地区均是2.

图1开发区示意图

超市选址应该综合考虑到达各单位的距离、各单位人数及客户去超市的相对频率这三方面,尽可能权值小的原则为最好.

5.2系统架构设计

采用十字链表存储结构表示,构造有向图G,用邻接矩阵来存储图.

在十字链表中,对应于有向图中的每一条弧有一个结点,对应于每个顶点也有一个结点.这些结点的结构图2所示.

弧结点：

顶点结点：

图2弧结点及顶点结点的结构

弧结点由四个域组成：

tailvex域：尾域,指示弧尾顶点在图中的位置；headvex域：头域,指示弧头顶点在图中的位置；hlink域：指向弧头相同的下一条弧；tlink域：指向弧尾相同的下一条弧.顶点结点由三个域组成：data域：存储和顶点的名称；firstin域：指向以该顶点为弧头的第一个弧结点；firstout域：指向以该顶点为弧尾的第一个弧结点.

以二维数组表示有n个顶点的图时,需存放n个顶点的信息和个弧信息的存储量.

6.结论

通过运行系统可以得到各个源点到其他源点的权值,从而可以得到最短权值.超市可以根据自身实际的情况,充分比较各个源点的最短路径,从而确立超市最终的最佳选址地点.