基于 Dijkstra 算法的路由选择
基于 Dijkstra 算法的路由选择
姓名: 班级: 学号:
摘要:本文阐述了最短路径问题及其算法,采用迪克斯屈拉算法解决最短路
由问题。最短路由的问题利用了图的描述,并把算法用 C++语言来实现,这就
很好地将所学知识和现实生活结合起来。
关键词:最短路径 Dijkstra 算法 C++
随着现代通信技术的不断发展,通信网的范围也逐渐扩大,通信网已成为人
们生活中不可或缺的一部分了。而随着人们之间通信次数的增加,使的通信网
的通信量也随之大量增加。这给通信网带了沉重的负担。如何在现有通信网的
基础上提高通信效率,网络利用率和网络可靠性,以满足人们日益增长的对网
络通信能力的需求已成为对通信网研究的主要内容。迪克斯屈拉算法是最适合
解决网络拓扑中两节点间的最短通信距离的问题的方法之一。本文就如何利用
迪克斯屈拉算法解决网络中点到点通信的最短距离问题做了说明,以此提高通
信网的通信效率。
一、迪克斯屈拉算法 1、算法介绍
迪克斯屈拉算法是由荷兰计算机科学家迪克斯屈拉(Dijkstra)于 1959 年提
出的,因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法,
解决的是有向图中最短路径问题。
其基本原理是:每次新扩展一个距离最短的点,更新与其相邻的点的距离。
当所有边权都为正时,由于不会存在一个距离更短的没扩展过的点,所以这个
点的距离永远不会再被改变,因而保证了算法的正确性。不过根据这个原理,
用 Dijkstra 求最短路的图不能有负权边,因为扩展到负权边的时候会产生更短
的距离,有可能就破坏了已经更新的点距离不会改变的性质。
Dijkstra(迪克斯屈拉)算法是典型的单源最短路径算法,用于计算一个节点到
其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩
1 / 3