《通信网基础》课程设计
设计题目： Dijkstra算法 班 级： 通信工程083班 姓 名： 吕 琦200809643 指导教师： 樊子锐
兰州交通大学课程设计
目录
摘 要 ...................................................................................................................................................................................... 2 1 DIJKSTRA算法概述 ................................................................................................................................................ 4
1.1 最短路径问题 .............................................................................................................................................................. 4
1.2 DIJKSTRA算法概念 .................................................................................................................................................... 4 1.3 D算法基本思想 .......................................................................................................................................................... 5
2 DIJKSTRA算法的编程与实现........................................................................................................................... 7
2.1 MATALAB程序与实现................................................................................................................................................ 7 2.2 C语言程序与实现...................................................................................................................................................... 9
总结 ........................................................................................................................................................................................ 12 参考文献.............................................................................................................................................................................. 13
1
兰州交通大学课程设计
摘 要
在通信网的网络结构确定以后，任意两点的通信，首选路由应是它们间的最短径，这就是求两点之间的最短径的问题。
Dijkstra(迪杰斯特拉)算法用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。
本文通过一个有向权图，分别用C和matlab语言对D算法实践。形象的解释D算法的思想和步骤。
关键字：通信网；最短径；Dijkstra算法；有向权图；C语言；matlab语言
2
兰州交通大学课程设计
Abstract
In the communication net , if the net structure is determined, the preferred route of any two points of communication net should be the shortest path between them, which is seeking the shortest path between two points of the problem.
Dijkstra (Dijkstra) algorithm is used to calculate a node to the other nodes of the shortest path. The main features of Dijkstra algorithm are the starting point for the center outward expansion of the layers, until extended to the end so far. Dijkstra shortest path algorithm can arrive at the optimal solution, but because it traverses a lot of compute nodes, so the efficiency is low.
In this paper, we use C and matlab language to practice the D algorithm for a map with the right, respectively, and interpret ideas and steps the algorithm.
Keywords: Communication networks; Shortest path; Dijkstra algorithm; Directed weighted graph; C language; Matlab language
3
兰州交通大学课程设计 1 Dijkstra算法概述
Dijkstra算法是典型最短路算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。
1.1 最短路径问题
在给定赋权图G中, 求两个互异顶点间的最短路( 径) , 简记为最短路( 径) 问题。求最短路问题的应用背景广泛, 研究此问题具有实用价值。
最短路问题一般归为两类: 一类是求从某个顶点( 源点) 到其他顶点( 终点) 的最短路径; 另一类是求图中每一对顶点间的最短路径。关于最短路径的研究, 目前已有很多算法, 但基本上均是以D i j k s t r a和F l o y d两种算法为基础, 因此, 对D i j k s t r a算法和F l o y d算法进行本质的研究非常必要。
结合图在计算机中的存储形式, 在程序运行以后, 赋权图的任意两点间的最短距离可用一个矩阵形式表示。设n阶有向或无向连通赋权图G=( V, E) , 其中顶点集V={
,
, …,
} ,边集E={,
, …,
} 。不妨设两顶点,
间的最
短距离为为
, 其中i, j=1, 2, …, n, 则图G的最短距离矩阵d=( ) n×n的元素定义
显然, 只要计算机能输出该图的最短距离矩阵d, 也就解决了最短路径问题。
1.2 Dijkstra算法概念
Dijkstra算法是1959年由E.W.Dijkstra提出的图论中求最短路径的一个著名的算法。Dijkstra算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法，在很多专业课程中都作为基本内
4