迪克斯屈拉最短路径算法图论论文.doc

计算机网络中迪克斯屈拉最短路径算法 的程序实现及应用 沈敬红 S140131109 重庆邮电大学通信与信息工程学院 摘要：本文首先介绍了图论的发展历程，介绍了图论在实际问题中的应用。其次，介绍了图论中最短路径的问题及相关内容，介绍了计算机网络中服务器之间存在的最短路径问题。然后，介绍了迪克斯屈拉（Dijkstra）最短路径算法。最后，依据算法的思想，分别实现了Dijkstra算法在求解计算网络最短路径的应用程序。 关键词：最短路径 服务器 Dijkstra算法 程序 Abstract in this paper, we firstly introduce the process of theory of graph. secondly, we give the introduction of the problem of shortest path and related content, and the application of networks which a lot of severs have to search the shortest path. And then shows the one of shortest path algorithms: The Dijkstra algorithm. Finally, according to the ideas of this algorithm, we put forward a method to achieve the procedure using in the networks. Key word Shortest—paths Sever Dijkstra Program 1、引 言 图论(Graph Theory)是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。 图论本身是应用数学的一部份，因此，历史上图论曾经被好多位数学家各自独立地建立过。关于图论的文字记载最早出现在欧拉1736年的论着中，他所考虑的原始问题有很强的实际背景。 图论的发展已有200多年的历史，它发源于18世纪普鲁士的柯尼斯堡。当地的居民想知道能否从任意一陆地出发，走遍联接该城的7座桥又回到原地? 其条件是每座桥都经过一次并且只经过一次。（具体见“七桥问题”） 在加权连通图中，寻求最短路径的问题有其实际背景，例如在某一国家或地区，城市与城市之间都互相连通，从一个城市到达另一城市存在着多条路径，如何实现最短的路径完成两个城市之间的货物运输就是一个解决图论中实现最短路径的问题。同样，比如需要架设电网、通信网络以及其他的有线网络，基于全网的考虑之下，点和点之间怎样架设一条最短的线路就是一个实际的最短路问题。按照图论的表述，在一个图中，两点之间的路径可能有很多条，且每条路径所经过的边数可能是不同的，如果是网络，每条路径的各边权数之和也可能是不同的，怎样找到一条顶点对顶点之间的各边权数之和为最小的路径问题称为最短路问题[1]。 本文提出了一个计算机网络中服务器之间最短路径的问题背景，并在迪克斯屈拉（Dijkstra）…un-1enun(u=u0,v=un),其中与边e（1≤i≤n）相邻的两个顶点ui和ui-1正好是ei的两个端点。 路：内部点不同的链称为路（path））j）。若结点i到结点j无边可连（在有向图中是方向不一致）时，取dij＝∞。 3、问题描述 在现有的Internet中存在着大量的不同种类的服务器[7]，这些服务器为用户提供不同种类的数据服务，在服务器与服务器之间存在着数据的交流。如果，我们将各个服务器看做是一个顶点，将服务器与服务器之间的链接看做是一条边，则服务器组成的网络就是一个无向连通图[9]。在这个图上，服务器与服务器之间的链路上都存在着一定的时延，由于网络环境的不同，每个边上的时延均不相同，有的只有几十毫秒，有的却达到上百毫秒，这些毫秒数就可以看做边的权值，如何选择最佳的路径使得服务器与服务器之间的数据交换所需时间最短的问题，就变成了求解在无向连通加权图中寻求最短路径的问题。如下图为网络服务器之间的拓扑图： （注：S1-S6为网络服务器节点，权值为10ms/每单位值） 4、迪克斯屈拉（Dijkstra）算法实现 4.1 Dijkstra算法[1]描述： 算法基本思想：一个顶点V1作为源点，求该顶点到其他各顶点的最短路径，提出了一个按路径长度递增的顺序产生最短路径的方法。此方法的基本思想是：把图中所有结点分成两组，第一组包括已确定最短路径的顶点，第二组包括尚未确定最短路径的顶点 ，按最短路径长度递增的顺序