最短路问题及其应用.doc

最短路问题及其应用
顾碧芬 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:     www.WuTianQ
***************************************/

#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);
}

（范文素材和资料部分来自网络，供参考。可复制、编制，期待你的好评与关注）

12 / 12