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

图论最短路径算法的图形化演示及系统设计.doc图论最短路径算法的图形化演示及系统设计
摘要:关于图论最短路径算法的图形化演示程序的开发和系统的设计。这里首先介绍最短路径问题
的概念和最短路径的算法(指迪杰斯特拉(Dijkstra) f法和弗洛伊德(Floyd)算法)。然后,在Eclipse和
。最后,运行系统演示程序进行正确性验证。该算法演示程序简单易用、清晰明了、形象而生动的演示了算法。
关键词:图论;最短路径;Dijkstra; Floyd;演示
系统
中图分类号:TP393文献标识码:A文章编号: 1009-3044 (2016) 18-0159-02
图论问题始终渗透整个计算机科学,可以说每个编程者都不可避免地与图打交道,因而图论算法对计算机科学至关重要。它的应用领域非常多。例如,图论可以应用于电路网络分析、运筹学、网络、信息论、控制论以及计算机科学等各个领域。我们知道最短路径问题是网络理论中应用最为广泛的问题之一。而这里介绍的最短路径算法是图论算法中重要的一支。最短路径算法可以解决许多问题,例如:线路安排、管道铺设、路由选择、地址选择、设备更新、广场布局、时变拓扑网络等。我们这里研宄的就是最短路径问题的算法,具体指的是迪杰斯特拉
(Dijkstra)算法和弗洛伊德(Floyd)算法。这里通过开发一个系统演示程序来生动的阐述迪杰斯特拉(Dijkstra)算法和弗洛伊德(Floyd)算法。该系统演示程序简单易用、清晰明了、界面友好、非常实用。该系统演示程序是在Eclipse 。它为解
决最短路径问题提供了一个简单实用的平台。 1最短路径问题
定义:我们给定一个带权重的有向图G= (V,E) 和权重函数w: E—R,该权重函数将每条边映射到实
数值的权重上。图中一条路径p=的权重w (p)是构成该路径的所有边的权重之和:w (p) =Ew (vi-1, vi) ,i=l,2,3…,ko
假设一条从节点m到节点n的最短路径权重为W (m, n),且W (m,n)计算如下:
①如果存在一条从节点m到节点n的路径,贝lj: 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最短路径算法

我们使用三重for循环产生一个矩阵来记录每个节点间的最小距离。对于弗洛伊德(Floyd)算法我们
使用矩阵 Juzhen[i][j] (i,j=l,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)
[j]=Juzhen[i即,将路径上的节点加入集合