算法与数据结构(九) 图论:最短路径问题

最路径问题 Shortest Path

一个节点到另一个节点最短的路径。路径规划问题。

  • 路径规划
  • 工作任务规划

对于无权图进行广度优先遍历就是求出了一个最短路径。

最短路径树

从起始点到其他节点路径最短的树

无权图的最短路径。

松弛操作。找到更短路径。

dijkstra 单源最短路径算法

前提:图中不能有负权边 复杂度 O( E log(V) )同最小生成树

最小索引堆

从源点能到达的点中最短的路径。 图中不能有负权边

经过2到达1和经过2到达3比原来记录的值小,所以松弛更新。

经过1到4更短

IndexMinHeap

代码实现:

// Dijkstra算法求最短路径
template<typename Graph, typename Weight>
class Dijkstra{

private:
    Graph &G;                   // 图的引用
    int s;                      // 起始点
    Weight *distTo;             // distTo[i]存储从起始点s到i的最短路径长度
    bool *marked;               // 标记数组, 在算法运行过程中标记节点i是否被访问
    vector<Edge<Weight>*> from; // from[i]记录最短路径中, 到达i点的边是哪一条
                                // 可以用来恢复整个最短路径

public:
    // 构造函数, 使用Dijkstra算法求最短路径
    Dijkstra(Graph &graph, int s):G(graph){

        // 算法初始化
        assert( s >= 0 && s < G.V() );
        this->s = s;
        distTo = new Weight[G.V()];
        marked = new bool[G.V()];
        for( int i = 0 ; i < G.V() ; i ++ ){
            distTo[i] = Weight();
            marked[i] = false;
            from.push_back(NULL);
        }

        // 使用索引堆记录当前找到的到达每个顶点的最短距离
        IndexMinHeap<Weight> ipq(G.V());

        // 对于其实点s进行初始化
        distTo[s] = Weight();
        from[s] = new Edge<Weight>(s, s, 0);
        ipq.insert(s, distTo[s] );
        marked[s] = true;
        while( !ipq.isEmpty() ){
            int v = ipq.extractMinIndex();

            // distTo[v]就是s到v的最短距离
            marked[v] = true;

            // 对v的所有相邻节点进行更新
            typename Graph::adjIterator adj(G, v);
            for( Edge<Weight>* e = adj.begin() ; !adj.end() ; e = adj.next() ){
                int w = e->other(v);
                // 如果从s点到w点的最短路径还没有找到
                if( !marked[w] ){
                    // 如果w点以前没有访问过,
                    // 或者访问过, 但是通过当前的v点到w点距离更短, 则进行更新
                    if( from[w] == NULL || distTo[v] + e->wt() < distTo[w] ){
                        distTo[w] = distTo[v] + e->wt();
                        from[w] = e;
                        if( ipq.contain(w) )
                            ipq.change(w, distTo[w] );
                        else
                            ipq.insert(w, distTo[w] );
                    }
                }
            }
        }
    }

    // 析构函数
    ~Dijkstra(){
        delete[] distTo;
        delete[] marked;
        delete from[0];
    }

    // 返回从s点到w点的最短路径长度
    Weight shortestPathTo( int w ){
        assert( w >= 0 && w < G.V() );
        assert( hasPathTo(w) );
        return distTo[w];
    }

    // 判断从s点到w点是否联通
    bool hasPathTo( int w ){
        assert( w >= 0 && w < G.V() );
        return marked[w];
    }

    // 寻找从s到w的最短路径, 将整个路径经过的边存放在vec中
    void shortestPath( int w, vector<Edge<Weight>> &vec ){

        assert( w >= 0 && w < G.V() );
        assert( hasPathTo(w) );

        // 通过from数组逆向查找到从s到w的路径, 存放到栈中
        stack<Edge<Weight>*> s;
        Edge<Weight> *e = from[w];
        while( e->v() != this->s ){
            s.push(e);
            e = from[e->v()];
        }
        s.push(e);

        // 从栈中依次取出元素, 获得顺序的从s到w的路径
        while( !s.empty() ){
            e = s.top();
            vec.push_back( *e );
            s.pop();
        }
    }

    // 打印出从s点到w点的路径
    void showPath(int w){

        assert( w >= 0 && w < G.V() );
        assert( hasPathTo(w) );

        vector<Edge<Weight>> vec;
        shortestPath(w, vec);
        for( int i = 0 ; i < vec.size() ; i ++ ){
            cout<<vec[i].v()<<" -> ";
            if( i == vec.size()-1 )
                cout<<vec[i].w()<<endl;
        }
    }
};

main.cpp:

// 测试我们的Dijkstra最短路径算法
int main() {

    string filename = "testG1.txt";
    int V = 5;

    SparseGraph<int> g = SparseGraph<int>(V, true);
    // Dijkstra最短路径算法同样适用于有向图
    //SparseGraph<int> g = SparseGraph<int>(V, false);
    ReadGraph<SparseGraph<int>, int> readGraph(g, filename);

    cout<<"Test Dijkstra:"<<endl<<endl;
    Dijkstra<SparseGraph<int>, int> dij(g,0);
    for( int i = 0 ; i < V ; i ++ ){
        if(dij.hasPathTo(i)){
            cout<<"Shortest Path to "<<i<<" : "<<dij.shortestPathTo(i)<<endl;
            dij.showPath(i);
        }
        else
            cout<<"No Path to "<<i<<endl;

        cout<<"----------"<<endl;
    }

    return 0;
}

运行结果

处理负权边

拥有负权环的不存在最短路径

两边形成负权环

Bellman-Ford 单源最短路径算法

复杂度高

  • 如果一个图没有负权环,
  • 从一点到另外一点的最短路径,最多经过所有的V个顶线,有V-1条边
  • 否则,存在顶点经过了两次,既存在负权环

松弛操作的核心是我们找到了一条边的路径,我们看一下有没有两条边的路径比他权值小。

  • 对一个点的一次松弛操作,就是找到经过这个点的另外一条路径,多一条边,权值更小。
  • 如果一个图没有负权环,从一点到另外一点的最短路径,最多经过所有的V个顶线,有V-1条边
  • 对所有的点进行V-1次松弛操作
  • 对所有的点进行V-1次松弛操作,理论上就找到了从源点到其他所有点的最短路径。
  • 如果还可以继续松弛,所说原图中有负权环。
// 使用BellmanFord算法求最短路径
template <typename Graph, typename Weight>
class BellmanFord{

private:
    Graph &G;                   // 图的引用
    int s;                      // 起始点
    Weight* distTo;             // distTo[i]存储从起始点s到i的最短路径长度
    vector<Edge<Weight>*> from; // from[i]记录最短路径中, 到达i点的边是哪一条
                                // 可以用来恢复整个最短路径
    bool hasNegativeCycle;      // 标记图中是否有负权环

    // 判断图中是否有负权环
    bool detectNegativeCycle(){

        for( int i = 0 ; i < G.V() ; i ++ ){
            typename Graph::adjIterator adj(G,i);
            for( Edge<Weight>* e = adj.begin() ; !adj.end() ; e = adj.next() )
                if( from[e->v()] && distTo[e->v()] + e->wt() < distTo[e->w()] )
                    return true;
        }

        return false;
    }

public:
    // 构造函数, 使用BellmanFord算法求最短路径
    BellmanFord(Graph &graph, int s):G(graph){

        this->s = s;
        distTo = new Weight[G.V()];
        // 初始化所有的节点s都不可达, 由from数组来表示
        for( int i = 0 ; i < G.V() ; i ++ )
            from.push_back(NULL);

        // 设置distTo[s] = 0, 并且让from[s]不为NULL, 表示初始s节点可达且距离为0
        distTo[s] = Weight();
        from[s] = new Edge<Weight>(s, s, 0); // 这里我们from[s]的内容是new出来的, 注意要在析构函数里delete掉

        // Bellman-Ford的过程
        // 进行V-1次循环, 每一次循环求出从起点到其余所有点, 最多使用pass步可到达的最短距离
        for( int pass = 1 ; pass < G.V() ; pass ++ ){

            // 每次循环中对所有的边进行一遍松弛操作
            // 遍历所有边的方式是先遍历所有的顶点, 然后遍历和所有顶点相邻的所有边
            for( int i = 0 ; i < G.V() ; i ++ ){
                // 使用我们实现的邻边迭代器遍历和所有顶点相邻的所有边
                typename Graph::adjIterator adj(G,i);
                for( Edge<Weight>* e = adj.begin() ; !adj.end() ; e = adj.next() )
                    // 对于每一个边首先判断e->v()可达
                    // 之后看如果e->w()以前没有到达过, 显然我们可以更新distTo[e->w()]
                    // 或者e->w()以前虽然到达过, 但是通过这个e我们可以获得一个更短的距离, 即可以进行一次松弛操作, 我们也可以更新distTo[e->w()]
                    if( from[e->v()] && (!from[e->w()] || distTo[e->v()] + e->wt() < distTo[e->w()]) ){
                        distTo[e->w()] = distTo[e->v()] + e->wt();
                        from[e->w()] = e;
                    }
            }
        }

        hasNegativeCycle = detectNegativeCycle();
    }

    // 析构函数
    ~BellmanFord(){

        delete[] distTo;
        delete from[s];
    }

    // 返回图中是否有负权环
    bool negativeCycle(){
        return hasNegativeCycle;
    }

    // 返回从s点到w点的最短路径长度
    Weight shortestPathTo( int w ){
        assert( w >= 0 && w < G.V() );
        assert( !hasNegativeCycle );
        assert( hasPathTo(w) );
        return distTo[w];
    }

    // 判断从s点到w点是否联通
    bool hasPathTo( int w ){
        assert( w >= 0 && w < G.V() );
        return from[w] != NULL;
    }

    // 寻找从s到w的最短路径, 将整个路径经过的边存放在vec中
    void shortestPath( int w, vector<Edge<Weight>> &vec ){

        assert( w >= 0 && w < G.V() );
        assert( !hasNegativeCycle );
        assert( hasPathTo(w) );

        // 通过from数组逆向查找到从s到w的路径, 存放到栈中
        stack<Edge<Weight>*> s;
        Edge<Weight> *e = from[w];
        while( e->v() != this->s ){
            s.push(e);
            e = from[e->v()];
        }
        s.push(e);

        // 从栈中依次取出元素, 获得顺序的从s到w的路径
        while( !s.empty() ){
            e = s.top();
            vec.push_back( *e );
            s.pop();
        }
    }

    // 打印出从s点到w点的路径
    void showPath(int w){

        assert( w >= 0 && w < G.V() );
        assert( !hasNegativeCycle );
        assert( hasPathTo(w) );

        vector<Edge<Weight>> vec;
        shortestPath(w, vec);
        for( int i = 0 ; i < vec.size() ; i ++ ){
            cout<<vec[i].v()<<" -> ";
            if( i == vec.size()-1 )
                cout<<vec[i].w()<<endl;
        }
    }
};

main.cpp:

// 测试Bellman-Ford算法
int main() {

    string filename = "testG2.txt";
    //string filename = "testG_negative_circle.txt";
    int V = 5;

    SparseGraph<int> g = SparseGraph<int>(V, true);
    ReadGraph<SparseGraph<int>, int> readGraph(g, filename);

    cout<<"Test Bellman-Ford:"<<endl<<endl;
    BellmanFord<SparseGraph<int>, int> bellmanFord(g,0);
    if( bellmanFord.negativeCycle() )
        cout<<"The graph contain negative cycle!"<<endl;
    else
        for( int i = 1 ; i < V ; i ++ ) {
            if (bellmanFord.hasPathTo(i)) {
                cout << "Shortest Path to " << i << " : " << bellmanFord.shortestPathTo(i) << endl;
                bellmanFord.showPath(i);
            }
            else
                cout << "No Path to " << i << endl;

            cout << "----------" << endl;
        }

    return 0;
}

运行结果:

运行结果

用于有向图,因为无向图中一条负权边就等价于两个方向都有,会形成环。

更多和最短路径相关的问题

单源最短路径算法 具体实现,distTo[i] 初始化为“正无穷”

  if( from[e->v()] && (!from[e->w()] || distTo[e->v()] + e->wt() < distTo[e->w()]) ){
                        distTo[e->w()] = distTo[e->v()] + e->wt();
                        from[e->w()] = e;
                    }

利用队列数据结构 queue-based bellman-ford算法

所有对最短路径算法

Floyed算法,处理无负权环的图 O( V^3 )

最长路径算法

最长路径问题不能有正权环。 无权图的最长路径问题是指数级难度的。 对于有权图,不能使用Dijkstra求最长路径问题。 可以使用 Bellman-Ford算法。(取负操作)

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏人工智能LeadAI

Python 设计模式初探

本文章是在阅读精通Python设计模式(中文版)(https://book.douban.com/subject/26829015/),以及阅读 Mask R-...

3606
来自专栏章鱼的慢慢技术路

Direct3D 11 Tutorial 7:Texture Mapping and Constant Buffers_Direct3D 11 教程7:纹理映射和常量缓冲区

在上一个教程中,我们为项目引入了照明。 现在我们将通过向我们的立方体添加纹理来构建它。 此外,我们将介绍常量缓冲区的概念,并解释如何使用缓冲区通过最小化带宽使用...

1014
来自专栏数据科学

朴素贝叶斯做文本分类

.dataframe tbody tr th:only-of-type { vertical-align: middle; ...

1915
来自专栏C语言及其他语言

【每日一题】问题 1213: 幸运儿

关注我们 题目描述 n 个人围成一圈, 并依次编号1~n,。从编号为1 的人开始,按顺时针方向每隔一人选出一个,剩下的人重新围成一圈,如此循环直到剩下两人,这...

53116
来自专栏漫漫深度学习路

tensorflow学习笔记(三十三):ExponentialMovingAverage

ExponentialMovingAverage Some training algorithms, such as GradientDescent and M...

5076
来自专栏图形学与OpenGL

实验5 运算符重载

1902
来自专栏深度学习之tensorflow实战篇

tensorflow(一)windows 10 64位安装tensorflow1.4与基本概念解读tf.global_variables_initializer

一.安装 目前用了tensorflow、deeplearning4j两个深度学习框架, tensorflow 之前一直支持到python 3.5,目前以更新...

3756
来自专栏用户2442861的专栏

阿里巴巴2014秋季校园招聘-软件研发工程师笔试题详解

http://blog.csdn.net/zs634134578/article/details/21018845

1432
来自专栏编程

数控宏程序的编程及应用

1. 什么场合会用到宏程序编程? 其实说起来宏就是用公式来加工零件,比如说椭圆,如果没有宏的话,我们要逐点算出曲线上的点,然后慢慢来用直线逼近,如果是个光洁度要...

2008
来自专栏python3

python语句-中断循环-continue,break

continue的作用是:从continue语句开始到循环结束,之间所有的语句都不执行,直接从一下次循环重新开始

1203

扫码关注云+社区

领取腾讯云代金券