dijkstra 订阅
艾兹格·W·迪科斯彻 (Edsger Wybe Dijkstra,1930年5月11日~2002年8月6日)荷兰人。 计算机科学家,毕业就职于荷兰Leiden大学,早年钻研物理及数学,而后转为计算学。曾在1972年获得过素有计算机科学界的诺贝尔奖之称的图灵奖,之后,他还获得过1974年 AFIPS Harry Goode Memorial Award、1989年ACM SIGCSE计算机科学教育教学杰出贡献奖、以及2002年ACM PODC最具影响力论文奖。 展开全文
艾兹格·W·迪科斯彻 (Edsger Wybe Dijkstra,1930年5月11日~2002年8月6日)荷兰人。 计算机科学家,毕业就职于荷兰Leiden大学,早年钻研物理及数学,而后转为计算学。曾在1972年获得过素有计算机科学界的诺贝尔奖之称的图灵奖,之后,他还获得过1974年 AFIPS Harry Goode Memorial Award、1989年ACM SIGCSE计算机科学教育教学杰出贡献奖、以及2002年ACM PODC最具影响力论文奖。
信息
主要成就
1972年获得图灵奖 1989年计算机科学教育杰出贡献奖 2002年ACM PODC最具影响力论文奖
毕业院校
荷兰Leiden大学
国    籍
荷兰
出生地
荷兰鹿特丹(Rotterdam)
别    名
艾兹格·迪科斯特拉
中文名
艾兹格·迪科斯彻
外文名
Edsger Wybe Dijkstra
出生日期
1930年5月11日
逝世日期
2002年8月6日
职    业
计算机科学家
艾兹格·迪科斯彻成就
艾兹格·W·迪科斯彻(Edsger Wybe Dijkstra)1 提出“goto有害论”;2 提出信号量和PV原语;3 解决了“哲学家聚餐”问题;4 Dijkstra最短路径算法和银行家算法的创造者;5 第一个Algol 60编译器的设计者和实现者;6 THE操作系统的设计者和开发者;与D. E. Knuth并称为我们这个时代最伟大的计算机科学家的人。与癌症抗争多年,于2002年8月6日在荷兰Nuenen自己的家中去世,享年72岁。
收起全文
精华内容
参与话题
问答
  • dijkstra

    2020-10-11 11:49:26
    原网页链接:https://www.luogu.com.cn/blog/little-sun/dijkstra
    展开全文
  • Dijkstra

    2020-09-06 12:59:41
    Dijkstra(迪杰斯特拉算法) #Dijkstra(迪杰斯特拉算法) 带权无向图中寻求最短路径 #动态演示过程: https://www.bilibili.com/video/BV1q4411M7r9?from=search&seid=5585063956337033177 #实现的话用优先...

     Dijkstra(迪杰斯特拉算法)

    #Dijkstra(迪杰斯特拉算法) 带权无向图中寻求最短路径
    #动态演示过程: https://www.bilibili.com/video/BV1q4411M7r9?from=search&seid=5585063956337033177
    #实现的话用优先队列实现(出队的都是确认是到该点的最短路径)
    import heapq
    import math
    graph = {
        "A": {"B": 5, "C": 1},
        "B": {"A": 5, "C": 2, "D": 1},
        "C": {"A": 1, "B": 2, "D": 4, "E": 8},
        "D": {"B": 1, "C": 4, "E": 3, "F": 6},
        "E": {"C": 8, "D": 3},
        "F": {"D": 6}
    }
    def init_distance(graph,s):
        distance = {s:0}
        nodes = graph.keys()
        for node in nodes:
            if node !=s:
                distance[node] = math.inf
        return distance
    
    def dijkstra(graph,s):
        #用heapq(小根堆)实现优先队列
        pqueue = []
        heapq.heappush(pqueue,(0,s))
        #此处的seen和BFS,DFS中的seen不一样,此处的seen都是出队的,已经确认最短路径的节点
        seen = set()
        #          A  B  C  D  E  F
        #distance(初始化位正无穷)
        #parent(初始化为-1)
        distance = init_distance(graph,s)
        parent = {s:None}
        #出队的都是已经确认是最短距离的
        while len(pqueue) > 0:
            pair = heapq.heappop(pqueue)
            dist = pair[0]
            cur = pair[1]
            seen.add(cur)
            #与cur相邻的节点
            nodes = graph[cur].keys()
            for n in nodes:
                if n not in seen:
                    #满足下面关系式才更新
                    if dist + graph[cur][n] < distance[n]:
                        heapq.heappush(pqueue,(dist + graph[cur][n],n))
                        parent[n] = cur
                        distance[n] = dist + graph[cur][n]
                
        return parent, distance
        

     

    展开全文
  • 今天要写yen’s algorithm,其内要用到Dijkstra,所以先发一篇Dijkstra的博客。 Dijkstra算法思想算法实现算法示例 算法思想 算法实现 算法示例

    今天要写yen’s algorithm,其中要用到Dijkstra,所以好好学习了一下。

    算法简介

    Dijkstra是典型最短路径算法,用于计算赋权图中单源最短路径问题——一个节点到其他所有节点的最短路径及长度、各个最短路径所包含的节点——但是,请注意,Dijkstra虽是寻找最短路径的算法,但是找到的最短路径并不止一条,因为它会找从起点到每个节点间的最短路径的集合。还有,Dijkstra算法要求图中不存在负权边

    自认:之所以要强调赋权图,是因为在无权图中,Dijkstra蜕变为图的广度优先遍历,原因详见算法思想处。

    虽然一会要看到的代码中,结束条件是所有节点都遍历到了,但是目的是确定起点到所有节点的最短路径的最终距离。一定要跟最小生成树的算法区分开,不要混淆。

    此外,值得一提的是,它是贪婪算法最好的例子

    贪婪算法

    贪婪算法一般分阶段求解一个问题,在每个阶段它都把出现的当做是最好的去处理——(自认)即在每一步都选择当前的最好选项。待细补。

    算法思想

    Dijkstra的基本思想,简单来说,是以起始点为中心向外层层扩展(广度优先遍历思想,也有点像树的层序遍历),直到扩展到终点为止。之所以说它像广度优先是因为,它每次都选择距离起点(注意,而非当前查找过程中所在的点)最近的点——依据离起点的远近,依次选择各点(近的优先)。并在选择这些点后,更新与它直接相邻的各个节点到起点的距离,直至所有点都遍历一遍为止。

    具体来说,就是:
    ①在开始时,将所有节点的(到起点)距离设为无穷大;全部(包括起点)纳入不确定集合中。

    ②选择起点,将其(到起点)距离设为0。因为自己到自己的距离肯定为0。

    ③循环地从不确定集合中选择一个节点,加入确定集合。
    当不确定集合为空时,此循环结束。
    其中,每次选择的节点,都是选择离起点最近的点——即具有最小(到起点)距离,加入到确定节点集中(但此时数值不一定固定、准确,即不到算法终止,结果都不一定准确)。这里多提一句,第一次一定会选择起点加入确定集合,因为第二步将起点的距离设为0,而其余的点距离还是无穷大。

    每次有节点加入到确定集合时,都会更新图中与新加入节点相连的所有点 (到起点) 的距离。其中(1)不论与新加入节点相连的点在确定集合还是不确定集合(2)更新距离时,只需考虑“与新加入节点相邻的这些节点”已有的(到起点)路径短,还是通过新加入节点到起点的距离短,即可。若通过新加入节点到起点更短,则换成新加入节点。用代码描述(2)中的判断就是if(v.dist + cvw < w.dist))

    算法实现

    此处仅给出伪代码和Java的代码实现。

    伪代码

    //Dijkstra中要用到的点的结构
    class Vertex{
    	/*自认这个变量没有用,但是有书上给出这一项,所以还是放在这里,供大家参考*/
    	public List	adj;//Adjacent list
    	/***********************************************************************/
    	public boolean known; //表示该点是否已确定到起点的最短路径
    	public int dist; //表示当前点到起点的距离。因为前面已经说到,Dijkstra是用来求一个点到图中所有点之间的最短路径,所以这里的起点是指那一个点。
    	public Vertex path; //记录自己(所在的路径序列中)的上一节点,用来遍历、记录找到的最短路径使用。
    }
    
    void dijkstra(Vertex s){
    
    	/*********************************初始化所有节点***************************************/
    	for each Vertex v
    	{
    		v.dist = INFINITY;//将所有节点到起点 s 的距离设为无穷大
    		v.known = false;//将所有节点标为未确定,即还未加入路径
    	}
    	/*****************************************************************************************/
    	
    	s.dist = 0; //将起点自己的dist设为0(因为dist这一属性专门记录各个节点到起点的距离,所以起点自己到自己的距离肯定是0)
    	
    	for( ; ; ){  //一直循环,直到触发break
    		Vertex v = smallest distance and unknown vertex; //从未确定的点集中取出距离起点最近的点
    		if(v==null) break; //若取到的点是空,即已无点可取
    		v.known = true; //将该点加入确定点
    
    		/*********************************更新距离***********************************/
    		for each Vertex w adjacent to v  //只遍历、选出与新加入节点v相连的节点w
    			if( !w.known ) //如果w还是未确定的点
    				//因为距离还未确定,所以比较,若是更近则更新
    				if(v.dist + cvw < w.dist){ //自认,cvw是指当前所选节点w与新加入节点v的距离
    					//即若发现新加入节点v周围的节点w们,通过v到起点的距离 比它们现有到起点的距离少,则更新对应的dist和用于存储上一节点的项path
    					w.dist = v.dist + cvw;
    					w.path = v;
    				}
    		/*****************************************************************************/
    	} 
    	
    }
    

    Java版

    在这里插入代码片
    

    算法示例

    动态图

    算法分析

    通过反证法的证明,我们可以知道,只要没有权值为负的边存在,Dijkstra总是能够顺利工作。

    时间复杂度分析

    书P248补
    运行时间依赖对顶点的处理方法:若在
    Vertex v = smallest distance and unknown vertex;处顺序扫描顶点,找出最小值的点,那么整个算法过程中查找最小值将花费

    展开全文
  • 最短路径问题---Dijkstra算法详解

    万次阅读 多人点赞 2017-03-08 16:42:46
    前言 Nobody can go back and start a new beginning,but anyone can start today and make a new ending. Name:Willam Time:2017/3/8 1、最短路径问题介绍 问题解释: 从图中的某个顶点出发到达另外一个顶点...

    前言
    Nobody can go back and start a new beginning,but anyone can start today and make a new ending.
    Name:Willam
    Time:2017/3/8

    1、最短路径问题介绍

    问题解释:
    从图中的某个顶点出发到达另外一个顶点的所经过的边的权重和最小的一条路径,称为最短路径

    解决问题的算法:

    这篇博客,我们就对Dijkstra算法来做一个详细的介绍

    2、Dijkstra算法介绍

    • 算法特点:

      迪科斯彻算法使用了广度优先搜索解决赋权有向图或者无向图的单源最短路径问题,算法最终得到一个最短路径树。该算法常用于路由算法或者作为其他图算法的一个子模块。

    • 算法的思路

      Dijkstra算法采用的是一种贪心的策略,声明一个数组dis来保存源点到各个顶点的最短距离和一个保存已经找到了最短路径的顶点的集合:T,初始时,原点 s 的路径权重被赋为 0 (dis[s] = 0)。若对于顶点 s 存在能直接到达的边(s,m),则把dis[m]设为w(s, m),同时把所有其他(s不能直接到达的)顶点的路径长度设为无穷大。初始时,集合T只有顶点s。
      然后,从dis数组选择最小值,则该值就是源点s到该值对应的顶点的最短路径,并且把该点加入到T中,OK,此时完成一个顶点,
      然后,我们需要看看新加入的顶点是否可以到达其他顶点并且看看通过该顶点到达其他点的路径长度是否比源点直接到达短,如果是,那么就替换这些顶点在dis中的值。
      然后,又从dis中找出最小值,重复上述动作,直到T中包含了图的所有顶点。

    3、Dijkstra算法示例演示

    下面我求下图,从顶点v1到其他各个顶点的最短路径

    这里写图片描述

    首先第一步,我们先声明一个dis数组,该数组初始化的值为:
    这里写图片描述

    我们的顶点集T的初始化为:T={v1}

    既然是求 v1顶点到其余各个顶点的最短路程,那就先找一个离 1 号顶点最近的顶点。通过数组 dis 可知当前离v1顶点最近是 v3顶点。当选择了 2 号顶点后,dis[2](下标从0开始)的值就已经从“估计值”变为了“确定值”,即 v1顶点到 v3顶点的最短路程就是当前 dis[2]值。将V3加入到T中。
    为什么呢?因为目前离 v1顶点最近的是 v3顶点,并且这个图所有的边都是正数,那么肯定不可能通过第三个顶点中转,使得 v1顶点到 v3顶点的路程进一步缩短了。因为 v1顶点到其它顶点的路程肯定没有 v1到 v3顶点短.

    OK,既然确定了一个顶点的最短路径,下面我们就要根据这个新入的顶点V3会有出度,发现以v3 为弧尾的有: < v3,v4 >,那么我们看看路径:v1–v3–v4的长度是否比v1–v4短,其实这个已经是很明显的了,因为dis[3]代表的就是v1–v4的长度为无穷大,而v1–v3–v4的长度为:10+50=60,所以更新dis[3]的值,得到如下结果:
    这里写图片描述

    因此 dis[3]要更新为 60。这个过程有个专业术语叫做“松弛”。即 v1顶点到 v4顶点的路程即 dis[3],通过 < v3,v4> 这条边松弛成功。这便是 Dijkstra 算法的主要思想:通过“边”来松弛v1顶点到其余各个顶点的路程。

    然后,我们又从除dis[2]和dis[0]外的其他值中寻找最小值,发现dis[4]的值最小,通过之前是解释的原理,可以知道v1到v5的最短距离就是dis[4]的值,然后,我们把v5加入到集合T中,然后,考虑v5的出度是否会影响我们的数组dis的值,v5有两条出度:< v5,v4>和 < v5,v6>,然后我们发现:v1–v5–v4的长度为:50,而dis[3]的值为60,所以我们要更新dis[3]的值.另外,v1-v5-v6的长度为:90,而dis[5]为100,所以我们需要更新dis[5]的值。更新后的dis数组如下图:
    这里写图片描述

    然后,继续从dis中选择未确定的顶点的值中选择一个最小的值,发现dis[3]的值是最小的,所以把v4加入到集合T中,此时集合T={v1,v3,v5,v4},然后,考虑v4的出度是否会影响我们的数组dis的值,v4有一条出度:< v4,v6>,然后我们发现:v1–v5–v4–v6的长度为:60,而dis[5]的值为90,所以我们要更新dis[5]的值,更新后的dis数组如下图:
    这里写图片描述

    然后,我们使用同样原理,分别确定了v6和v2的最短路径,最后dis的数组的值如下:
    这里写图片描述

    因此,从图中,我们可以发现v1-v2的值为:∞,代表没有路径从v1到达v2。所以我们得到的最后的结果为:

    起点  终点    最短路径    长度
    v1    v2     无          ∞    
          v3     {v1,v3}    10
          v4     {v1,v5,v4}  50
          v5     {v1,v5}    30
          v6     {v1,v5,v4,v6} 60
    

    4、Dijkstra算法的代码实现(c++)

    • Dijkstra.h文件的代码
    /************************************************************/
    /*                程序作者:Willam                          */
    /*                程序完成时间:2017/3/8                    */
    /*                有任何问题请联系:2930526477@qq.com       */
    /************************************************************/
    //@尽量写出完美的程序
    
    #pragma once
    //#pragma once是一个比较常用的C/C++杂注,
    //只要在头文件的最开始加入这条杂注,
    //就能够保证头文件只被编译一次。
    
    #include<iostream>
    #include<string>
    using namespace std;
    
    /*
    本程序是使用Dijkstra算法实现求解最短路径的问题
    采用的邻接矩阵来存储图
    */
    //记录起点到每个顶点的最短路径的信息
    struct Dis {
        string path;
        int value;
        bool visit;
        Dis() {
            visit = false;
            value = 0;
            path = "";
        }
    };
    
    class Graph_DG {
    private:
        int vexnum;   //图的顶点个数
        int edge;     //图的边数
        int **arc;   //邻接矩阵
        Dis * dis;   //记录各个顶点最短路径的信息
    public:
        //构造函数
        Graph_DG(int vexnum, int edge);
        //析构函数
        ~Graph_DG();
        // 判断我们每次输入的的边的信息是否合法
        //顶点从1开始编号
        bool check_edge_value(int start, int end, int weight);
        //创建图
        void createGraph();
        //打印邻接矩阵
        void print();
        //求最短路径
        void Dijkstra(int begin);
        //打印最短路径
        void print_path(int);
    };
    
    • Dijkstra.cpp文件的代码
    #include"Dijkstra.h"
    
    //构造函数
    Graph_DG::Graph_DG(int vexnum, int edge) {
        //初始化顶点数和边数
        this->vexnum = vexnum;
        this->edge = edge;
        //为邻接矩阵开辟空间和赋初值
        arc = new int*[this->vexnum];
        dis = new Dis[this->vexnum];
        for (int i = 0; i < this->vexnum; i++) {
            arc[i] = new int[this->vexnum];
            for (int k = 0; k < this->vexnum; k++) {
                //邻接矩阵初始化为无穷大
                    arc[i][k] = INT_MAX;
            }
        }
    }
    //析构函数
    Graph_DG::~Graph_DG() {
        delete[] dis;
        for (int i = 0; i < this->vexnum; i++) {
            delete this->arc[i];
        }
        delete arc;
    }
    
    // 判断我们每次输入的的边的信息是否合法
    //顶点从1开始编号
    bool Graph_DG::check_edge_value(int start, int end, int weight) {
        if (start<1 || end<1 || start>vexnum || end>vexnum || weight < 0) {
            return false;
        }
        return true;
    }
    
    void Graph_DG::createGraph() {
        cout << "请输入每条边的起点和终点(顶点编号从1开始)以及其权重" << endl;
        int start;
        int end;
        int weight;
        int count = 0;
        while (count != this->edge) {
            cin >> start >> end >> weight;
            //首先判断边的信息是否合法
            while (!this->check_edge_value(start, end, weight)) {
                cout << "输入的边的信息不合法,请重新输入" << endl;
                cin >> start >> end >> weight;
            }
            //对邻接矩阵对应上的点赋值
            arc[start - 1][end - 1] = weight;
            //无向图添加上这行代码
            //arc[end - 1][start - 1] = weight;
            ++count;
        }
    }
    
    void Graph_DG::print() {
        cout << "图的邻接矩阵为:" << endl;
        int count_row = 0; //打印行的标签
        int count_col = 0; //打印列的标签
        //开始打印
        while (count_row != this->vexnum) {
            count_col = 0;
            while (count_col != this->vexnum) {
                if (arc[count_row][count_col] == INT_MAX)
                    cout << "∞" << " ";
                else
                cout << arc[count_row][count_col] << " ";
                ++count_col;
            }
            cout << endl;
            ++count_row;
        }
    }
    void Graph_DG::Dijkstra(int begin){
        //首先初始化我们的dis数组
        int i;
        for (i = 0; i < this->vexnum; i++) {
            //设置当前的路径
            dis[i].path = "v" + to_string(begin) + "-->v" + to_string(i + 1);
            dis[i].value = arc[begin - 1][i];
        }
        //设置起点的到起点的路径为0
        dis[begin - 1].value = 0;
        dis[begin - 1].visit = true;
    
        int count = 1;
        //计算剩余的顶点的最短路径(剩余this->vexnum-1个顶点)
        while (count != this->vexnum) {
            //temp用于保存当前dis数组中最小的那个下标
            //min记录的当前的最小值
            int temp=0;
            int min = INT_MAX;
            for (i = 0; i < this->vexnum; i++) {
                if (!dis[i].visit && dis[i].value<min) {
                    min = dis[i].value;
                    temp = i;
                }
            }
            //cout << temp + 1 << "  "<<min << endl;
            //把temp对应的顶点加入到已经找到的最短路径的集合中
            dis[temp].visit = true;
            ++count;
            for (i = 0; i < this->vexnum; i++) {
                //注意这里的条件arc[temp][i]!=INT_MAX必须加,不然会出现溢出,从而造成程序异常
                if (!dis[i].visit && arc[temp][i]!=INT_MAX && (dis[temp].value + arc[temp][i]) < dis[i].value) {
                    //如果新得到的边可以影响其他为访问的顶点,那就就更新它的最短路径和长度
                    dis[i].value = dis[temp].value + arc[temp][i];
                    dis[i].path = dis[temp].path + "-->v" + to_string(i + 1);
                }
            }
        }
    
    }
    void Graph_DG::print_path(int begin) {
        string str;
        str = "v" + to_string(begin);
        cout << "以"<<str<<"为起点的图的最短路径为:" << endl;
        for (int i = 0; i != this->vexnum; i++) {
            if(dis[i].value!=INT_MAX)
            cout << dis[i].path << "=" << dis[i].value << endl;
            else {
                cout << dis[i].path << "是无最短路径的" << endl;
            }
        }
    }
    • main.cpp文件的代码
    #include"Dijkstra.h"
    
    
    //检验输入边数和顶点数的值是否有效,可以自己推算为啥:
    //顶点数和边数的关系是:((Vexnum*(Vexnum - 1)) / 2) < edge
    bool check(int Vexnum, int edge) {
        if (Vexnum <= 0 || edge <= 0 || ((Vexnum*(Vexnum - 1)) / 2) < edge)
            return false;
        return true;
    }
    int main() {
        int vexnum; int edge;
    
        cout << "输入图的顶点个数和边的条数:" << endl;
        cin >> vexnum >> edge;
        while (!check(vexnum, edge)) {
            cout << "输入的数值不合法,请重新输入" << endl;
            cin >> vexnum >> edge;
        }
        Graph_DG graph(vexnum, edge);
        graph.createGraph();
        graph.print();
        graph.Dijkstra(1);
        graph.print_path(1);
        system("pause");
        return 0;
    }

    输入:

    6 8
    1 3 10
    1 5 30
    1 6 100
    2 3 5
    3 4 50
    4 6 10
    5 6 60
    5 4 20

    输出:
    这里写图片描述

    从输出可以看出,程序的结果和我们之前手动计算的结果是一样的。

    展开全文
  • 简单易懂——Dijkstra算法讲解

    万次阅读 多人点赞 2018-02-18 00:22:46
    我的机器学习教程「美团」算法工程师带你入门机器学习 已经开始更新了,欢迎大家订阅~ 任何关于算法、编程、AI行业知识或博客内容的问题,可以随时扫码关注公众号「图灵的猫」,加入”学习小组“,沙雕博主在线答疑...
  • Dijkstra算法

    千次阅读 2017-08-13 14:07:35
    Dijkstra算法
  • 最短路径: 在一个带权图中,顶点V0到图中任意一个顶点Vi的一条路径所经过边上的权值之和,定义为该路径的带权路径长度,把带权路径最短的那条路径称为最短路径。 DiskStra算法: 求单源最短路径,即求一个顶点到...
  • dijkstra/dijkstra.c:63:2: warning: passing argument 1 of ‘dijkstra’ from incompatible pointer type [enabled by default] printf("The minimum distance from %d to %d is %d\n", source, ...
  • dijkstra算法

    2020-04-08 21:04:45
    迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学家狄克斯特拉于1959 年提出的,因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法,解决的是有权图中最短路径问题。

空空如也

1 2 3 4 5 ... 20
收藏数 28,033
精华内容 11,213
关键字:

dijkstra