周忠玉　方欢　方贤文

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

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

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

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

1 最短路径问题