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

《迪克斯屈拉最短路径算法图论论》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、姓名：沈敬红学院：通信学院学号：s140131109计算机网络中迪克斯屈拉最短路径算法的程序实现及应用沈敬红S140131109重庆邮电大学通信与信息工程学院摘要：本文首先介绍了图论的发展历程，介绍了图论在实际问题中的应用。其次，介绍了图论中最短路径的问题及相关内容，介绍了计算机网络中服务器之间存在的最短路径问题。然后，介绍了迪克斯屈拉（Dijkstra）最短路径算法。最后，依据算法的思想，分别实现了Dijkstra算法在求解计算网络最短路径的应用程序。关键词：最短路径服务器Dijkstra算法程序Abstractinthispaper,wefirstlyintroducethe

2、processoftheoryofgraph.secondly,wegivetheintroductionoftheproblemofshortestpathandrelatedcontent,andtheapplicationofnetworkswhichalotofsevershavetosearchtheshortestpath.Andthenshowstheoneofshortestpathalgorithms:TheDijkstraalgorithm.Finally,accordingtotheideasofthisalgorithm,weputforwardameth

3、odtoachievetheprocedureusinginthenetworks.KeywordShortest—pathsSeverDijkstraProgram1、引言图论(GraphTheory)是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。图论本身是应用数学的一部份，因此，历史上图论曾经被好多位数学家各自独立地建立过。关于图论的文字记载最早出现在欧拉1736年的论着中，他所考虑的原始问题有很强的实际背景。图论的发展已有2

4、00多年的历史，它发源于18世纪普鲁士的柯尼斯堡。当地的居民想知道能否从任意一陆地出发，走遍联接该城的7座桥又回到原地?其条件是每座桥都经过一次并且只经过一次。（具体见“七桥问题”）在加权连通图中，寻求最短路径的问题有其实际背景，例如在某一国家或地区，城市与城市之间都互相连通，从一个城市到达另一城市存在着多条路径，如何实现最短的路径完成两个城市之间的货物运输就是一个解决图论中实现最短路径的问题。同样，比如需要架设电网、通信网络以及其他的有线网络，基于全网的考虑之下，点和点之间怎样架设一条最短的线路就是一个实际的最短路问题。按照图论的表述，在一个图中，两点之间的路径可能有很多条，且

5、每条路径所经过的边数可能是不同的，如果是网络，每条路径的各边权数之和也可能是不同的，怎样找到一条顶点对顶点之间的各边权数之和为最小的路径问题称为最短路问题[1]。本文提出了一个计算机网络中服务器之间最短路径的问题背景，并在迪克斯屈拉（Dijkstra）算法的基础上，实现算法在服务器之间寻求最短路径的程序设计。9姓名：沈敬红学院：通信学院学号：s1401311092、图论相关概念[1,2]：无向图：每一条边都是无向边的图称为无向图。链：设u和v是任意图G的顶点，图G的一条u-v链（chain或walk）是有限的顶点和边交替的序列u0e1u1e2…un-1enun(u=u0,v=un

6、),其中与边e（1≤i≤n）相邻的两个顶点ui和ui-1正好是ei的两个端点。路：内部点不同的链称为路（path）。圈：两端点相同的路（即闭路）称为圈或回路。加权图：边上有数的图称为加权图（weightedgraph）。若边e标记数为k，则称边e的权(weight)为k。在加权图中，链（迹、路）的长度为链（迹、路）上的所有边的权值之和.邻接矩阵：设G＝是任意图，规定n阶方阵A=（aij）为G的邻接矩阵，其中aij为图G中以xi为起点且以yj为终点的边的数目。边权矩阵：设G＝是n阶加权简单图，规定D=（dij）m×n是图的加权矩阵，即dij＝w（i，j）。若结点

7、i到结点j无边可连（在有向图中是方向不一致）时，取dij＝∞。3、问题描述在现有的Internet中存在着大量的不同种类的服务器[7]，这些服务器为用户提供不同种类的数据服务，在服务器与服务器之间存在着数据的交流。如果，我们将各个服务器看做是一个顶点，将服务器与服务器之间的链接看做是一条边，则服务器组成的网络就是一个无向连通图[9]。在这个图上，服务器与服务器之间的链路上都存在着一定的时延，由于网络环境的不同，每个边上的时延均不相同，有的只有几十毫秒，有的却达到上百毫秒，这些毫秒