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

迪克斯屈拉最短路径算法图论论文
预览:

计算机网络中迪克斯屈拉最短路径算法

的程序实现及应用

沈敬红 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)算法的基础上,实现算法在服务器之间寻求最短路径的程序设计。

1

第1页/共9页 下一页>尾页

寻找更多 "迪克斯屈拉最短路径算"