图论最短路径算法的图形化演示及系统设计

周忠玉　方欢　方贤文

摘要：关于图论最短路径算法的图形化演示程序的开发和系统的设计。这里首先介绍最短路径问题的概念和最短路径的算法（指迪杰斯特拉（Dijkstra）算法和弗洛伊德（Floyd）算法）。然后，在Eclipse和JDK1.6环境下开发演示最短路径问题算法的流程。最后，运行系统演示程序进行正确性验证。该算法演示程序简单易用、清晰明了、形象而生动的演示了算法。

关键词：图论；最短路径；Dijkstra；Floyd；演示系统

中图分类号：TP393 文献标识码：A 文章编号：1009-3044（2016）18-0159-02

图论问题始终渗透整个计算机科学，可以说每个编程者都不可避免地与图打交道，因而图论算法对计算机科学至关重要。它的应用领域非常多。例如，图论可以应用于电路网络分析、运筹学、网络、信息论、控制论以及计算机科学等各个领域。我们知道最短路径问题是网络理论中应用最为广泛的问题之一。而这里介绍的最短路径算法是图论算法中重要的一支。最短路径算法可以解决许多问题，例如：线路安排、管道铺设、路由选择、地址选择、设备更新、广场布局、时变拓扑网络等。我们这里研究的就是最短路径问题的算法，具体指的是迪杰斯特拉（Dijkstra）算法和弗洛伊德（Floyd）算法。这里通过开发一个系统演示程序来生动的阐述迪杰斯特拉（Dijkstra）算法和弗洛伊德（Floyd）算法。该系统演示程序简单易用、清晰明了、界面友好、非常实用。该系统演示程序是在Eclipse和JDK1.6的环境下用java语言开发而成的。它为解决最短路径问题提供了一个简单实用的平台。

1 最短路径问题

定义：我们给定一个带权重的有向图G=（V，E）和权重函数w：E→R，该权重函数将每条边映射到实数值的权重上。图中一条路径p=的权重w（p）是构成该路径的所有边的权重之和：w（p）=∑w（vi-1 ， vi） ，i=1，2，3…，k。

假设一条从节点m到节点n的最短路径权重为W（m，n），且W（m，n）计算如下：

①如果存在一条从节点m到节点n的路径，则：W（m，n）=min{w（p）|p是一条从节点m到节点n的路径}；②否则，W（m，n）=∞。

从节点m到节点n的路径p，如果满足w（p）= W（m，n）则该路径p即为从节点m到节点n的最短路径。求从节点m到节点n的最短路径和最短距离的问题就是最短路径问题。

2 最短路径算法

2.1弗洛伊德算法思想

我们使用三重for循环产生一个矩阵来记录每个节点间的最小距离。对于弗洛伊德（Floyd）算法我们使用矩阵Juzhen[i][j]（i，j=1，2，……n+1）存储有向图的权重值。所以，其基本思想为：初始化一个n阶矩阵A（k），其主对角线上的元素初始化为0，非对角线上的元素初始化A（k） [i][j]，其中每一个A（k） [i][j]是节点i到节点j的权重值，k是运算到第几步。算法一开始，我们选择任意两个节点分别作为起始点和终止点，若他们之间有边则取其权重值作为他们的路径长度，若无权重边，则令其路径长度为∞，再有k=0时，我们初始化A（k）[i][j]，此时A（0）[i][j]=Juzhen[i][j]，将路径上的节点加入集合S中，之后再选择不在集合S中但能构成最短路径的节点，使其加入集合S，如果在i节点和j节点之间增加了中间节点后，使得节点i到节点j的路径比A（k） [i][j]小，就用新的权重值去更新A（k） [i][j]。

因此，弗洛伊德（Floyd）算法步骤如下：

（1）当k=0时，A（0）[i][j]= Juzhen[i][j]； 其中Juzhen[i][j]为邻接矩阵

（2）当k=i+1，i+2，…，j时，A（k）[i][j]=min{A（k-1） [i][j]，A（k-1） [i][k]+A（k-1） [k][j]}

其中A（k）[i][j]表示节点点vi 到vj ， 中间节点的不大于k的最短路径的长度，这里求的是中间节点的不大于n的最短路径的长度即A（n）[i][j]。

因而，其算法可以描述为：

（1）令D[i][j]=A[i][j]

（2）for（k=1；k<=n；k++）

for（i=1；i<=n；i++）

for（j=1；j<=n；j++）

if（D[i][j]> D[i][k]+ D[k][j]）

{D[i][j]=D[i][k]+ D[k][j]}

（3）算法结束后矩阵D存储了所有节点之间的最短路径值。

2.2 迪杰斯特拉算法的思想

Dijkstra算法解决的是带权重的有向图上单源点最短路径的问题。该算法要求所有边的权重都为非负值。Dijkstra算法把图中所有的节点分为两组：设集合S表示已经求出的最短路径上的节点的集合；集合T=V-S表示在集合V中而在节点S之外的所有的节点的集合。然后把集合T中节点按权值非减的次序排序，并按此顺序依次加入到集合S里。除此之外，还要满足如下两个条件：第一，从出发点v0到集合S中每一个节点的最短路径长度A（k）[i][j]都应该小于或者等于从节点v0到集合T中所有节点的权重值也即最短路径长度；第二，集合S和集合T都对应一个距离值。S中的节点表示的距离是从出发点v0到该集合中每一个节点的最短路径长度，集合T中的节点表示从出发点v0到集合T中所有的节点且只经过集合S中节点作为中间节点的最短路径长度。因此，迪杰斯特拉算法可描述为：

设置辅助数组dist，其中每个分量dist[k] 表示 当前所求得的从源点到其余各顶点k的最短路径。

（1）S = {v0}；//顶点v0为源点

（2）设置集合V-S中各顶点的初始距离值；

（3）while （集合S中顶点数

{在集合V-S中选择距离最小的顶点vj；S=S+{vj}；

调整集合VS中顶点的距离值；}

3 最短路径算法图形化演示程序检验

下面通过一个实例检验系统演示程序的正确性。

实例：如图1所示，求一条从节点A到节点C的最短路径，并求出其权重值。

具体操作步骤是：①运行系统；②点击新结点按钮和结点连线按钮，然后在画布上用鼠标点击构造结点和连线；③双击结点输入结点名，双击连线输入权重值，以此构造出图1；④选择始点为A，终点为B，选择使用的算法（迪杰斯特拉算法或弗洛伊德算法）；⑤点击激活按钮后，点击开始按钮，结果如图2所示；⑥点击算法展示按钮会出现迪杰斯特拉算法和弗洛伊德算法的展示选择界面；⑦点击概念展示按钮会出现迪杰斯特拉算法和弗洛伊德算法的概念选择界面；⑧在算法展示界面和概念展示界面点击相应的按钮会弹出与此相符的PPT文件进行展示。

4 结论

在了解图论最短路径的问题的算法（迪杰斯特拉（Dijkstra）算法和弗洛伊德（Floyd）算法）、概念和原理的基础上，开发了一个算法图形化演示程序，并对改程序进行了正确性的验证。这里开发的算法系统演示程序生动形象地阐述了迪杰斯特拉（Dijkstra）算法和弗洛伊德（Floyd）算法的概念和原理，并通过画图的方式简化了操作。该系统演示程序简单易用、清晰明了、界面友好、非常实用。它为解决最短路径问题提供了一个简单实用的平台，这样的研究是有积极意义的。

参考文献：

[1] 田丰，马仲蕃.图与网络流理论[M].北京：科学出版社，1987.

[2] 徐凤生.求最短路径的新算法[J].计算机工程与科学，2006，2.

[3] 魏文红，李清霞，蔡昭权.一种基于桶结构的单源最短路径算法[J].计算机工程与科学，2012，4（34）：77-81

[4] 王树西，吴政学.改进的Dijkstra 最短路径算法及其应用研究[J].计算机科学，2012，5（39）：223-228

[5] 朱福喜.面向对象与Java程序设计[M]. 北京：清华大学出版社，2008.

[6] 朱福喜.Java编程技巧与开发实例[M]. 北京：清华大学出版生，2004.

[7] 王昆仑，李红.数据结构与算法[M]. 北京：中国铁道出版社，2006.

[8] 侯风巍.数据结构要点精细[M]. 北京：北京航空航天大学出版社，2006.

[9] 刘万军.Java程序设计实践教程[M]. 北京：清华大学出版社， 2006.

[10] 方贤文.Java语言程序设计[M]. 安徽：安徽科学技术出版社，2014.

[11] 李兴华.java开发实战经典[M]. 北京：清华大学出版社，2009.

[12] 李刚.疯狂java讲义[M]. 北京：电子工业出版社，2012.

[13] 李钟尉.Java从入门到精通[M]. 北京：清华大学出版社，2008.