更新时间: 2016-09-23 09:19:44       分类: 算法


开始图论学习的第二部分:最短路径。

由于知识储备还不充足,暂时不使用邻接表的方法来计算。

最短路径主要分为两部分:多源最短路径和单源最短路径问题

多源最短路径:

介绍最简单的Floyd Warshall算法:

思路如下:把所有从顶点i到j可能经过的顶点一一枚举,不断更新从i到j的最小权值:d[i][j] = min{d[i][j],d[i][k]+d[k][j]},是一种动规的思想

局限性:不能处理有负权回路(负圈)的情况,而且一般是使用邻接矩阵的方式来实现。

优劣性:思路简单,核心代码简洁易懂,但是时间复杂度为O(N^3)效率较差,适合处理小范围数据。

核心代码只有5行:

for (int k = 1; k <= n; k++)
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (e[i][j]>e[i][k] + e[k][j])
                e[i][j] = [i][k] + e[k][j];  

在情况不是特别复杂的情况下也可以用来求解单源最短路径问题

单源最短路径:

先介绍简单的Dijkstra算法

核心思路:假设计算从顶点1到其余各顶点的最短路径。先用一个一维数组dis储存1号顶点到其余各顶点的初始路程(这时每个值被称为估计值),找到一个离1的距离最小的顶点,比如2,那么dis[2]的值就成为确定值(因为顶点1到其它顶点的距离都更长,所以从其他顶点中转肯定没有直接从1走到2短,那么这个值就是1到2的最短路径)。现在我们有了一个确定值dis[2],就开始利用这个值尝试去更新1到其他顶点的最短距离(说白了就是都从2绕一下试试),更新完成后我们就不再管顶点2,从顶点3开始再搜索一个到1距离最短的点(这时候用的是已经更新过的值),不断重复上述的过程,直到所有的估计值都变成确定值。

局限性:不能应对有负权边的情况

优化:当边数较少时(稀疏图),使用邻接表效率会比邻接矩阵更高(后续会给出,这里先用邻接矩阵写)

要注意的是:我们使用两个集合P和Q来区别已经确定的顶点和待确定的顶点(用book数组来标记)

整体代码如下:(求顶点1到其他顶点的最短路径)

/*Dijkstra算法用邻接矩阵实现,求一号顶点到其他各顶点的最短路径*/
# include<iostream>

using namespace std;

int dis[101],book[101];//dis数组存放估计值,最后变为确定值。book数组用于标记顶点是否被处理过

int e[101][101];//邻接矩阵

const int INF = 99999999;//INF用于表示正无穷

int main()
{
    int n, m;//n为顶点数目,m为边的数目
    int t1, t2, t3;
    int temp;

    //初始化邻接矩阵:
    for (int i = 1; i <= 100; i++)
        for (int j = 1; j <= 100; j++)
        {
            if (i == j)
                e[i][j] = 0;
            else
                e[i][j] = INF;
        }

    //读入边:
    for (int i = 0; i < m; i++)
    {
        cin >> t1 >> t2 >> t3;//表示从顶点t1到顶点t2有一条权为t3的边
        e[t1][t2] = t3;//这里是有向图
    }

    //初始化dis数组:
    for (int i = 1; i <= n; i++)
        dis[i] = e[1][i];
    
    //初始化book数组,说明dis[1]已经是确定值了
    book[1] = 1;

    //Dijkstra算法核心:
    for (int i = 1; i < n; i++)//只用执行n-1次,最后一个点一定是确定的
    {
        //第一步:找到现在距离顶点1最近的点
        int min = INF;
        for (int j = 1; j <= n; j++)
        {
            if (book[j] == 0 && dis[j] < min)
            {
                min = dis[j];
                temp = j;//记录
            }
            
            book[temp] = 1;

            for (int i = 1; i <= n; i++)
            {
                if (e[temp][i] < INF)
                {
                    if (dis[i]>dis[temp] + e[temp][i])
                        dis[i] = dis[temp] + e[temp][i];
                }
            }
        }
    }

    //输出:
    for (int i = 1; i <= n; i++)
        cout << dis[i] << " ";


    //system("pause");

    return 0;
}

评论

还没有评论