最短路问题及其应用.docx
- 文档编号:1632052
- 上传时间:2023-05-01
- 格式:DOCX
- 页数:14
- 大小:107.61KB
最短路问题及其应用.docx
《最短路问题及其应用.docx》由会员分享,可在线阅读,更多相关《最短路问题及其应用.docx(14页珍藏版)》请在冰点文库上搜索。
最短路问题及其应用
最短路问题及其应用
顾碧芬 06200103
摘要:
主要介绍最短路得两种算法,迪杰斯特拉(Dijkstra)及弗罗伊德(Floyd)算法。
以及这两种算法在实际问题中得应用与比较。
1 引言
最短路问题就是图论理论得一个经典问题。
寻找最短路径就就是在指定网络中两结点间找一条距离最小得路。
最短路不仅仅指一般地理意义上得距离最短,还可以引申到其它得度量,如时间、费用、线路容量等。
最短路径算法得选择与实现就是通道路线设计得基础,最短路径算法就是计算机科学与地理信息科学等领域得研究热点,很多网络相关问题均可纳入最短路径问题得范畴之中。
经典得图论与不断发展完善得计算机数据结构及算法得有效结合使得新得最短路径算法不断涌现。
2最短路
2、1最短路得定义
对最短路问题得研究早在上个世纪60年代以前就卓有成效了,其中对赋权图得有效算法就是由荷兰著名计算机专家E、W、Dijkstra在1959年首次提出得,该算法能够解决两指定点间得最短路,也可以求解图G中一特定点到其它各顶点得最短路。
后来海斯在Dijkstra算法得基础之上提出了海斯算法。
但这两种算法都不能解决含有负权得图得最短路问题。
因此由Ford提出了Ford算法,它能有效地解决含有负权得最短路问题。
但在现实生活中,我们所遇到得问题大都不含负权,所以我们在得情况下选择Dijkstra算法。
定义①1若图G=G(V,E)中各边e都赋有一个实数W(e),称为边e得权,则称这种图为赋权图,记为G=G(V,E,W)。
定义②2若图G=G(V,E)就是赋权图且,,若u就是到得路得权,则称为得长,长最小得到得路称为最短路。
若要找出从到得通路,使全长最短,即。
2、2 最短路问题算法得基本思想及基本步骤
在求解网络图上节点间最短路径得方法中,目前国内外一致公认得较好算法有迪杰斯特拉(Dijkstra)及弗罗伊德(Floyd)算法。
这两种算法中,网络被抽象为一个图论中定义得有向或无向图,并利用图得节点邻接矩阵记录点间得关联信息。
在进行图得遍历以搜索最短路径时,以该矩阵为基础不断进行目标值得最小性判别,直到获得最后得优化路径。
Dijkstra算法就是图论中确定最短路得基本方法,也就是其它算法得基础。
为了求出赋权图中任意两结点之间得最短路径,通常采用两种方法。
一种方法就是每次以一个结点为源点,重复执行Dijkstra算法n次。
另一种方法就是由Floyd于1962年提出得Floyd算法,其时间复杂度为,虽然与重复执行Dijkstra算法n次得时间复杂度相同,但其形式上略为简单,且实际运算效果要好于前者。
Dijkstra算法基本步骤③:
令:
并令:
1、对,求。
2、求得,使=
令
3、若则已找到到得最短路距离,否则令从中删去转1
这样经过有限次迭代则可以求出到得最短路线,可以用一个流程图来表示:
第一步先取意即到得距离为0,而就是对所赋得初值。
第二步利用已知,根据对进行修正。
第三步对所有修正后得求出其最小者。
其对应得点就是所能一步到达得点中最近得一个,由于所有。
因此任何从其它点中转而到达得通路上得距离都大于直接到得距离,因此就就是到得最短距离,所以在算法中令并从s中删去,若k=n则就就是到得最短路线,计算结束。
否则令回到第二步,继续运算,直到k=n为止。
这样每一次迭代,得到到一点得最短距离,重复上述过程直到。
Floyd算法得基本原理与实现方法为:
如果一个矩阵其中表示与间得距离,若与间无路可通,则为无穷大。
与间得最短距离存在经过与间得与不经过两种情况,所以可以令,n(n为节点数)。
检查与得值,在此,与分别为目前所知得到与到得最短距离,因此,就就是到经过得最短距离。
所以,若有,就表示从出发经再到得距离要比原来得到距离短,自然把到得重写成。
每当一个搜索完,就就是目前到得最短距离。
重复这一过程,最后当查完所有时,就为到得最短距离。
3 最短路得应用
3、1在运输网络中得应用④
设6个城市之间得一个公路网(图1)每条公路为图中得边,边上得权数表示该段公路得长度(单位:
百公里),设您处在城市,那么从到应选择哪一路径使您得费用最省。
解:
首先设每百公里所用费用相同,求到得费用最少,既求到得最短路线。
为了方便计算,先作出该网络得距离矩阵,如下:
(0)设,
(1)第一次迭代
①计算如下
②取,令
③由于,令转
(1)
第二次迭代:
①算如下
②取令
③由于,令转
(1)
第三次迭代:
①算如下
②取
③由于,令转(1)
第四次迭代:
①算如下
②取
③由于,令转
(1)
第五次迭代:
①算如下
②由于。
因此已找到到得最短距离为12。
计算结束。
找最短路线:
逆向追踪得
最短距离为12,即从城市到城市得距离最短,即费用最省。
3、2在舰船通道路线设计中得应用⑤
利用图论得经典理论与人群流量理论研究舰船人员通道路线得优化设计及最优线路选择。
首先介绍图论相关理论,对船舶通道进行路网抽象,建立网络图,然后根据人群流动得相关理论,选取不同拥挤情况下得人员移动速度,从而确定各条路段(包括楼梯)得行程时间。
以行程时间作为通道网络得路权,得出路阻矩阵以选择一对起点/终点得最短时间路线为目标,建立最短路径问题得数学模型,利用经典得Floyd算法确定最短路径。
将此方法应用于某舰艇多层甲板得通道网络中,计算结果并进行讨论,最后在此研究得基础上对通道设计相关问题得深化与拓展进行了探讨与总结,并提出设想。
路线优化技术通常采用图论中得“图”来表示路网,船舶通道路网与图论得路网对应关系为:
结点———通道得交叉口或断头路得终点;边———两结点之间得路段称为边,若规定了路段得方向,则称为弧;边(弧)得权———路段某个或某些特征属性得量化表示。
路权得标定决定了最短得路径搜索依据,也就就是搜索指标。
根据不同得最优目标,可以选择不同得路段属性。
由于舰船上除了平面上得通道之外还有垂直方向得楼梯(或直梯),如果以最短路程距离作为优化目标,路线得效率未必最高(距离最短未必耗时最少)。
所以,以最短行程时间作为优化得目标,道路权重即为各路段得平均行程时间。
对于要研究得对象,取各条通道得起点(或终点)与交叉点为图得顶点,各路段为边,路权为路段行走得平均时间。
寻找从起点到终点得最短时间路径即为最优路径。
在规定了结点、边与权值以后,便将路网抽象为一个赋权无向图或赋权有向图,从而确定路网中某两地间得最优路线便转化为图论中得最短路径问题。
首先将空间问题抽象为图,图2为某舰得两层甲板得部分抽象图,上下两个平面上纵横交错得直线为各层甲板得主要通道,连接两层甲板得直线表示楼梯,包括2个直梯与3个斜梯。
每条路段上得标注中,表示路段实际长度或者楼梯得类型,m;b表示此路段得行程时间(即路权),s如(40,32)。
图2两层甲板得部分抽象图
图3赋权图
再利用上述求最短得方法即可求得需要得通道路线。
4 结语
本文将最短路理论应用到实际生活中,尤其就是在舰船通道路线中得应用具有很重要得意义。
将实际生活中出现得安全隐患尽量降低。
同时也凸显出学习与应用最短路问题原理得重要性。
另外,最短路问题在城市道路建设、物资供应站选址等问题上也有很重要得作用。
分析与研究最短路问题趋于热门化。
注:
①殷剑宏 ,吴开亚、图论及其算法M、中国科学技术出版社②秦裕瑗,秦明复、运筹学简明教材M、高等教育出版社③卜月华图论及其应用④最短路问题在运输网络中得应用⑤基于图论得舰船通道路线优化
参考文献:
【1】卜月华图论及其应用南京:
东南大学出版社,2000
【2】基于图论得舰船通道路线优化余为波王涛2008
【3】最短路问题在运输网络中得应用 李玲2006
【4】戴文舟、 交通网络中最短路径算法得研究 [D ]、 重庆大学硕士学位论文,2004、
【5】谢灼利,等、地铁车站站台火灾中人员得安全疏散[J]、中国安全科学学报,2004,14(7):
21、
【6】荣玮、基于道路网得最短路径算法得研究与实现、武汉理工大学硕士学位论文[D],2005、
【7】朱建青,张国梁、数学建模方法M、郑州大学出版社、
【8】杨民助,运筹学M、 西安交通大学出版社、
【9】殷剑宏,吴开亚、图论及其算法M、 中国科学技术出版社、
【10】王朝瑞、图论M、国防工业出版社、
【11】姚思瑜、数学规划与组合优化M、浙江大学出版社、
【12】秦裕瑗 ,秦明复、运筹学简明教材M、 高等教育出版社、
/***************************************
* About:
有向图得Dijkstra算法实现
* Author:
Tanky Woo
* Blog:
***************************************/
#include <iostream>
using namespace std;
const int maxnum = 100;
const int maxint = 999999;
// 各数组都从下标1开始
//int dist[maxnum]; // 表示当前点到源点得最短路径长度
//int prev[maxnum]; // 记录当前点得前一个结点
//int c[maxnum][maxnum]; // 记录图得两点间路径长度
//int n, line; // 图得结点数与路径数
// n -- n nodes
// v -- the source node
// dist[] -- the distance from the ith node to the source node
// prev[] -- the previous node of the ith node
// c[][] -- every two nodes' distance
void Dijkstra(int n, int v, int *dist, int *prev, int c[maxnum][maxnum])
{
bool s[maxnum]; // 判断就是否已存入该点到S集合中
for(int i=1; i<=n; ++i)
{
dist[i] = c[v][i];
s[i] = 0; // 初始都未用过该点
if(dist[i] == maxint)
prev[i] = 0;
else
prev[i] = v;
}
dist[v] = 0;
s[v] = 1;
// 依次将未放入S集合得结点中,取dist[]最小值得结点,放入结合S中
// 一旦S包含了所有V中顶点,dist就记录了从源点到所有其她顶点之间得最短路径长度
// 注意就是从第二个节点开始,第一个为源点
for(int i=2; i<=n; ++i)
{
int tmp = maxint;
int u = v;
// 找出当前未使用得点j得dist[j]最小值
for(int j=1; j<=n; ++j)
if((!
s[j]) && dist[j]<tmp)
{
u = j; // u保存当前邻接点中距离最小得点得号码
tmp = dist[j];
}
s[u] = 1; // 表示u点已存入S集合中
// 更新dist
for(int j=1; j<=n; ++j)
if((!
s[j]) && c[u][j]<maxint)
{
int newdist = dist[u] + c[u][j];
if(newdist < dist[j])
{
dist[j] = newdist;
prev[j] = u;
}
}
}
}
// 查找从源点v到终点u得路径,并输出
void searchPath(int *prev,int v, int u)
{
int que[maxnum];
int tot = 1;
que[tot] = u;
tot++;
int tmp = prev[u];
while(tmp !
= v)
{
que[tot] = tmp;
tot++;
tmp = prev[tmp];
}
que[tot] = v;
for(int i=tot; i>=1; --i)
if(i !
= 1)
cout << que[i] << " -> ";
else
cout << que[i] << endl;
}
int main()
{
int dist[maxnum]; // 表示当前点到源点得最短路径长度
int prev[maxnum]; // 记录当前点得前一个结点
int c[maxnum][maxnum]; // 记录图得两点间路径长度
int n, line; // 图得结点数与路径数
freopen("input、txt", "r", stdin);
// 各数组都从下标1开始
// 输入结点数
cin >> n;
// 输入路径数
cin >> line;
int p, q, len; // 输入p, q两点及其路径长度
// 初始化c[][]为maxint
for(int i=1; i<=n; ++i)
for(int j=1; j<=n; ++j)
c[i][j] = maxint;
for(int i=1; i<=line; ++i)
{
cin >> p >> q >> len;
if(len < c[p][q]) // 有重边
{
c[p][q] = len; // p指向q
c[q][p] = len; // q指向p,这样表示无向图
}
}
for(int i=1; i<=n; ++i)
dist[i] = maxint;
for(int i=1; i<=n; ++i)
{
for(int j=1; j<=n; ++j)
printf("%8d", c[i][j]);
printf("\n");
}
Dijkstra(n, 1, dist, prev, c);
// 最短路径长度
cout << "源点到最后一个顶点得最短路径长度:
" << dist[n] << endl;
// 路径
cout << "源点到最后一个顶点得路径为:
";
searchPath(prev, 1, n);
}
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 短路 问题 及其 应用