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

    多人点赞 2019-08-09 09:22:29
    Dijkstra算法思想 如果图是不带负权的有向图或者无向图,我们可以利用贪心策略,从起点s每次扩展一个距离起点s最短的点,并且利用这个点,更新起点到其他点的距离。 Dijkstra算法流程 1、用一个数组a[i]记录其它点到...

    转载

    ——————————————

    Dijkstra算法思想

    如果图是不带负权的有向图或者无向图,我们可以利用贪心策略,从起点s每次扩展一个距离起点s最短的点,并且利用这个点,更新起点到其他点的距离。

    Dijkstra算法流程

    1、用一个数组a[i]记录其它点到起点s的最短距离,用一个数组b[i]标记是否得到从起点s到点i的最短距离
    2、初始化数组a[i],修改其它点到起点s的距离,其中a[s]=0(起点到起点的距离为0),其他a[i]=∞(无限大)
    3、选择一个没有被标记的点k并且d[k]的值是最小的
    4、如果找不到,退出
    5、标记点k,b[k]=true;
    6、以k为中点,修改其他点到起点s的距离

    Dijkstra算法流程模拟

    下面用一个实例来具体说明:
    在这里插入图片描述
    (1)V0-V5 共6个节点,节点间路径已标出,现要求从V0到其余各节点的最短路径;
    (2)有上面的算法流程可知,在使用Dijkstra算法时需要几个结构来保存我们想要的信息:
    1.保存这张图的结构体
    2.记录V0到其余各节点最短路径的数组(这里设为len[n+1])
    3.记录某节点是否已找到最短路径的数组(这里设为note[n+1])
    (3)接下来就是算法实现部分:
    1.标记note[V0]=true;初始化 Len[]={0,∞,0,∞,10,∞,30,100}

    2.第一次循环与V0相邻的有V2、V4、V5,其中V2距离最短为10,标记V2,并且以V2为中间点(路径为V0->V2->Vx)更新最短路表,此时V3被更新为10+50=60。

    3.进入第二次循环,此时未被标记的有V1、V3、V4、V5,,其中从V0到这些的临时最短路分别为∞、60、30、100,从中找到最小的即V4,将V4标记为1,以V4为中间点(路径为V0->V4->Vx)更新最短路表,此时V3被更新为50,V5被更新为90。

    4.进入第三次循环,此时未被标记的有V1、V3、V5,其中临时最短路分别为∞、50、90,从中找到最小的即V3,将V3标记为1,以V3为中间点(路径为V0->V4->V3->Vx)更新最短路表,此时V5被更新成60。

    5.进入第四次循环,此时未被标记的有V1、V5,其中临时最短路分别为∞、60,找到V5,标记为1,以V5为中间点更新最短路表,此时没有元素被更新

    6.进入第五次循环,这次循环没找到任何东西

    7.退出循环,Len表中即为V0到其余各个节点的最短路径。

    Dijkstra模板例题(没有优化O(n2))

    题目来源:https://www.luogu.org/problemnew/show/P2299
    【题目描述】
    从1城市到n城市有很多条路,经过每条路所用的时间有可能不同,请问从1城市到n城市至少需要多少时间
    【输入输出格式】
    【输入格式】:
    第一行有两个数n,m。n表示有n个停留站,m表示共有m条路。
    之后m行,每行三个数ai bi ci,表示第ai​个停留站到第bi​个停留站需要ci​的时间。(无向)
    【输出格式】:
    一行,输出1到n最短时间。
    【输入输出样例】
    【输入样例】
    5 8
    1 2 3
    2 3 4
    3 4 5
    4 5 6
    1 3 4
    2 4 7
    2 5 8
    1 5 100
    【输出样例】
    11
    【说明】
    时空限制:1000ms,128M
    数据规模:
    n≤2500 m≤2∗10的5次方

    Dijkstra模板例题程序:

    //Dijkstra
    //https://www.luogu.org/problemnew/show/P2299
    #include<fstream>
    #include<cstring>
    #include<iostream>
    #define xb 2505
    using namespace std;
    int n,m,x,y,v;
    int xy[xb][xb];
    bool ifx[xb];//标记每个点最短路有没有被确定 
    int weight[xb];//每个点到1城市的最小值 
    void begin()
    {
        memset(weight,0x7f,sizeof(weight));//把每个城市到1城市的所用时间调到最大
        weight[1]=0;//1到1的最小值为0 
        for(int i=1;i<=n;i++)
        {//初始化每个点到点1的值 
            weight[i]=xy[1][i];
        }
        ifx[1]=true;//1的最短路径已被确定
    }
    void Dijkstra()
    {
        begin();//初始化
        for(int i=2;i<=n;i++)
        {
        	//打擂台找哪个城市到1城市所用的时间最少且这座城市的最短路径还没被确定 
            int num=0,sum=weight[0];
            for(int j=1;j<=n;j++)
            {
                if(!ifx[j]&&weight[j]<sum)
                {
                	sum=weight[j];
                	num=j;
                }
            }
            //如果找不到城市,退出 
            if(!num)break; 
            ifx[num]=true;//标记 
            for(int j=1;j<=n;j++)
            {
            	if(xy[num][j]+weight[num]<weight[j])
            	{//修改最短路径 
            		weight[j]=weight[num]+xy[num][j];
                }
            }
        }
    }
    int main()
    {
        memset(xy,0x7f,sizeof(xy));//先调到最大值 
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++)
        {
        	scanf("%d%d%d",&x,&y,&v);
        	if(v<xy[x][y])//x到y可能有很多条道路,要找出最小值 
        	xy[x][y]=xy[y][x]=v;
        }
        Dijkstra();
        printf("%d",weight[n]);
        return 0;
    }
    

      【堆优化】
      题目:https://www.luogu.org/problem/P4779

      #include<queue>
      #include<fstream>
      #include<cstring>
      #include<iostream>
      #include<algorithm>
      using namespace std;
      typedef long long LL;
      int n,m,s,f;
      int next[200005],one[200005],g[200005],w[200005];
      LL weight[100005];
      bool note[100005];
      priority_queue<pair<int,int> >q;
      void Dij()
      {
      	memset(weight,0x7f,sizeof(weight));
      	weight[s]=0;
      	q.push(make_pair(0,s));//优先队列排序第一个优先级更高,顺序不能乱
      	while(q.size())
      	{
      		int now=q.top().second;
      		q.pop();
      		if(note[now])continue;
      		note[now]=true;
      		for(int i=one[now];i;i=next[i])
      		{
      			if(weight[g[i]]>weight[now]+w[i])
      			{
      				weight[g[i]]=weight[now]+w[i];
      				q.push(make_pair(-weight[g[i]],g[i]));
      			}
      		}
      	}
      }
      int main()
      {
      	scanf("%d%d%d",&n,&m,&s);
      	for(int i=1;i<=m;i++)
      	{
      		scanf("%d%d%d",&f,&g[i],&w[i]);
      		next[i]=one[f];
      		one[f]=i;
      	}
      	Dij();
      	for(int i=1;i<=n;i++)
      	{
      		printf("%d ",weight[i]);
      	}
      	return 0;
      }
      
      展开全文
    • dijkstra

      千次阅读 2018-07-25 19:56:23
      前言 SPFASPFASPFA算法由于它上限 O(NM)=O(VE)O(NM)=O(VE)O(NM) = O(VE)的时间复杂度,被卡掉的几率很大.在算法竞赛中,我们需要一个更稳定的算法:dijkstradijkstradijkstra. 什么是dijkstradijkstradijkstra?...

      前言

      • SPFA算法由于它上限 O(NM)=O(VE)的时间复杂度,被卡掉的几率很大.在算法竞赛中,我们需要一个更稳定的算法:dijkstra.

      什么是dijkstra?

      • dijkstra是一种单源最短路径算法,时间复杂度上限为O(n2)(朴素),在实际应用中较为稳定;加上堆优化之后更是具有O((n+m)log2n)的时间复杂度,在稠密图中有不俗的表现.

      dijkstra的原理/流程?

      • dijkstra本质上的思想是贪心,它只适用于不含负权边的图.
      • dijkstra的流程如下:
      • 1. 初始化dis[start]=0,其余节点的dis值为无穷大.
      • 2. 找一个未被标记的,dis值最小的节点x,标记节点x.
      • 3. 遍历x的所有出边(x,y,z),dis[y]>dis[x]+z,则令dis[y]=dis[x]+z
      • 4. 重复2,3两步,直到所有点都被标记.
      • 时间复杂度为O(n2)

      图解

      • 我们把点分成两类,一类是已经确定最短路径的点,称为”白点”,另一类是未确定最短路径的点,称为”蓝点”
      • (令start=1)
      • 开始时我们把dis[start]初始化为0,其余点初始化为inf
        初始化
      • 第一轮循环找到dis值最小的点1,将1变成白点,对所有与1相连的蓝点的dis值进行修改,使得dis[2]=2,dis[3]=4,dis[4]=7
        1
      • 第二轮循环找到dis值最小的点2,将2变成白点,对所有与2相连的蓝点的dis值进行修改,使得dis[3]=3,dis[5]=4
        2
      • 第三轮循环找到dis值最小的点3,将3变成白点,对所有与2相连的蓝点的dis值进行修改,使得dis[4]=4
        3
      • 接下来两轮循环分别将4,5设为白点,算法结束,求出所有点的最短路径
      • 时间复杂度O(n2)

      为什么dijkstra不能处理有负权边的情况?

      • 我们来看下面这张图
        3
      • 23的边权为4,显然从13的最短路径为2(1>2>3).但在循环开始时程序会找到当前dis值最小的点3,并标记它为白点.
      • 这时的dis[3]=1,然而1并不是起点到3的最短路径.因为3已经被标为白点,所以dis[3]不会再被修改了.我们在边权存在负数的情况下得到了错误的答案.

      dijkstra的堆优化?

      • 观察dijkstra的流程,发现步骤2可以优化
      • 怎么优化呢?
      • 我会zkw线段树!我会斐波那契堆!
      • 我会堆!
      • 我们可以用堆对dis数组进行维护,用O(log2n)的时间取出堆顶元素并删除,用O(log2n)遍历每条边,总复杂度O((n+m)log2n)

      • 范例代码:

      #include<bits/stdc++.h>
      
      const int MaxN = 100010, MaxM = 500010;
      
      struct edge
      {
          int to, dis, next;
      };
      
      edge e[MaxM];
      int head[MaxN], dis[MaxN], cnt;
      bool vis[MaxN];
      int n, m, s;
      
      inline void add_edge( int u, int v, int d )
      {
          cnt++;
          e[cnt].dis = d;
          e[cnt].to = v;
          e[cnt].next = head[u];
          head[u] = cnt;
      }
      
      struct node
      {
          int dis;
          int pos;
          bool operator <( const node &x )const
          {
              return x.dis < dis;
          }
      };
      
      std::priority_queue<node> q;
      
      
      inline void dijkstra()
      {
          dis[s] = 0;
          q.push( ( node ){0, s} );
          while( !q.empty() )
          {
              node tmp = q.top();
              q.pop();
              int x = tmp.pos, d = tmp.dis;
              if( vis[x] )
                  continue;
              vis[x] = 1;
              for( int i = head[x]; i; i = e[i].next )
              {
                  int y = e[i].to;
                  if( dis[y] > dis[x] + e[i].dis )
                  {
                      dis[y] = dis[x] + e[i].dis;
                      if( !vis[y] )
                      {
                          q.push( ( node ){dis[y], y} );
                      }
                  }
              }
          }
      }
      
      
      int main()
      {
          scanf( "%d%d%d", &n, &m, &s );
          for(int i = 1; i <= n; ++i)dis[i] = 0x7fffffff;
          for( register int i = 0; i < m; ++i )
          {
              register int u, v, d;
              scanf( "%d%d%d", &u, &v, &d );
              add_edge( u, v, d );
          }
          dijkstra();
          for( int i = 1; i <= n; i++ )
              printf( "%d ", dis[i] );
          return 0;
      }
      

      例题

      • 入门模板:P3371
      • 进阶模板:P4779
      • 其余例题请右转洛谷题库,搜索”最短路”

      后记

      • 本文部分内容摘自李煜东《算法竞赛进阶指南》和《信息学竞赛一本通》
      • 友情提示:正权图请使用dijkstra算法,负权图请使用SPFA算法
      展开全文
    • 今天要写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算法

      千次阅读 2017-08-13 14:07:35
      Dijkstra算法
    • 简单易懂——Dijkstra算法讲解

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

      万次阅读 多人点赞 2017-02-19 22:46:13
      Dijkstra算法 1.定义概览 Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。Dijkstra算法是很有代表性...
    • Dijkstra算法图文详解

      万次阅读 多人点赞 2018-11-20 09:19:59
      Dijkstra算法   Dijkstra算法算是贪心思想实现的,首先把起点到所有点的距离存下来找个最短的,然后松弛一次再找出最短的,所谓的松弛操作就是,遍历一遍看通过刚刚找到的距离最短的点作为中转站会不会更近,如果...

    空空如也

    1 2 3 4 5 ... 20
    收藏数 27,861
    精华内容 11,144
    关键字:

    dijkstra