基于Dijkstra算法的路由选择

基于Dijkstra算法的路由选择

姓名： 班级： 学号：

摘要：本文阐述了最短路径问题及其算法，采用迪克斯屈拉算法解决最短路由问题。最短路由的问题利用了图的描述，并把算法用C++语言来实现，这就很好地将所学知识和现实生活结合起来。

关键词：最短路径 Dijkstra算法 C++

随着现代通信技术的不断发展，通信网的范围也逐渐扩大，通信网已成为人们生活中不可或缺的一部分了。而随着人们之间通信次数的增加，使的通信网的通信量也随之大量增加。这给通信网带了沉重的负担。如何在现有通信网的基础上提高通信效率，网络利用率和网络可靠性，以满足人们日益增长的对网络通信能力的需求已成为对通信网研究的主要内容。迪克斯屈拉算法是最适合解决网络拓扑中两节点间的最短通信距离的问题的方法之一。本文就如何利用迪克斯屈拉算法解决网络中点到点通信的最短距离问题做了说明，以此提高通信网的通信效率。

一、迪克斯屈拉算法 1、算法介绍

迪克斯屈拉算法是由荷兰计算机科学家迪克斯屈拉（Dijkstra）于1959年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有向图中最短路径问题。

其基本原理是：每次新扩展一个距离最短的点，更新与其相邻的点的距离。当所有边权都为正时，由于不会存在一个距离更短的没扩展过的点，所以这个点的距离永远不会再被改变，因而保证了算法的正确性。不过根据这个原理，用Dijkstra求最短路的图不能有负权边，因为扩展到负权边的时候会产生更短的距离，有可能就破坏了已经更新的点距离不会改变的性质。

Dijkstra(迪克斯屈拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法，该算法要求图中不存在负权边。

Procedure Dijkstra（G：所有权都为正数的加权连通简单图）

{G带有定点a=v0, v1 ……，vn=z和权w（vi , vj）,若{ vi, vj }不是G中的边，则w（vi, vj）=∞}

For i:=1 to n L（vi）:=∞ L（a）: =0 S:=φ

{初始化标记，a的标记为0，其余结点标记为∞，S是空集} While z错误！未找到引用源。S begin

u:=不属于S的L（u）最小的一个顶点 S：=S错误！未找到引用源。{u} for 所有不属于S的顶点v if L(u)+w(u,v) < L(v) then L(v):=L(u)+w(u,v)

{这样就给S中添加带最小标记的顶点并且更新不在S中的顶点标记} end {L（z）=从a到z的最短路的长度}

2、根据Dijkstra算法给出的定理

定理1 迪克斯屈拉算法求出连通简单无向加权图中的两个顶点之间最短路的长度。

迪克斯屈拉算法通过一步一步的迭代求出最短路径，假设在第k次迭代中。 在s中的顶点v的标记L(v)是从a到这个顶点v的最短路的长度。不在s中的顶点的标记是（除了这个顶点自身之外）只经过s中顶点的从a到这个顶点的最短路的长度。设u是第k次迭代结束时带最小标记的不在s中的顶点（若该顶点不唯一，可采用带最小标记的任意顶点）。在第k+1次迭代中，u是添加到s中的顶点，则在第k+1次迭代中，u的标记必须是a到u的最短路的长度。否则，k次迭代后，从结点a到某个结点l的路，其路得长度小于Lk（v）。

2

定理2 迪克斯屈拉算法使用O（n）次运算（加法和比较）来求出n阶连通简单无向加权图中两个顶点之间最短路的长度,求加权无向图中最短路的Dijkstra算法可以推广到求加权有向图中最短有向路。

定理3 设有向图G中不含长度非正的有向圈，并且从点1到其余各点都有有限长的有向路,那么G中结点1到其余各点j的最短有向路长度Sj有唯一有限解{Sj}。

定理4 设Sj是加权有向图G中自结点1到结点j的最短有向路的长度，并且对所有的j=1，2，3，……，n，Sj为有限值。若图G中除结点1外的其余各点能重新编写成如下的序号2，3，……，n使得对所有i

Si≤Sj 错误！未找到引用源。且w≥0

或者Si>Sj 且 w=错误！未找到引用源。,即 错误！未找到引用源。E（G），则

错误！未找到引用源。

定理5 设G=是一个边权为正值的有向图，其中V={1，2，3……，n}。则在G中，任意一条最短有向路得长都大于它的真子有向路的长。

Dijkstra算法求出了图中一个特定顶点到其他各定点的最短路，可以利用Dijkstra算法解决实际生活中的一些问题。

二、Dijkstra算法的实际应用 1、问题的提出

在现实生活中，我们常常会遇到很多问题，都是要找到一个地方到另一个地方的最短路径，当然还要满足各方面的要求，包括可实现性、预算、带来的利益等各方面条件。比如Dijkstra算法在计算机网络路由问题中的应用。通常我们解决的办法就是找到一条距离最短，又在现实可接受范围内的路径。

2、运用Dijkstra算法解决实际问题

在通信网中，如何利用现有的通信网络，通过最短的通信路径完成信息的传递，在通信网研究中具有重要意义。为了降低研究复杂性，我们假设每条通信线路的通信系能和状况都一样且恒定不变。建立如下网络模型：点用来表示路由节点（用a到e及z…表示），边用来表示两节点间的通信线路，边上的权重表示两节点间的距离，节点本身到他自己的距离记为0，如果两节点没有边直接相连用 ∞ 表示。

b400a200c1000图1 无向图G e

500d600100800200300z利用Dijkstra算法实现求解最短路径问题要有边权。本文最佳路径是基于两个路由节点间的距离。因此找路由节点间的最短距离就转化成了找图G=（V,E）中指定两点间的最小距离了。

首先我们利用上图可以知道节点之间的邻接关系，为此我们可以先画出节点间的邻接矩阵，方便我们对节点的关系进行了解。如下表（单位：m）：

a b c d e z a 0 400 200 ∞ ∞ ∞ b c 400 200 0 100 100 0 500 800 ∞ 1000 ∞ ∞ d ∞ 500 800 0 200 600 e ∞ ∞ 1000 200 0 300 z ∞ ∞ ∞ 600 300 0

下面对最优路径进行分析，我们a为路径的起点，z为终点。 初始化： L(a)=0

L(b)=∞，L(c)=∞，L(d)=∞，L(e)=∞，L(z)=∞， S=Φ, 一次迭代：U=a，S={a}

L(a)+W(a,b)=0+400=400

L(a)+W(a,e)=0+∞=∞ L(a)+W(a,z)=0+∞=∞

L(b)=400, L(c)=200, L(d)= L(e)= L(z)= ∞

二次迭代：U=c，S={a,c}

L(c)+W(c,b)=200+100=300

L(b)=300， L(d)=1000， L(e)=1200，L(z)= ∞ 三次迭代：U=b，S={a，c，b}

L(b)+W(b,d)=300+500=800 ∞ L(b)+W(b,z)=300+∞=∞

L(d)=800， L(e)=1200, L(z)= ∞ 四次迭代：U=d，S={a，c，b，d}

L(d)+W(d,e)=800+200=1000

L(e)+W(e,z)=1000+300=1300

结束：U=z，S={a，c，b，d，e，z}

由于终点z已经进入S集合中所以迭代结束。这样就找到了从起点a到终点z的最短路径以及到中间各点的最短路径。

本文的算法是在VC++的环境下实现的，程序的基本思想是基于Dijkstra算法的。这个程序中是以节点1代表a，且以节点1作为初始节点，节点6最为终止节点，在程序中所求的最短路径问题则为从节点1到节点6以及其他中间节点的最短路径。具体的程序代码见附录。

图2运行结果

三、结论

通过本学期对《计算机算法设计与分析》的学习，使我深刻体会到了算法在实际生活中的广泛应用，也使从以前的定向思维上升了一个台阶，学会把抽象的变为具体，能用点、线、图来描述抽象的事物，把很多抽象的知识具体化，使得抽象的知识更容易理解、记忆。

《计算机算法设计与分析》中有很多简便的算法，可以实现很多功能。Dijkstra算法是计算机众多算法中的一种，能够方便的找到两点之间的最短路径，通过上面Dijkstra算法的应用例子可以清楚的看到通过Dijkstra算法可以在很复杂的图中很容易的找到点到点的最短路径，也可以对实际生活中的一些问题给予很大的帮助。

参考文献：

[1] 王晓东.计算机算法设计与分析第四版.

[2] 乐阳,龚健雅.Dijkstra最短路径算法的一种高效率实现. [3] 凡金伟,吕康.基于Dijkstra算法在物流配送中的应用.

[4] 徐凤生，李天志.所有最短路径的求解算法[J].微计算机应用.

附录：

#include #include

#define MaxNum 10000 //节点间不是邻居节点 #define n 6//节点数目

本文来源：https://www.bwwdw.com/article/jp6h.html