数据结构——最短路径Dijkstra算法

在上一篇博文里,我记录了最小生成树的算法实现,而在这篇里,我们来讲讲查找最短路径的算法,Dijkstra算法。

Dijkstra's algorithm常用于路由算法或者作为其他图算法的一个子模块。距离来说,如果我们将图的顶点理解为每个城市,而边上的权重表示城市间开车行径的路径,该算法可以用来找到两个城市之间的最短路径。

Dijkstra算法是通过为每个顶点v保留目前为止所找到的从s到v的最短路径来工作的。初始时,原点s的路径权重被赋为0(d[s] = 0)。若对于顶点s存在能直接到达的边,则比较路径的长度,如果路径更短则更新存储的值,当算法结束时,d[v]中存储的便是从s到v的最短路径,或者如果路径不存在的话则是无法访问,用marked数组来记录从s到点v是否存在路径。下面我们来看Dijkstra算法的代码实现,首先是C++版本:

#include <iostream>
#include <vector>
#include <stack>
#include "Edge.h"
#include "IndexMinHeap.h"

using namespace std;

// 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;
            }
        }
    }
};

之后是java版本的:

// Dijkstra算法求最短路径
public class Dijkstra<Weight extends Number & Comparable> {

    private WeightedGraph G;      // 图的引用
    private int s;                // 起始点
    private Number[] distTo;      // distTo[i]存储从起始点s到点i的最短路径长度
    private boolean[] marked;     // 标记数组,在算法运行过程中标记节点是否被访问
    private Edge<Weight>[] from;  // 可以用来恢复整个最短路径

    // 构造函数,使用Dijkstra算法求最短路径
    Dijkstra(WeightedGraph graph, int s) {

        // 算法初始化
        this.G = graph;
        assert s >= 0 && s < G.V();
        this.s = s;
        distTo = new Number[G.V()];

        for (int i = 0; i < G.V(); i++) {
            distTo[i] = 0.0;
            marked[i] = false;
            from[i] = null;
        }

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

        // 对于起始点s进行初始化
        distTo[s] = 0.0;
        from[s] = new Edge<Weight>(s, s, (Weight)(Number)(0.0));
        ipq.insert(s, (Weight) distTo[s]);
        marked[s] = true;

        while (!ipq.isEmpty()) {
            int v = ipq.extractMinIndex();

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

            // 对v的所有相邻节点进行更新
            for (Object item : G.adj(v)) {
                Edge<Weight> e = (Edge<Weight>) item;
                int w = e.other(v);

                // 如果s点到w点的最短路径还没有找到
                if (!marked[w]) {

                    // 如果w点以前没有访问过
                    // 或者访问过,但是通过当前v点到w点的距离g更短,则进行更新
                    if (from[w] == null || distTo[v].doubleValue() + e.wt().doubleValue() < distTo[w].doubleValue()) {
                        distTo[w] = distTo[v].doubleValue() + e.wt().doubleValue();
                        from[w] = e;
                        if ( ipq.contain(w) ) {
                            ipq.change(w, (Weight) distTo[w]);
                        } else {
                            ipq.insert(w, (Weight) distTo[w]);
                        }
                    }
                }
            }
        }
    }

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

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

    // 寻找从s点到w点的最短路径,将整个路径存放在vec中
    private Vector<Edge<Weight>> shortestPath(int w) {
        assert w >= 0 && w < G.V();
        assert hasPathTo(w);

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

        s.push(e);

        // 从栈中依次取出元素,获得顺序的从s到w的路径
        Vector<Edge<Weight>> res = new Vector<Edge<Weight>>();
        while (!s.isEmpty()) {
            e = s.pop();
            res.add(e);
        }

        return res;
    }

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

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

        Vector<Edge<Weight>> path =  shortestPath(w);
        for( int i = 0 ; i < path.size() ; i ++ ){
            System.out.print( path.elementAt(i).v() + " -> ");
            if( i == path.size()-1 )
                System.out.println(path.elementAt(i).w());
        }
    }
}

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏人工智能LeadAI

Python 设计模式初探

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

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

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

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

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

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

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

5096
来自专栏专知

【附源码】TensorFlow动态图(Eager模式)的那些神坑

导读:TensorFlow的动态图(Eager模式)为TensorFlow提供了Pythonic的API,让开发者可以像使用PyTorch一样使用TensorF...

1082
来自专栏图形学与OpenGL

实验5 运算符重载

1902
来自专栏人工智能LeadAI

TensorFlow应用实战 | TensorFlow基础知识

hw = tf.constant("Hello World! Mtianyan love TensorFlow!")

1724
来自专栏java 成神之路

java.util.Random 实现原理

3375
来自专栏WD学习记录

数据结构与算法2016-06-01

1.数据结构包括数据的逻辑结构和物理结构。数据的逻辑结构就是从具体问题抽象出来的数学模型,是为了讨论问题的方便,与数据在计算机中的具体存储没有关系。讨论数据结构...

932
来自专栏丁科的专栏

Pytorch 学习笔记之自定义 Module

pytorch 是一个基于 python 的深度学习库。pytorch 源码库的抽象层次少,结构清晰,代码量适中。相比于非常工程化的 tensorflow,py...

4.3K2
来自专栏LhWorld哥陪你聊算法

【推荐系统篇】--推荐系统之训练模型

经过之前的训练数据的构建可以得到所有特征值为1的模型文件,本文将继续构建训练数据特征并构建模型。

1751

扫码关注云+社区

领取腾讯云代金券