最短路径优先

最短路径优先（精选11篇）

最短路径优先 篇1

摘要：首先介绍了OSPF(Open Shortest Path First开放最短路径优先)路由协议,接下来介绍了OSPF的HELLO报文、DD报文、LSR报文、LSU报文、LSAck报文等5种报文以及OSPF协议计算路由的过程。针对OSPF的攻击与防范问题,介绍了基于LSA(链路状态广播)攻击的基本原理及基本防范方法。

关键词：路由协议,OSPF协议,链路状态广播,攻击

开放最短路径优先协议OSPF(Open Shortest Path First)是一种基于链路状态的内部网关路由协议。OSPF引入了路由更新认证、可变长子网掩码VLSM和路由聚合等概念。本文首先阐述OSPF的工作原理,然后讨论关于OSPF的攻击及防范方法。

1 OSPF路由协议原理

OSPF路由协议是一种典型的链路状态(Link-state)的路由协议,一般用于同一个路由域内。路由域是指一个自治系统(Autonomous System),即AS,它是指一组通过统一的路由策略或路由协议互相交换路由信息的网络。在这个AS中,所有的OSPF路由器都维护一个相同的描述这个AS结构的数据库,该数据库中存放的是路由域中相应链路的状态信息,OSPF路由器通过这个数据库中的链路状态信息计算出其对应的OSPF路由表。

作为一种链路状态的路由协议,OSPF将链路状态广播数据包LSA(Link State Advertisement)传送给在某一区域内的所有路由器。运行距离矢量路由协议的路由器是将部分或全部的路由表传递给与其相邻的路由器。

1.1 OSPF协议的特点

OSPF协议具有以下特点:

适用范围广,OSPF支持各种规模的网络,最大可支持几百台路由器;快速收敛,如果网络结构发生变化,OSPF立即发送更新报文,使这一变化在自治系统中同步;无自环,OSPF通过收集到的链路状态(LSA)用最短路径树算法计算路由,故从算法本身保证了不会生成自环路由;子网掩码,由于OPSF在描述路由时携带网段的掩码信息,所以OSPF协议不受自然掩码的限制,对VLSM提供很好的支持;区域划分,OSPF协议允许自治系统的网络被划分成区域来管理,区域间传送的路由信息被进一步抽象,从而减少了占用网络的带宽;等值路由,OSPF支持到同一目的地址的多条等值路由;路由分级,OSPF使用4类不同的路由,按优先顺序来说分别是:区域内路由、区域间路由、第一类外部路由、第二类外部路由;支持验证,它支持基于接口的报文验证以保证路由计算的安全性;组播发送,OSPF在有组播发送能力的链路层上以组播地址发送协议报文,即达到了广播的作用,有最大程度的减少了对其他网络设备的干扰。

1.2 OSPF的协议报文

OSPF的报文类型一共有五种:

HELLO报文(Hello Packet):最常用的一种报文,周期性的发送给本路由器的邻居。内容包括一些定时器的数值,DR,BDR,以及自己已知的邻居。

DD报文(Database Description Packet):两台路由器进行数据库同步时,用DD报文来描述自己的LSDB,内容包括LSDB中每一条LSA的摘要(摘要是指LSA的HEAD,通过该HEAD可以唯一标识一条LSA)。这样做是为了减少路由器之间传递信息的量,因为LSA的HEAD只占一条LSA的整个数据量的一小部分,根据HEAD,对端路由器就可以判断出是否已经有了这条LSA。

LSR报文(Link State Request Packet):两台路由器互相交换过DD报文之后,知道对端的路由器有哪些LSA是本地的LSDB所缺少的或是对端更新的LSA,这时需要发送LSR报文向对方请求所需的LSA。内容包括所需要的LSA的摘要。

LSU报文(Link State Update Packet):用来向对端路由器发送所需要的LSA,内容是多条LSA(全部内容)的集合。

LSAck报文(Link State Acknowledgment Packet):用来对接收到的LSU报文进行确认。内容是需要确认的LSA的HEAD(一个报文可对多个LSA进行确认)。

1.3 OSPF协议计算路由过程:

右图描述了通过OSPF协议计算路由的过程:

1)由四台路由器组成的网络,连线旁边的数字表示从一台路由器到另一台路由器所需要的花费。为简化问题,我们假定两台路由器相互之间发送报文所需花费是相同的。

2)每台路由器都根据自己周围的网络拓扑结构生成一条LSA(链路状态广播),并通过相互之间发送协议报文将这条LSA发送给网络中其它的所有路由器。这样每台路由器都收到了其它路由器的LSA,所有的LSA放在一起称作LSDB(链路状态数据库)。显然,4台路由器的LSDB都是相同的。

3)由于一条LSA是对一台路由器周围网络拓扑结构的描述,那么LS-DB则是对整个网络的拓扑结构的描述。路由器很容易将LSDB转换成一张带权的有向图,这张图便是对整个网络拓扑结构的真实反映。显然,4台路由器得到的是一张完全相同的图。

4)接下来每台路由器在图中以自己为根节点,使用SPF算法计算出一棵最短路径树,由这棵树得到了到网络中各个节点的路由表。显然,4台路由器各自得到的路由表是不同的。这样每台路由器都计算出了到其它路由器的路由。

由上面的分析可知:OSPF协议计算出路由主要有以下三个主要步骤:

描述本路由器周边的网络拓扑结构,并生成LSA;将自己生成的LSA在自治系统中传播,并同时收集所有的其他路由器生成的LSA;根据收集的所有的LSA计算路由。

2 OPSF攻击与防范

路由器在每个网络中起到关键的作用,如果一路由器被破坏或者一路由被成功的欺骗,网络的完整性将受到严重的破坏,如果使用路由的主机没有使用加密通信那就更为严重,因为这样的主机被控制的话,将存在着中间人(man-in-the-middle)攻击,拒绝服务攻击,数据丢失,网络整体性破坏,和信息被嗅探等攻击。

OSPF由于内建几个安全机制所以比起RIP协议安全的多,但是,其中LSA的几个组成部分也可以通过捕获和重新注入OSPF信息包而被修改。如果一个攻击者冒充一台合法路由器与网络中的一台路由器建立邻接关系,并向攻击路由器输入大量的链路状态广播(LSA,组成链路状态数据库的数据单元),就会引导路由器形成错误的网络拓扑结构,从而导致整个网络的路由表紊乱,导致整个网络瘫痪。

关于OSPF常见的借助于LSA的拒绝攻击:

1)Max Age attack攻击

Max Age attack攻击LSA的最大age值为一小时(3600),攻击者发送带有最大MaxAge设置的LSA信息包,这样,最开始的路由器通过产生刷新信息来发送这个LSA,而后就引起在age项中的突然改变值的竞争。如果攻击者持续的突然插入最大值到信息包给整个路由器群将会导致网络混乱和导致拒绝服务攻击。

2)Sequence++攻击

攻击者持续插入比较大的LSA sequence(序列)号信息包,因为LS sequence number(序列号)栏是被用来判断旧的或者是否同样的LSA,序列号越大表示这个LSA越是新近的。所以当攻击者持续插入比较大的LSA sequence(序列)号信息包时候,最初的路由器就会产生发送自己更新的LSA序列号来超过攻击者序列号的竞争,这样就导致了网络不稳定并导致拒绝服务攻击。

3)最大序列号攻击

即攻击者把最大的序列号0x7FFFFFFF插入。当想超过最大序列号的时候,LSA就必须从路由domain(域)中刷新,有InitialSequen-ceNumber初始化序列号。这样如果攻击者的路由器序列号被插入最大序列号,并即将被初始化,理论上就会马上导致最开始的路由器的竞争。

4)伪造LSA攻击

这个攻击主要是gated守护程序的错误引起的,需要所有gated进程停止并重新启动来清除伪造的不正确的LSA,由此导致拒绝服务的产生。这个攻击对硬件的路由器不影响并且对于新版本的gated也没有效果。

3 结束语

OSPF使用协议类型89,其虽然具有验证机制、可靠的扩散机制、分层路由等的自我保护能力,但仍然存在许多漏洞。可以使用目前应用最广的nmap协议扫描判断OSPF存在的威胁,如下所示:

这里建议,如果大多数的主机使用静态路由就能很好的完成各项功能则使用静态路由,因为使用动态路由协议很会受到攻击;如果OSPF启用了报文验证功能(HMAC验证),则可以从很大程度上避免上述基于LSA的攻击。

参考文献

[1]王先培,文云冬,高志新,潘汪杰.OSPF路由协议的脆弱性分析[J].武汉大学学报:工学版,2004(37,3).

[2]蔡昭权.OSPF路由协议的攻击分析与安全防范[J].计算机工程于设计,2007.12(28,23).

[3]谭浩强.网络互联设备实用技术教程[M].北京:清华大学出版社,2008.

[4]张普生.局域网组网技术与实训[M].北京:清华大学出版社,2008.

最短路径优先 篇2

用dp记忆化搜索的思想来考虑是思路很清晰的，但是困难在如何求出字典序最小的路。

因为左边到右边的字典序最小就必须从左边开始找，于是我们可以换个思路，dp时从右边走到左边，这样寻找路径就可以从左向右了。

代码：

/*

* Author: illuz

* Blog: blog.csdn.net/hcbbt

* File: uva116.cpp

* Create Date: -09-20 20:56:07

* Descripton: dp, memorial

*/

#include

#include

using namespace std;

const int MAXN = 102;

int dis[MAXN][MAXN], map[MAXN][MAXN], n, m;

int cg(int x) {

if (x == 0) x = n;

else if (x == n + 1) x = 1;

return x;

}

int dp(int x, int y) {

x = cg(x);

if (dis[x][y] != -0xffffff) return dis[x][y];

return dis[x][y] = map[x][y] + min(min(dp(x - 1, y + 1), dp(x, y + 1)), dp(x + 1, y + 1));

}

void print(int x, int y) {

if (y < m)

printf(“%d ”, x);

else {

printf(“%d”, x);

return;

}

int a[3] = {cg(x - 1), cg(x), cg(x + 1)};

sort(a, a + 3);

int tt = dis[x][y] - map[x][y];

if (tt == dis[a[0]][y + 1])

print(a[0], y + 1);

else if (tt == dis[a[1]][y + 1])

print(a[1], y + 1);

else

print(a[2], y + 1);

}

int main {

while (scanf(“%d%d”, &n, &m) != EOF) {

for (int i = 1; i <= n; i++)

for (int j = 1; j <= m; j++) {

scanf(“%d”, &map[i][j]);

if (j == m) dis[i][j] = map[i][j];

else dis[i][j] = -0xffffff;

}

int Min = 0xffffff, t, rx, ry;

for (int i = 1; i <= n; i++) {

t = dp(i, 1);

if (t < Min)

rx = i, Min = t;

}

print(rx, 1);

printf(“%d”, Min);

}

return 0;

数据结构最短路径算法及其应用 篇3

关键词： 最短路径 Dijkstra算法 Floyd算法 图论

最短路径，就是在所有路径中找到一条距离最短的路径，而我们所说的最短路径不仅指地理意义的距离最短，而且可以引申到其他度量，如时间、费用、路线容量。相应地，最短路径问题就成为最快路径问题，最低费用问题等，所以我们所说的最短路径也可以看做最优路径问题。最短路径问题在交通网络结构的分析，交通运输路线的选择，通讯线路的建造与维护，运输货流的最小成本分析，城市公共交通网络的规划等方面，都有直接应用的价值。最短路径问题在实际中常用于汽车导航系统及各种应急系统等这些系统，一般要求计算出到出事地点的最佳路线的时间应该在1s到3s内，在行车过程中还需要实时计算出车辆前方的行驶路线，这就决定了最短路径问题的实现应该是高效的。经典图论与不断发展完善的计算机数据结构及算法的有效结合使新的最短路径算法不断涌现。

一、图论基本概念

1.图的定义。图（graph）是一种较线性表和树更为复杂的数据结构，图与线性表和树的结构区别表现在结点之间的关系上，线性表中的每个结点（除首尾结点外）都有一个前驱结点和一个后继结点，结点与结点之间的关系是一对一的关系；树上的每个结点都有一个父结点（根结点除外）和一个或多个孩子结点（叶子结点除外），结点与结点的关系是一对多的关系；而图中结点之间的关系是多对多的关系，结点与结点之间的连接是任意的，每对结点间可以有连接也可以没有连接。

2.图的存储结构。除了存储图中各个顶点本身的信息外，还要存储顶点与顶点之间的所有关系。常用的图的存储结构有邻接矩阵、邻接表、十字邻接表和邻接多重表。

二、最短路径问题

所谓最短路径即从图G中某对顶点Vi和Vj（i≠j）之间的所有路径中选出权值之和最短的一条路径作为顶点Vi到顶点Vj的最短路径。其中边的权值可多种，如路途、费用、耗时等，也可以同时存在多种权值，根据给定的比例，算出边的综合权值。

1.最短路径。在一个无权的图中，若从一个顶点到另一个顶点存在一条路径，则称该路径长度为该路径上经过的边的数目，等于该路径上的顶点数减1。由于从一个顶点到另一个顶点可能存在多条路径，每条路径上经过的边数不同，即长度不同，把长度最短的那条叫做最短路径。

2.最短路径算法。求图中最短路径有两方面问题：求图中某一顶点到其余各顶点的最短路径与求图中每一对顶点之间的最短路径。它们分别有Dijkstra算法和Floyd算法。

2.1Dijkstra算法。Dijkstra算法又称为标号法，是用于求解单源点最短路径的实用算法，至今仍然被公认为是解决从固定点出发到网络中的任意顶点的最短路径问题的较好方法之一。基本思想如下：设置并逐步扩充一个集合S，存放已求出其最短路径的顶点，则尚未确定最短路径的顶点集合是V-S，其中，V为网中所有顶点集合。按最短路径长度递增的顺序逐个用V-S中的顶点加到S中，直到S中包含全部顶点，而V-S为空。

2.2Floyd算法。Floyd算法能够求得任意顶点之间的最短路径。基本思想是任意2个顶点vi到vj的距离的带权邻接矩阵开始，每次插入一个顶点vk，然后将vi到vj间的已知最短路径与插入顶点vk作为中间顶点时可能产生的vi到vj路径距离比较，取较小值以得到新的距离矩阵。如此循环迭代下去，依次构造出N个矩阵D（1），D（2）…D（n），当所有顶点均作为任意 2个顶点vi到vj中间顶点时得到的最后的带权邻接矩阵D（n）就反映了所有顶点对之间的最短距离信息，成为图G的距离矩阵。

三、 应用举例

1.Dijkstra算法在公交网络中的应用。在纷繁复杂的城市公交网中，如果想寻找到一条从当前某个站点到达另一个目的站点的最短路径应该怎样实现呢？针对这个问题采用图论中最短路径思想进行了思考和研究，并采用Dijkstra算法实现搜寻计算操作和过程。

（1）实际问题描述。公交网络中最短路径问题可以描述为从某起始站点S出发到达目的站点E，其中S和E之间可行的线路往往不只一条，而是有很多条，那么这么多可行线路中哪一条是最短的呢？这里“最短”指实际走过的路程最短，或指在不计算公交换乘花费时间和公车保持匀速行驶的前提下，能够以最短时间到达目的地中的“最短”。要求解这个问题如果不考虑其他各方面的复杂因素，就可以看成一个简单的最短路径问题。

（2）数学模型建立。起始站点、目的站点及所有可行路径和中间站点构成的交通网络，可以抽象为一个图状的数据模型——有向带权图记为G=（V，E，L），其中V表示所有站点的集合，假设共有N个站点；E表示所有直接通路或直通边的集合，假设共有M条直通边，注意，在实际应用中，这里的边是有方向性的，边的方向表示该直接通路的可行方向；L表示每条直接通路对应的边权集合，即每条直通边对应的距离值或时间开销等。

（3） 实际问题抽象化。经过上述分析和建模，实际最短路径问题可抽象为有向带权图中两顶点之间的最短路径问题。

四、结语

若寻找从起始点到其他所有顶点的最短路径，按照Dijkstra算法则最多需要经过N-1步的搜寻计算操作（N表示G中的顶点个数）。在实际应用中，Dijkstra算法称为单源点最短路径算法。事实上，Dijkstra最短路径算法除了可以用在公交网络上之外，还可以用在现实生活的很多方面，如邮政线路、物流线路、管道布线等，我们还可以不断将其推广应用于更多方面，从而使数学与计算机科学能够更充分地为人类服务。

参考文献：

[1]严蔚敏，吴伟民.数据结构[M].北京：清华大学出版社，2002.

[2]李春葆，曾慧，张植民.数据结构程序设计题典[M].北京：清华大学出版社，2002.

[3]张永，李睿，年福忠.算法与数据结构[M].北京：国防工业出版社，2008.

[4]刘玉龙.数据结构与算法实用教程[M].北京：电子工业出版社，2007.

[5]徐俊明.图论及其应用[M].合肥：中国科学技术大学出版社，2004.

最短路径的教学 篇4

《数据结构》课程是计算机类信息类专业的基础核心课程, 这门课程掌握的程度影响到其它后续课程的学习, 相关知识也会应用在实际的软件开发中。大多数院校在低年级开设这门课程, 低年级的学生一般只学过一门高级程序设计语言, 如C语言, 对面向对象程序设计、面向对象编程思想、抽象类型、数学模型、解决实际问题的算法了解甚少。笔者长期从事《数据结构》课程的教学, 对这门课程的教学有一套自己的方法。本文以最短路径的教学为例, 论述了《数据结构》中抽象类型--图的教学思路。

1. 问题的提出

随着生活水平的提高, 汽车已经进入千家万户, 工薪阶层拥有汽车已经成为可能。假期上班族开着自己的汽车到外地旅游已经成为一种时尚。在旅游的过程中, 如何缩短路程减少费用, 成了人们关心的问题。如, 旅客要自己开车从福州到乌鲁木齐, 怎样选择线路, 才能使路径的总和最短, 从而费用总和最少。

2. 数学模型

在上面的问题中, 可以把城市看成顶点, 城市之间若有路可到达的话, 在城市对应的顶点之间加上一条边, 在边上加上权值表示两个城市之间的距离, 这样可以构成一个图 (我们称为无向网络) 。在构造无向网络的过程中, 只要考虑感兴趣的城市 (也就是说只要把感兴趣城市对应的顶点加入到无向网络中) , 同样道理, 也只要把感兴趣的线路加入到无向网络中。

3. 存储结构

G.kind存储的值有四种DG, DN, UDG, UDN。DG表示有向图, DN表示有向网络, UDG表示无向图, UDN表示无向网络。G.vertexnum存储的值表示顶点的个数 (或者说是城市的个数) 。G.edgenum存储的值表示边的条数 (或者说是线路的条数) 。G.edges[j][k]存储的值表示两个城市之间的距离。G.vertexs[i]存储的值是城市的名称。

最终, D[j][k]存放从第j个顶点到第k个顶点的最短距离, P[j][k][t]存放从第j个顶点到第k个顶点的最短路径上的顶点的下标, N[j][k]存放从第j个顶点到第k个顶点的最短路径上的顶点的个数。

4. 实现算法

5. 问题的解决

调试过程如下 (带下划线的字符为从键盘输入的数据) :

要创建图, 请输入图的类型,

0表示有向图 (DG) , 1表示有向网络 (DN) , 2表示无向图 (UDG) , 3表示无向网络 (UDN) :3

要创建无向网络 (UDN) , 请输入顶点的数目:25

要创建无向网络 (UDN) , 请输入边的数目:30

要创建无向网络 (UDN) , 请输入25个顶点:

福州南昌上海徐州天津大连沈阳长春哈尔滨北京郑州武汉株州广州深圳南宁柳州贵阳昆明成都西安呼和浩特兰州西宁乌鲁木齐 (回车)

要创建无向网络 (UDN) , 请输入25*25的矩阵, 有边用权值, 无边用0:

请输入起点城市:

请输入终点城市:

从福州到乌鲁木齐的最短路径为:福州---南昌---株州---武汉---郑州---西安---兰州---乌鲁木齐 (5011)

继续吗?请输入 (Y或y表示继续, N或n表示终止) :

请输入起点城市:

请输入终点城市:

从南宁到乌鲁木齐的最短路径为:南宁---柳州---株州---武汉---郑州---西安---兰州---乌鲁木齐 (4949)

继续吗?请输入 (Y或y表示继续, N或n表示终止) :

摘要：本文论述了《数据结构》图论部分最短路径这一小节教学过程当中的一些体会。从实际问题出发, 提出相关的数学模型, 建立相应的存储结构, 在建立的结构上编写算法, 从而达到解决实际问题。

关键词：数据结构,抽象类型,最短路径,教学方法

参考文献

[1]《数据结构 (C语言版) 》, 严蔚敏吴伟民编著, 清华大学出版社, 1997.4

最短路径优先 篇5

一、实验目的：

理解最短路径分析的基本原理，学习利用arcgis软件进行各种类型的最短路径分析的操作。

二、实验准备

1、实验背景：

最短路径分析是空间网络分析中最基本的应用，而交通网络中要素的设置对最短路径的选择有着很大的影响。实验要求根据不同的权重，给出到达指定目的地的路径选择方案，并给出路径长度。

 在网络中指定一个超市，要求分别求出在距离、时间限制上从家到超市的最佳路径。

 给定访问顺序，按要求找出从家经逐个地点达到目的地的最佳路径。

2、实验材料：

软件：ArcGIS Desktop 9.x，实验数据：文件夹ex6中，一个GeoDatabase地理数据库：City.mdb，内含有城市交通网、超市分布图，家庭住址以及网络关系。

三、实验内容及步骤

首先启动ArcMap，选择ex6city.mdb，再双击后选择将整个要素数据集“city”加载进来，然后将“place”点状要素以“HOME”字段属性值进行符号化，1值是家，0值是超市。

第1步 无权重最佳路径的选择  加载 “设施网络分析”工具条（“视图”>>“工具条”，勾选“设施网络分析”），点选旗标和障碍工具板下拉箭头，将旗标放在家和想要去的超市点上。

第2步 加权最佳路径选择

 在设施网络分析工具条上，点选旗标和障碍工具板下拉箭头，将旗标放在家和想去的某个超市点上。

 选择“分析”下拉菜单，选择“选项”按钮，打开“分析选项”对话框，选择“权重”标签页，在“边权重”上，全部选择长度“length”权重属性。 点选“追踪任务”下拉菜单选择“查找路径”。单击“执行”键，则以长度为比重为基础的最短路径将显示出来，这条路径的总成本将显示在状态列。

 上述是通过距离的远近选择而得到的最佳路径，而不同类型的道路由于道路车流量的问题，有时候要选择时间较短的路径，同样可以利用网络分析进行获得最佳路径。

第3步 按要求和顺序逐个对目的点的路径的实现

 在设施网络分析工具条上，点选旗标和障碍工具板下拉箭头，将旗标按照车辆访问的顺序逐个放在点上。

 选择“分析”下拉菜单，选择“选项”按钮，打开“分析选项”对话框，选择“权重”标签页，在“边权重”上，全部选择长度“length”权重属性。 点选“追踪任务”下拉菜单选择“查找路径”。单击“执行”键，则从起点按顺序逐一经过超市最后回到家的最短有效路径将显示出来，这条路径的总成本将显示在状态列。

同样是经过这11个地点，换成权重是时间的，由于道路车流量的不同，如在市中心车流量特别大，车速慢，故而为节约时间，所以使得路径发生很大的改变。

第4步 阻强问题

这里的阻强是指网络中的点状要素或线状要素因为实际中遇到的例如修路，或那个时段车辆饱和，十字路口发生事故等一些缘故而使得要素不可运行，这时原来获得的最短路径就需要进行修正，具体操作如下： 修路的情形出现，即某个路段不可运行，这在网络中的表现是设置阻强，方法有两种，一种是永久性的，直接将网络边要素的属性修改成不可运行。选择要进行设置的边要素，将其属性中的“Enabled”字段改成“False”即可；另一种是暂时性的，设置边要素障碍。即利用边要素障碍添加工具将边设置。



最短路径优先 篇6

关键词：Dijkstra算法 K最短路径 公共交通 衔接规划

Solves K most shortpath improvement Dijkstra algorithm

Zhang SongWang JunMa Jinping

Abstract:This article first from the orbital transportation and the conventional transportation engagement plan angle of view,elaborated solves the K most shortpath question to optimize in the public transportation wire the significance.Then most shortcircuits in Dijkstra in the algorithm foundation,creatively has introduced many P sign and many T sign records the beginning to this node K shortpath and the upper boundary,after makes the improvement the algorithm success to solve the K most shortpath.Finally uses the C language to carry on the realization to the algorithm,and had the test data to carry on the algorithm test stochastically,the test result has indicated this algorithm counting yield and the application prospect.

Keywords:Dijkstra algorithmK most shortpath Mass transit Engagement plan

【中图分类号】F542【文献标识码】C 【文章编号】1009-9646(2009)04-0029-03

1．引言

最短路径问题是网络分析中最基本的组合优化问题之一，在公交线网规划中的应用十分广泛。尤其是随着我国经济的飞速发展和城市化进程的加快，城市轨道交通已进入大发展时期。作为城市客运交通骨干，轨道交通应该与常规公交、铁路客运、公路客运、航空客运、小汽车、自行车和步行等多种交通方式密切配合，这就对城市交通的发展提出了衔接规划的要求。轨道交通的衔接规划是基于轨道交通的发展,对其沿线的交通资源配置优化和整合,达到客运交通资源最优化。其中很重要的任务就是对现有城市公交线网进行重新规划。然而在实际进行公交线网优化设计中，最短路径模型往往无法直接应用。原因主要有两个方面：首先，在线网规划中往往要求公交路线必需经过某些指定路段（地铁终点站、主要接驳站等），或者必需不经过某些指定路段（与地铁线路重复的路段、需要抽疏的路段等），从而出现了指定路线的最短路径问题。其次，在线网规划中有很多无法通过数学模型具体表达的要求，决策者往往需要多个线路设计方案，并从中进行决策，从而出现了K最短路径问题。

在非负权网络最短路径问题中，最有效的方法是Dijkstra算法［1］ 。基于这个算法，还出现了一些对Dijkstra算法的扩展和改进［2］，其中具有代表性的是TQQ、DKA、DKD ［3］、HOPA ［4］、A*算法［5］等。对于K最短路径问题，Yen提出了递推算法［6］，基于动态规划，李成江提出了复杂度为0(m+nlgn+mlgk)的算法［7］。由于Dijkstra算法的高效性和易扩展性，本文在经典的Dijkstra算法的基础上，提出了新的求解K最短路径的算法。

2.求解K最短路径的改进Dijkstra算法

对于一个具有n个节点和m条边的非负权有向网络G(V,E,L)，Dijkstra算法求解起点vs到vt的最短路径的基本思想是：如果节点序列{vs,…,vi,vt}是从vs到vt的最短路径，则{vs,…,vi}必为从vs到vi的最短路径，即从起点到某节点的最短路权一定是它全部紧前节点的最短路权与相应路权之和的最小值。在Dijkstra算法中，对每个节点进行标号，或者是试探性T标号，或者永久性P标号。T(vi)标号表示从vs到vi的最短路权的上界，是一种临时标号。P(vi)标号表示从vs到vi的最短路权，该标号一旦确定不再改变。算法的过程是不断修正节点的T标号值，将最小T标号修改为该节点的P标号，直至得到vt的P标号。

在K最短路径问题中，我们注意到从起点vs到节点vi的第k短路权，k=1,…K，一定是vs到vi的全部紧前节点的前k短路权与相应路权之和的第k小值。因此，计算节点vi的第k短路径时只需考虑vi的全部紧前节点的前k短路径。为了记录前K短路径，我们需要为每个节点设置K个标号，或者是试探性T标号，或者永久性P标号。Tk(vi)表示起点vs到vi的第k短路径路权的上界；Pk(vi)表示起点vs到vi的k最短路权值，而且一定有T1(vi)≤T2(vi)≤…≤TK(vi)，P1(vi)≤P2(vi)≤…≤PK(vi)。 在算法中，我们需要不断修正节点的K个T标号，将其中最小的T标号修改为该节点相应的P标号，直到得到PK(vi)为止。具体步骤如下：

步骤0.给vs以P标号，P1(vs)=0；

其余各点均给T标号，Tk(vi)=+∞,vi∈V/{vs},k=1,…,K。

步骤1.vi为刚得到Pk(vi)标号的节点，考虑节点vj:(vi,vj)∈E。

(1)如果Pk(vi)+lij＜Tk(vj)，确定一个q值，满足

Tq-1(vj)≤pk(vi)+lij＜Tq(vj)

(2)将Pk(vi)+lij按照q值插入vj的K个T标中，即

Tk(vj)Tk-1(vj),Tk-1(vj)Tk-2(vj),…,Tq+1(vj)Tq(vj),Tq(vj)Pt(vj)+lij

步骤2.比较所有T标号的值，将最小的T标号改为相应的P标号，即

Pk*（vj*）Tk*(vj*)=mink,j{Tk(vj)}，记录(vi,vj*)。

如果存在多个最小者时，将它们同时改为P标号；

如果Pk(vt)已经标出，算法结束；否则，返回步骤1。

3.算例求解

下面我们用一个算例来说明新算法的步骤。求解网络（如图1所示）中从v0到v4的前3短路径。

步骤0，P1(v0)=0,Tk(vi)=+∞,i=1,…,4,k=1,2,3。

迭代一.（v0）：

步骤1，考虑节点v1、v2，计算其T标号值：

P1(v0)+l01=0+2＜T3(v1)=+∞，得到q=1，T3(v1)=T2(v1)=+∞，

T2(v1)=T1(v1)=+∞，T1(v1)=P1(v0)+l01=2；

p1(v0)+l02=0+3＜T3(v2)=+∞，得到q=1，T3(v2)=T2(v2)=+∞，

T2(v2)=T1(v2)=+∞，T1(v2)=P1(v0)+l02=3。

步骤2，比较所有标号，T1(v1)=2是最小的T标号，将其改为P1(v1)=2，记录(v0，v1)。

迭代二.（v1）：

步骤1,考虑v2、v3、v4，计算其T标号值：

P1(v1)+l12=2+2＜T3(v2)=+∞，得到q=2，T3(v2)=T2(v2)=+∞，

T2(v2)=P1(v1)+l12=4；

P1(v1)+l13=2+5＜T3(v3)=+∞，得到q=1，T3(v3)=T2(v3)=+∞，

T2(v3)=T1(v3)=+∞,T1(v3)=P1(v1)+l13=7；

P1(v1)+l14=2+1＜T3(v4)=+∞，得到q=1，T3(v4)=T2(v4)=+∞，

T2(v4)=T1(v4)=+∞,T1(v4)=P1(v1)+l14=3；

步骤2，比较所有的T标号，T1(v2)=T1(v4)=3最小，P1(v2)=3，记录(v0,v2)，

P1(v4)=3，记录(v1,v4)。

迭代三.（v2）：由于v4没有紧后节点，故不考虑。

步骤1，考虑节点v1、v3、v4，计算其T标号值：

P1(v2)+l21=3+2＜T3(v1)=+∞，得到q=2，T3(v1)=T2(v1)=+∞，

T2(v1)=P1(v2)+l21=5；

P1(v2)+l23=3+3＜T3(v3)=+∞，得到q=1，T3(v3)=T2(v3)=+∞，

T2(v3)=T1(v3)=7,T1(v3)=P1(v2)+l23=6；

P1(v2)+l24=3+4＜T3(v4)=+∞，得到q=2，T3(v4)=T2(v4)=+∞，

T2(v4)=P1(v2)+l24=7；

步骤2，比较所有T标号，T2（v2）=4最小，P2(v2)=4，记录(v1,v2)。

继续迭代，直至得到P3(v4)=7，并得到从v0到v4的前三短路为分别为v0→v1→v4，v0→v2→v1→v4和v0→v2→v4，它们的路权分别为3，6和7。

迭代过程如图2所示。

4.算法测试

本算法用C语言实现，并对算法进行了测试。测试环境为：Microsoft Windows XP Service Pack 4；Inter(R) Core(TM)2Duo CPU 1.5GHz；Phys Memory：1023MB DDR2-667MHz。用伪随机数随机生成网络邻接矩阵，产生不同规模的问题，n=20,40,60,80,100，每种规模生成10个问题，分别计算前2，3，4短路径，统计计算所需的CPU时间（单位秒），结果如表1所示。

当前节点考虑节点标号最小标号修改后标号

初始值

v0p1=0

v1T1=∞,T2=∞,T3=∞

v2T1=∞,T2=∞,T3=∞

v3T1=∞,T2=∞,T3=∞

v4T1=∞,T2=∞,T3=∞

迭代一v0

v1T1=2,T2=∞,T3=∞T1=2P1=2,T2=∞,T3=∞

v2T1=3,T2=∞,T3=∞

迭代二v1

v2T1=3,T2=4,T3=∞T1=3P1=3,T2=4,T3=∞

v3T1=7,T2=∞,T3=∞

v4T1=3,T2=∞,T3=∞T1=3P1=3,T2=∞,T3=∞

迭代三v2

v1P1=2,T2=5,T3=∞

v3T1=6,T2=7,T3=∞

v4P1=3,T2=7,T3=∞

*v2P1=3,T2=4,T3=∞T2=4P1=3,P2=4,T3=∞

v4不指向任何节点

迭代四v2

v1P1=2,T2=5,T3=6T2=5P1=2,P2=5,T3=6

v3T1=6,T2=7,T3=7

v4P1=3,T2=7,T3=8

迭代五v1

v2P1=3,P2=4,T3=7

v3T1=6,T2=7,T3=7T1=6P1=6,T2=7,T3=7

v4P1=3,T2=6,T3=7T2=6P1=3,P2=6,T3=7

*v1P1=2,P2=5,T3=6T3=6P1=2,P2=5,T3=6

迭代六v1

v2P1=3,P2=4,T3=7

v3P1=3,T2=7,T3=7T3=7P1=3,P2=7,P3=7

v4P1=3,P2=6,T3=7

v3

v2P1=3,P2=4,T3=7T2=T3=7P1=3,P2=4,P3=7

v4P1=3,P2=6,T3=7T3=7P1=3,P2=6,P3=7

v4不指向任何节点

图2



表1 算法计算统计结果

n平均时间(s)最短时间(s)最长时间(s)

K=2

202.32.32.4

404.94.75.2

608.17.49.2

8010.09.710.4

10012.412.012.8

K=3

203.43.33.4

407.77.58.1

6011.511.812.1

8015.315.015.8

100内存溢出

K=4

204.64.54.7

4010.19.610.7

6015.415.015.9

80内存溢出

100内存溢出

从统计结果可知，本算法求解100个节点的网络前2短路径平均需要CPU时间12.4秒。在测试环境内存的限制下，求解前3短路径时最多可以计算80个节点的网络，而求解前4短路径时最多可以计算60个节点的网络。

根据以上计算结果，可以相信在计算机内存可以保证的条件下，能够计算200个节点的网络前5最短路径问题，满足城市公交线网优化的要求。

参考文献

［1］ Dijkstra E.W.A note on two problems in connexion with graphs ［J］.Numerische Mathematik,1959,1:269~271

［2］ Xu M.H.，Liu Y.Q.，Huang Q.L.,Zhang Y.X.,Luan G.F.An improved Dijkstra s shortest path algorithm for sparse network ［J］.Applied Mathematics and Computation,2007,185:247~254

［3］ Zhan F B.Three fastest shortest path algorithms on real road networks ［J］.Journal of Geographic Information and Decision Analysis,1997,1(1):69~82

［4］ 王景存、张晓彤、陈彬、陈和平.一种基于 Dijkstra算法的启发式最优路径搜索算法［J］.北京科技大学学报,2007，3（3）：346~350

［5］ Rothkopf H,Stark R M.Competitive bidding:A comprehensive bibliography［J］.Operations Research,1979,27(2):365~390

［6］ Yen J.Y.Finding the k shortest loopless pathes in a network ［J］,Management Science,1971,17:712~716

A*寻找最短路径算法及实现 篇7

关键词：C#语言,A*算法,寻找最短路径

1 引言

A*算法是静态路网中求解最短路径最有效的一种方法, 公式表示为f (n) =g (n) +h (n) , 其中f (n) 是从初始节点经由节点n到目标点的估价函数, g (n) 是从初始节点到n节点的实际代价, h (n) 是从n到目标节点最佳路径的估计代价。因为g (n) 是已知的, 找到最短路径关键在于估计函数h (n) 的选取, 下文h (n) 选择为n到目标节点的Hamilton距离。

2 设计思路

利用C#语言实现A*寻找最短路径算法, 如图1所示, 除了窗口界面类外设计了两个类。

一是模型类 (MapMode) , 功能为建立网格数据模型和实现A*算法。建立网格数据模型包括:建立网格节点结构模型 (Grid) , 实现模型的构造 (MapMode (int[, ]_map) ) , 初始化网格节点 (InitMapGrid () ) ;实现A*算法包括:AstarFindPath (int_startGridId, int_end GridId) , AStarFindPath_step (int_startGridId, int_endGridId) 。

二是画图类 (Draw) , 功能为绘制起点 (DrawStaPoint (int x, int y) ) , 绘制终点 (DrawEndPoint (int x, int y) ) , 绘制障碍 (DrawHinderPoint (int x, int y) ) , 绘制路径 (DrawPathPoint (int x, int y) ) , 绘制游戏场景 (DrawBackground () ) , 清空游戏背景 (BackgroundClear () ) 。

网络资料上, A*算法的搜索过程一般为创建两个表, OPEN表保存所有已生成而未考察过的节点, CLOSE表记录已经访问的节点。以下实现过程没有创建表, 而是在网格节点 (Grid) 中包含字段open (表示该节点是否在计算列表中) , 字段close (表示该节点是否在行走路径中) 。通过计算节点相邻的上下左右4个节点的f (n) 的值, 并维护节点的字段open、close的值, 在字段open为true的所有节点中选择f (n) 最小的值为下一步格子, 实现最短路径搜索。该方法仅针对网格节点进行计算和维护, 使程序流程更加清晰。

3 实现代码

3.1 窗口界面类

3.2 MapMode类

3.3 Draw类

4 结语

基于邻接矩阵的最短路径算法 篇8

关键词：最短路径,定界,活节点

0 引言

最短路径问题是给定有向图G、节点V的集合及边上的权值求源点到目标点最短距离。目前解决这个问题的算法很多, 其中最有名的算法是Dijkstra算法, 其余的方法大都是利用Dijkstra算法或者改进它, 例如:王江晴使用dijkstra算法计算动态路径, 而李洪波只是利用矩阵计算路径上的节点数, 没有涉及到路径上的权值。本文把邻接矩阵的计算用于解决最短路径, 提供了一种解决最短路径问题的新方法, 特别对于邻接矩阵是稀疏矩阵的情况下非常适合。

1 相关概念

已知:一个有向图G= (V (G) , E (G) , W (G) ) , 其中G表示图, V (G) 表示图G的节点集合, E (G) 表示图G边的集合, W (G) 表示边上路径的权值。设节点集合为V (G) = (v1v2…vn) vi为节点, E (G) = (…eij…) eij表示邻接节点vi、vj边上的权值, W (G) = (…wij…) wij表示从节点vi到vj的路径上权值累加和。求一条从v1到vn的最短有向路径的长度。

设n个顶点的邻接矩阵为:A (G) = (aij) =A

令B= (bij) 表示图G的可达性矩阵

其中:Aj= (ajst) , ajst表示矩阵A的j次幂的第s行第t列位置的元素s, t=1, …, n。

对于大规模稀疏矩阵的时候, 由于数据元素或者为1或者为零, 因此, 只需要存储非零数据元素的行和列的位置, 而不需要存储元素的值。本文将采用下面所示二元组的顺序表和行逻辑连接的顺序表存储数组元素:

2 路径构造的方法与策略

2.1 通路的构造

设A和Ar (r

2.2 中间节点的选取原则

每次从可选取的节点中, 选择一个邻接边长最短的节点, 但不构成回路。

2.3 更新活节点集

更新的方法是把刚刚添加到路径中的新节点从活节点集合中删除;同时, 把新节点的子节点添加到活节点集合中;这个过程表示为:active=active-{新添加的节点}∪{新添加的节点的子节点}。

Active表示活节点集合。

2.4 定界

定界分两种情况考虑:

情况1:如果算法计算到某一步骤, 已经产生一条从始节点v1到终节点vn的通路, 设通路的有向路径的长度为w1。而另一条正在搜索的路路径长度为w2, 不管正在计算的路径是否已经搜索到通路, 如果满足:w1≤w2, 那么这条正在搜索的路径应该去掉;如果满足w1>w2, 那么搜索继续。

情况2:设vj有k个分支点vj+1, …vj+k, 如下图1所示, 设ejj+1是其中邻接边长最短的, vn到vj比目前找出来的最短路径短, 而从vn到vj+1比目前的最短路径要长, 那么, 按照情况1, vj+1应该不在最优路径上, 应该删除, 事实上这时经过vj的每一条路径都比经过vj, vj+1要长, 所以更应该删除, 因此vj应该被删除。

2.5 计算路径长度

设第一搜索点为vn, 已经搜索到vi, 而vj是要加到这条路径上的vi的邻接点, 那么:wnj=wni+eij。

另外, 本算法采取从最后一个节点逆向搜索节点, 本算法假设寻找vi到vn的最短路径, 对于其余情况也是类似的。

3 搜索算法

初始化:给A赋初值

第一步计算矩阵A的幂

令活节点集

active={vi│vi为指向vn的邻接点, 并且vi在起点到终点的通路上}

第二步深度搜索优先, 寻找第一条通路。按深度搜索优先原则, 根据2.1和2.2增加邻接边, 按2.3更新活节点集合, 按照2.5计算路径长度, 重复这个步骤直到找到第一条从源点到目标点的通路, 并且令这条路是当前的最短路径。

第三步宽度搜索优先, 选择新的分支点。按宽度搜索优先原则, 根据2.1和2.2增加邻接边;按照2.5计算准路径的长度, 转第四步。

第四步定界。如果准路径长度大于当前最短路径, 根据定界2.4删除相应的活节点;如果准路径长度小于等于当前最短路径的长度, 按2.3更新活节点集合active, 然后分两种情况:

(1) 准路径是从源点到目标点的通路, 准路径为新的当前最短路径;

(2) 准路径不是从源点到目标点的通路, 则转第三步。

第五步输出最短路径节点集和最短路径长度。

4 实例

上图2为一个有向路径图, 求标号为0的节点v0到标号为4的节点v4的最短距离。

首先给出邻接矩阵:

计算A的幂其中乘法为普通乘法, 加法为逻辑相加:

有:a04=1, a204=1, a304=1

对应于a304=1, 有a202=1, a24=1, 所以v2、v4为邻接点, e24=10

对应于a204=1, 有a03=1, a34=1所以v3、v4为邻接点, e34=60

对应于a04=1, 有e04=100

min{e04, e24, e34}=e24=10, 所以v4的邻接点为v2, 对应active={v1, v3}。

以v2进行深度搜索得到节点v1, e12=50, 继续得到节点v0, e01=10所以通路为:T={v0, v1, v2, v4}, w0, 4=70 active={v3}。

第三步从active={v3}中取出v3, 而w34=60, w34+w03=90>70, 舍弃e04=100>w04, 舍弃。

所以:T={v0, v1, v2, v4}, w0, 4=70 active={v3}。

5 结束语

从上面的实例可以看出v5虽然与v4邻接边长最短, 但是, 由于它不在从目的点到源点的通路上, 所以v5不在活节点集合中, 这样会减少很多搜索的计算量, 故, 本算法的第一条是只有在通路上的节点才是活节点。本算法与Dijksta算法不同之处在于:Dijkstra算法只要跟源点是连通的点都是活节点, 而本算法只有从源点到目的点通路上的点才是活节点;Dijkstra算法把源点到其余每一点的最短路径都求出来, 本算法直接求源点到每个目的点的最短路径, 因此从这个角度来说本文节省了大量的计算量。当然由于要计算矩阵的幂, 会增加计算量, 并且一般情况下, 这个计算量很大;但是, 当邻接矩阵是稀疏矩阵时, 矩阵幂的计算量会大大减少。因此本文算法适合于邻接矩阵是稀疏矩阵的情况。

参考文献

[1]吴晓红.关于最短路径问题的一种有效算法[J].系统工程与电子技术, 1999 (11) .

[2]段凡丁.关于最短路径的SPFA快速算法[J].西南交通大学学报, 1994 (2) .

[3]伍建华.单源最短路径问题的Seidel迭代法[J].计算机应用, 2001 (8) .

[4]乐阳, 龚健雅.Dijkstra最短路径算法的一种高效率实现[J].武汉测绘科技大学学报, 1999 (3) .

[5]孙强.Dijkstra的一种改进算法[J].计算机工程与应用, 2003 (3) .

[6]王江晴.动态车辆路径问题中的实时最短路径算法研究[J].武汉理工大学学报 (交通科学与工程) , 2007 (1) .

[7]李洪波.Floyd最短路径算法[J].计算机工程与应用, 2006 (34) .

经纬网格寻址中最短路径算法优化 篇9

对经纬网格进行二维剖分, 进而利用最短路径的方法, 求两个之间的最短距离, 是解决天气数值预报中模式计算的核心问题。进行最短路径的计算, 就必须首先将其按结点和边的关系抽象为图的结构, 这称为构建网络的拓扑关系。只有建立了拓扑关系, 才能进行网络路径分析。于是最短路径计算实现的关键在于网络拓扑结构的建立和高效能最短路径算法。文中针对解决实际最短路径问题较为有效的Dijkstra算法进行并行优化。即如图1所示从源点甲地出发, 到达图上丁地的最短路径。

2 流程伪代码

这里采用了贪心的策略, 利用宽度优先一层层搜索, 直到遍历所有结点或已经找到最短路径。算法伪代码如下:

2.1 优化一

对Dijkstra (G, w, s) 取最短路径是运用map-reduce方法, 对D的更新在main函数中进行。

2.2 优化二

对阵列D进行更新的时候运用map-reduce方法, 对D的更新采用了一种单map多个reduce的暴力方法:

Step1:用map函数获取D[i]!=INFINITY且没有取得最短路径的所有节点及其邻接节点的信息。

Step2:采用多个reduce函数同时对阵列D进行更新, 输出 (路径长, 节点) 的元组, 通过后台进行排序, 获取一次迭代得到的最短路径。

3 实验结果

程序都进行了相对严谨的测试。对于不同N值的程序得到了相同的结果, 跟串行程序的结果也一样。程序结果列举如图2所示。图1为N=10时, 零点到所有顶点的最短路径结果显示。根据上方的邻接矩阵可以很容易匹配上下面的打印结果。图3为N=1024时的打印结果, 两个程序结果一致, 另外本人还写了一个串行的求单点最短路径的程序, 输出结果均与之相符。

4 结论

依据最短路径算法分析, 采用贪心策略和MapReduce编程模型实现路径计算过程中优先级队列的一系列操作, 从而提高算法的计算性能。解决数值预报中地理空间范围内两点间的最短路径求解难题, 该结果的合理应用为数值预报模式中最短路径求解提供参考依据。

摘要：最短路径分析地理信息系统中的空间经纬网络寻址中的计算瓶颈, 对其算法进行优化很有必要。针对最短路径中经典的Dijkstra算法, 采用贪心策略和MapReduce编程模型实现路径计算过程中优先级队列的一系列操作, 从而提高了算法的计算性能。

最短路径优先 篇10

EXCEL作为日常办公软件Office的套件之一,除了常用的报表处理功能外,还有另外一个强大的功能就是在管理决策和优化决策方面的应用。对于处理最优化问题,EXCEL可以说是容易理解且操作方便的强大工具,同事也避免了非专业人员不熟悉专业处理软件等棘手问题。最短路径问题求解方法不仅可以直接应用于实际生产中出现的问题,比如线路安排、管道铺设等,还可以作为一种解决方法来解决其他的最优化问题。对于规模不大的最短路径求解问题,可以利用EXCEL软件解决。

文章以某公司开发产品要求总时间最短的案例作为最短路径问题的研究对象,应用EXCEL软件进行分析和求解,对解决其他最短路径问题可以达到举一反三的效果。

1 最短路径问题

最短路径问题属于最优化问题的一种,同时也是线性规划问题的特殊类型,目的是从一个网络中寻找从起点到某个节点之间一条最短的路线。在一些实际应用中,最短路径问题的目的就是求解总距离最短,目标是使得一系列活动的总时间最短,通过建立线性规划模型并求解。

2 应用案例

某公司正在开发一款新产品,分为4个阶段,分别是设计、研发、生产和销售。管理者希望在有限的预算内,更快地将产品推向市场,占领主导地位。开发过程中每个阶段的实施水平都可分为正常水平和紧急水平,现在考虑可以提高实施水平使得产品可以加速完成。表1列出了在这些水平下每个阶段所需的时间。

公司计划为该项目拨款1000万元,每个阶段的费用如表2所示。

(单位:万元)

在最短路径问题中,管理者最希望得到的结果是每个阶段选择特定水平进行开发,在有限的开发经费内保证总时间最少。根据最优化方法,最短的开发总时间为目标函数,约束条件则是要遵循的相关规则,解决方法是利用EXCEL线性规划求解。

因为该网络存在超过一个的结束节点,不满足最短路径问题有且仅有一个目标的要求,所以添加了一个虚拟的目的地T,使得网络中仍然只有一个共同的终点,并为这些节点之间插入长度为0的弧。图1中除了虚拟的目的地以外,每个节点都由两个数字表示,其中第一个数字表示当前完成的阶段,第二个数字表示剩余的资金(百万元)。每条弧表示某阶段以某种水平进行工作,弧上的数字表示花费的时间。选择时间作为弧长的尺度是因为目标是为了使4个阶段所花费的总时间最少。该网络得到最优解时的最短路径就是使完成所有阶段总时间最短的方案。

2.1 EXCEL建立模型并求解

假设xij表示弧上的数字,即完成该阶段所花费的时间,yij表示决策变量。决策变量就是最优解,即最短路径是否通过该弧,通过为1,未通过为0。那么要使时间总和f最小,就可以列出这样的式子:

约束条件:,其中度数和表示最短路径通过节点的出度减去入度。起点的度数和为1,终点的度数和为-1,其余节点的度数和为0。

根据该网络规划问题为基础得到的结果如图2所示。

其中B列和C列列出了所有的弧,D列用0或1表示是否为最优解,F列表示了每一条弧所对应的时间。D24单元格表示目标函数,即所花费的时间最短,在EXCEL中通过函数D24=SUMPRODUCT(运输数量,价格/容量)计算。H列列出了所有的节点,I列表示每个节点出度减去入度的值,在I3:I16中输入的等式用了两个SUMIF函数的差来表示出度减去入度,第一个SUMIF计算该节点的出度,第二个SUMIF计算该节点的入度,两者之差就是度数和,如I3=SUMIF(起点,H3,是否最优解)-SUMIF(终点,H3,是否最优解),I4=SUMIF(起点,H4,是否最优解)-SUMIF(终点,H4,是否最优解),以此类推。

在图3中,将“设置目标”为目标函数单元格,选择求解最小值,可变单元格为(D3∶D22)。约束条件出度-入度=度数和表示为I3∶I16=K3∶K16。为了保证得到的最优解满足非0即1的条件,要勾选“使无约束变量为非负数”。另外在选择求解方法中选择单纯线性规划。通过求解,就得到了图4中的答案,总时间最少需要16个月,比正常完成该产品提前了4个月。

图4是得到最优解的电子表格模型,可以看到在D列中为1的即是最短路径通过的弧,于是可以画出该产品生产的最短时间图(见图5)。可以看到设计阶段采用了紧急水平,研发阶段采用了正常水平,生产阶段采用了正常水平,销售阶段采用紧急水平。

3 结语

本文介绍了EXCEL线性规划在求解最短路径问题中的应用,通过对最短路径问题的扩展案例进行详细介绍,使用者还可以举一反三地解决最优化问题中最大流、最小支撑树等问题。对于管理者来说,不需要了解复杂的求解过程,只需把数据、目标函数、约束条件等在EXCEL电子表格中设置好,即可以直接求得所需结果,符合管理者的实用价值,还可以使EX⁃CEL软件的使用价值大大提高。

参考文献

[1]朱德通.最优化模型与实验[M].上海:同济大学出版社,2003.

[2]顾运筠.EXCEL规划求解的两类应用[J].计算机应用与软件,2005(1):137-139.

[3]付木亮,余小飞.基于EXCEL的网络最短路问题的求解[J].技术与市场,2010(6):18-19.

[4]弗雷德里克,希利尔,马克,等.数据模型与决策[M].任建标,译.北京:中国财政经济出版社,2003.

几种最短路径的算法及比较 篇11

为了方便我们对最短路径问题的研究, 下面给出其定义。

定义:在最短路径问题中, 给出的是一张有向加权图G= (V, E) , 在其上定义的加权函数w:E→R为边到实型权值的映射。路径p= (v0, v1, …vk) 的权指的是其组成边的所有权值之和:

定义从u到v的最短路径的权为:

2. 单源最短路径算法

单源最短路径问题所求的是:从某结点s到其它所有结点的最短路径。这是最短路径问题的基础问题, 其它的最短路径问题都可以转化为单源最短路径问题进行求解。

2.1 松弛技术 (Relax) [1]

在每个单源最短路径算法中都运用了松弛技术。松弛一条边就是试图找到一条比当前已知路径更短的边。对每一结点v∈S, 我们用d[v]来表示从源s到v当前已知的最短路径的权的上界, 称之为最短路径估计。用pre[v]来表示当前最短路径估计中v前面的点。

松弛一条边 (u, v) 的过程包括测试我们是否可能通过结点u对迄今找出的到v的最短路径估计进行改进, 如果可能则更新d[v]和pre[v]。

注意:单源最短路径的每个算法都要先调用初始化过程, 然后重复松弛过程。

2.2 Dijkstra算法[2]

Dijkstra算法解决了有向加权图的最短路径问题, 它可以解决单源最短路径问题, 如果以每个点作为源都做一次Dijkstra算法, 则可以求出每对结点间的最短路径。该算法的条件是所有边的权值都非负, 这个重要的条件使得我们用贪心得到该算法。

2.2.1 算法描述

设置一结点集合S, 从源s到集合S中所有点的最短路径均已求出。算法反复挑选出最短路径估计为最小的结点u加入S集合, 并对所有离开结点u的边进行松弛操作, 直到所有结点进入集合。

2.2.2 算法分析

这里的D要用优先队列实现, 需用到删除最小 (Delete Min) 与减值 (Decrease Key) 的操作。假设用普通的队列实现则算法复杂度为O (V2) 。如果用Fibonacci堆来实现优先队列则算法复杂度为O (|E|+|V|lg|V|) 。

2.3 Bell Man-Ford算法[3]

如果一个图包含负权圈, 那么这个图就不存在最短路径。在Dijkstra算法中我们假定不存在负权边, 而在Bellman-Ford算法中则可以存在负权边:找到从源s到所有点的最短路径或确定存在负权圈。

2.3.1 算法描述

对于每一结点s∈S, 逐步减小从源s到v的最短路径估计d[v]直至其到达实际最短路径的权。最多进行|V[G]|-1次松弛操作。算法返回True当且仅当图中不存在负权圈。

2.3.2 算法分析

该算法的时间复杂度为O (VE) 。

2.3.3 算法优化

该算法名为Shortest path faster algorithm4, SPFA其实就是Bellman-Ford的一种队列实现, 减少了冗余, 即松驰的边至少不会以一个d为∞的点为起点。

2.3.4 复杂度分析

SPFA在形式上和宽度优先搜索非常类似, 不同的是宽度优先搜索中一个点出了队列就不可能重新进入队列, 但是SPFA中一个点可能在出队列之后再次被放入队列, 也就是一个点改进过其它的点之后, 过了一段时间可能本身被改进, 于是再次用来改进其它的点, 这样反复迭代下去。设一个点用来作为迭代点对其它点进行改进的平均次数为k, 有办法证明对于通常的 (不含负圈, 较稀疏) 情况, k在2左右。算法复杂度理论上同Bellman-Ford, O (VE) , 但实际上却是O (k E) 。

4. 每对结点间的最短路径算法

最直接的方法是把每个结点都作为源做一次单源最短路径算法, 我们用Floyd-Warshall算法来解决这类问题。Floyd算法是一种用来解决关于图G (V, E) 间每对结点间的最短路径问题的算法, 可以存在负权边, 但我们假定不存在负权圈。

4.1 算法描述

本质就是用动态规划:

Gk (u, v) 表示u到v的不经过k, k+1, ..., n结点 (除u, v外) 时, 从u到v的最短路长。下面用归纳法证明:

k=1显然成立。

假设对k成立, 下面考虑k+1的情况;

从u到v且不通过k+1, ..., n

节点的最短路有两种可能: (1) 不经过k节点, 即为Gk (u, v) ; (2) 经过k节点, 即为Gk (u, k) +Gk (K, v)

由于第k+1次迭代过程中, 不会影响k次的迭代结果, 使用O (V2) 的空间即可。二维数组pre (u, v) , 记录u到v, 最后经过哪个k的迭代。

4.2 算法分析

时间复杂度为O (V3) , 空间复杂度为O (V2) 。

5. Johnson算法

5.1 算法描述

本算法适用于稀疏图。它是Dijkstra和Bellman-Ford算法的综合应用。

本算法用了权值改造 (reweighting) 技术。若图的权值非负, 则对于每个结点用一次Dijkstra算法, 就可以求出所有顶点对间最短路。若图中有负权, 但没有负圈, 则可以把权值W改造成W', W'非负, 使得能够使用Dijkstra算法。

(1) 给图G, 加一个新结点v0。对v0用Bellman-Ford, 若有负, 则结束;否则可以得到h (v) , 即v到v的最短路长。O (VE)

(2) 对于所有边 (u, v) , 权值改造, 即令w' (u, v) =w (u, v) +h (u) -h (v) 。O (m)

(3) 对于每个结点, 用一次以Fibonacci Heap为优先队列的Dijkstra算法, 可求出v与其他顶点的最短路。O (Vlog V+E) *O (V)

权值改造满足两个原则: (1) W'非负; (2) 对于任意顶点u, v, p是在W上的u到v的最短路当且仅当p是在W'上的u到v的最短路。下证w' (u, v) =w (u, v) +h (u) -h (v) , 满足以上两个原则:

(1) 由于h是v0到v的最短路长, h (u) +w (u, v) ≥h (v) , 所以w' (u, v) =w (u, v) +h (u) -h (v) ≥0。

(2) 令路径p= (v1, v2, L, vn) , 则

w' (p) 只与w (p) 以及首尾的标号h有关, 不影响w' (p) 的决策。所w (p) 是最短路长当且仅当w' (p) 是最短路长, 且不影响最短路p。

6.结论

在单源最短路径问题中, Dijkstra算法适合于处理权值都为正的图, 而Bellman则适用于含有负权的图, 并且可以处理负权圈。改进后的SPFA是最快的。

在有向无环图中有特殊的算法, 可以在的时间内实现。

在所有点之间的最短路径问题中, 我们可以多次运行SPFA算法。但在完全图中Floyd算法则更为优秀, 并且实现简单。

摘要：最短路径问题是图论中一个非常有实际意义的问题, 在实际生活中的各种规划设计问题中及数据挖掘中都有重要的作用。本文着重介绍了用计算机编程语言实现单源最短路径算法与每对结点间的最短路径算法, 并作了简单比较。

关键词：Relax,Dijkstra,Bellman,有向无环图上的最短路,Floyd-Warshall,Johnson

参考文献

[1].Herbert S.Wilf.Algorithms and Complexity.University of Pennsylvania, 1994

[2].Thomas H.Cormen, Charles E.Leiserson, Ronald L.Rivest, and Clifford Stein.Introduction to Algorithms.MIT Press, Cam bridge, MA, 2001

[3].Michael Sipser.Introduction to the Theory of Computation, second edi-tion.Thomson, USA, 2006.