基于Dijkstra算法的路由选择.docx
版权申诉
129 浏览量
2022-06-25
23:25:54
上传
评论
收藏 141KB DOCX 举报
基于 Dijkstra算法的路由选择
姓名：
班级：
学号：
摘要：本文阐述了最短路径问题及其算法，采用迪克斯屈拉算法解决最短路由问
题。最短路由的问题利用了图的描述，并把算法用 C++语言来实现，这就很好地
将所学知识和现实生活结合起来。
关键词：最短路径 Dijkstra算法 C++
随着现代通信技术的不断发展，通信网的范围也逐渐扩大，通信网已成为人
们生活中不可或缺的一部分了。而随着人们之间通信次数的增加，使的通信网的
通信量也随之大量增加。这给通信网带了沉重的负担。如何在现有通信网的基础
上提高通信效率，网络利用率和网络可靠性，以满足人们日益增长的对网络通信
能力的需求已成为对通信网研究的主要内容。迪克斯屈拉算法是最适合解决网络
拓扑中两节点间的最短通信距离的问题的方法之一。本文就如何利用迪克斯屈拉
算法解决网络中点到点通信的最短距离问题做了说明，以此提高通信网的通信效
率。
一、迪克斯屈拉算法
1、算法介绍
迪克斯屈拉算法是由荷兰计算机科学家迪克斯屈拉 （Dijkstra）于 1959
年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短
路径算法，解决的是有向图中最短路径问题。
其基本原理是：每次新扩展一个距离最短的点，更新与其相邻的点的距
离。当所有边权都为正时，由于不会存在一个距离更短的没扩展过的点，
所以这个点的距离永远不会再被改变，因而保证了算法的正确性。不过根
据这个原理，用 Dijkstra 求最短路的图不能有负权边，因为扩展到负权边
的时候会产生更短的距离，有可能就破坏了已经更新的点距离不会改变的
性质。
Dijkstra(迪克斯屈拉 )算法是典型的单源最短路径算法， 用于计算一个
节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩
展，直到扩展到终点为止。 Dijkstra 算法是很有代表性的最短路径算法，
该算法要求图中不存在负权边。
Procedure Dijkstra（G：所有权都为正数的加权连通简单图）
{G带有定点 a=v , v ……，v=z和权 w（v , v ）,若{ v , v }不是 G 中的
0
边，则 w（v , v ）=∞}
1
n
i
j
i
j
i
j
For i:=1 to n
L（vi）:=∞
L（a）: =0
S:=φ
资源评论
