Dijkstra算法最短路径的C++实现与输出路径

某个源点到其余各顶点的最短路径

这个算法最开始心里怕怕的,不知道为什么,花了好长时间弄懂了,也写了一遍,又遇到时还是出错了,今天再次写它,心里没那么怕了,耐心研究,懂了之后会好开心的,哈哈

Dijkstra算法:

图G

如图:若要求从顶点1到其余各顶点的最短路径,该咋求;

迪杰斯特拉提出“按最短路径长度递增的次序”产生最短路径。

首先,在所有的这些最短路径中,长度最短的这条路径必定只有一条弧,且它的权值是从源点出发的所有弧上权的最小值,例如:在图G中,从源点1出发有3条弧,其中以弧(1,2)的权值为最小,因此,(1,2)不仅是1到2的一条最短路径,并且它可能是源点到其它各个终点的最短路径中的一条子路径。

其次,第二条长度次短的最短路径只可能有两种情况:①它或者只含一条从源点出发的弧且弧上的权值大于已求得最短路径的那条弧的权值,但小于其他从源点出发的弧上的权值②它或者是一条只经过已求得最短路径的顶点的路径。

例如图G中,从1到其他各点。过程中,用d[i]保存从1到i的的最短路径(过程会变化),初值为:若源点到该源点有弧,则为权值,否则初始化为无穷大,每求得一条到达某个终点i的最短路径,就继续检查是否存在以此路径为子路径的到达其他点的最短路径,若存在,判断其长度是否比当前求得的路径长度短,若短,就更新为更短的长度。

如图G中,求得到2的最短路径d[2]为10,就把d[2]作为与2相连的到其他点的子路径继续检查,得到到3的最短路径为d[2]+50=60

过程:

(1).令S={1},S集合中表示已经找到最短路径的结点,开始时1为源点,并设定d[i]的初始值为:d[i]=(1,i),

(2).求出到j点的最短路径,j点为不在S集合中的某点

d[j]=min{d[i]}

(3).判断所有没在S集合中的顶点k,若d[k]>d[j]+(j,k)则修改d[k]的值为:

d[k]=d[j]+(j,k)

(4).重复(2).(3)操作共n-1次,每次操作,在(2)得到一个到

某点的最短路径。

有向图求最短路径

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define max 900000000
//有向图
int main(){
  int n,m,a,b,v,i,j,min,k;
  scanf("%d%d",&n,&m);//输入n个顶点,m条边
  int g[n+1][n+1],d[n+1],vis[n+1];//g[i][j]表示i到j的边的权值,vis[i]表示到此顶点的最短路是否已经找到,d[i]当前源点到i顶点的最短路径
  memset(vis,0,sizeof(vis));
  for(i=0;i<=n;i++){
    for(j=0;j<=n;j++){
      g[i][j]=max;
    }
    d[i]=max;
  }
  for(i=0;i<m;i++){//i到j的边权值储存到g邻接矩阵中,i点到j点无直接相连的边时,g[i][j]=max
    scanf("%d%d%d",&a,&b,&v);
    g[a][b]=v;
  }
  for(i=2;i<=n;i++){
      d[i]=g[1][i]; //初始化源点到i点边权值,之后过程中会发生变化
  }
  vis[1]=1;
  for(i=2;i<=n;i++){//共循环n-1次,每循环一次,确定一条最短路,再次循环时这条路就不用考虑了,去寻找下一条最短路
    min=max;
    for(j=2;j<=n;j++){//寻找下一条当前最短路
      if(d[j]<min&&vis[j]==0){
       min=d[j];
       k=j;
      }
    }
    vis[k]=1;//找到了,到k点的路是当前最短路,标记它,根据它寻找下一条最短路
    for(j=2;j<=n;j++){
      if(d[j]>d[k]+g[k][j]&&vis[j]==0){//经过此k点到达j点的路径是否小于其他到达j点的路径
        d[j]=d[k]+g[k][j];
      }
    }
  }
  for(i=2;i<=n;i++){//输出到达个点的最短路径
    printf("%d\n",d[i]);
  }
  return 0;
}

无向图求最短路径

无向图也是相同思路:在构造邻接矩阵时考虑对称就行。

无向图求最短路径且有路径输出

在求最短路的过程中,最短路①它或者是从源点出发的弧②它或者是一条经过已到其他最短路径的顶点的路径。

建立一个新的结构体类型path,该类型变量d表示到达某点的最短路径距离 ,该类型变量pre表示该最短路径是经过哪个点传过来的

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define max 900000000
typedef struct{
  int d;//到达某点的最短路径距离
  int pre;//该最短路径是经过哪个点传过来的,源点或其他某个点
}path;
//有向图
int main(){
  int n,m,a,b,v,i,j,min,k,from;
  scanf("%d%d",&n,&m);//输入n个顶点,m条边
  int g[n+1][n+1],vis[n+1];//g[i][j]表示i到j的边的权值,vis[i]表示到此顶点的最短路是否已经找到,d[i]当前源点到i顶点的最短路径
  path to[n+1];//记录当前到某个点的最短路径以及从哪个点传过来的
  memset(vis,0,sizeof(vis));
  for(i=0;i<=n;i++){
    for(j=0;j<=n;j++){
      g[i][j]=max;
    }
    to[i].d=max;
  }
  for(i=0;i<m;i++){//i到j的边权值储存到g数组中,i点到j点无直接相连的边时,g[i][j]=max
    scanf("%d%d%d",&a,&b,&v);
    g[a][b]=v;
    g[b][a]=v;
  }
  for(i=2;i<=n;i++){
      to[i].d=g[1][i]; //初始化源点到i点边权值,之后过程中会发生变化
      if(g[1][i]!=max){
       to[i].pre=1;
      }
  }
  vis[1]=1;
  for(i=2;i<=n;i++){//共循环n-1次,每循环一次,确定一条最短路,再次循环时这条路就不用考虑了,去寻找下一条最短路
    min=max;
    for(j=2;j<=n;j++){//寻找下一条当前最短路
      if(to[j].d<min&&vis[j]==0){
       min=to[j].d;
       k=j;
      }
    }
    vis[k]=1;//找到了,到k点的路是当前最短路,标记它,根据它寻找下一条最短路
    for(j=2;j<=n;j++){
      if(to[j].d>to[k].d+g[k][j]&&vis[j]==0){//经过此k点到达j点的路径是否小于其他到达j点的路径
        to[j].d=to[k].d+g[k][j];
        to[j].pre=k;//改变j点是谁传来的,现在到j点的最短路径是经过k点的,由j点传来
      }
    }
  }
  for(i=2;i<=n;i++){//输出到达个点的最短路径
    printf("%d ",to[i].d);
    printf("%d ",i);
    j=i;
    while(j!=1){
      j=to[j].pre;
      printf("%d ",j);
    }
    printf("\n");
  }
  return 0;
}

总结

以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作具有一定的参考学习价值,谢谢大家对我们的支持。如果你想了解更多相关内容请查看下面相关链接

(0)

相关推荐

  • C++实现学生选课系统

    本文实例为大家分享了C++实现学生选课系统的具体代码,供大家参考,具体内容如下 #include <iostream> #include <iomanip> #include <fstream> #include<Windows.h> #include<cstring> using namespace std; struct SubList/*某个学生所学的课程中的某一个 */ { int num; /*课程代号 */ SubList *next

  • 一张图总结C++中关于指针的那些事

    指向对象的指针,指向数据成员的指针,指向成员函数的指针: 数组即指针,数组的指针,指针数组: 指向函数的指针,指向类的成员函数的指针,指针作为函数参数,指针函数: 指针的指针,指向数组的指针:常指针,指向常对象的指针: -- 大哥,这些都是什么鬼?! 用下面一张图全概括.用例子对照图示,有感觉,就用术语将概念大声地念出来,动员所有的感官参与,搞清楚这些,不是事. 图如下: 总结 以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作具有一定的参考学习价值,谢谢大家对我们的支持.如果你想

  • C++项目求Fibonacci数列的参考解答

    [项目:求Fibonacci数列] Fibonacci数列在计算科学.经济学等领域中广泛使用,其特点是:第一.二个数是1,从第3个数开始,每个数是其前两个数之和.据此,这个数列为:1 1 2 3 5 8 13 21 34 55 89 --,请设计程序,输出这个数列,直到这个数字超过10000. [提示]数列可以表示为: [参考解答] #include <iostream> using namespace std; int main( ) { int f1,f2,fn,n; f1=f2=1; n

  • C++实践数组作数据成员的参考

    [项目 - 数组作数据成员]下面是设计好的一个工资类(Salary): class Salary { public: void set_salarys( );//输入职工工资(输入-1标志着工资输入结束),工资保存到salary数组中,实际人数保存到number中: void add_salarys(int x); //给每个人涨x元工资 void sort_salarys(); //对工资由大到小排序 void show_salarys( ); //显示工资信息 private: double

  • C++面试基础之static关键字详解

    前言 static是 c++ 的关键字,顾名思义是表示静态的含义.它在 c++ 中既可以修饰变量也可以修饰函数.那当我们使用 static 时,编译器究竟做了哪些事情呢? 早先面试中被问到 static 关键字,感觉既熟悉又陌生.熟悉是都知道如何去使用它,陌生又来自不知道它究竟对我们程序做了什么.今天就来好好复习下这个关键字,本文的重点也在第三部分. 先看一下示例代码: test1.cpp #include <iostream> extern int a_int; extern void fu

  • C++/JAVA/C#子类调用父类函数情况总结

    时间久了就容易记不清了,特留存备用查看 c++ 1.构造函数调用   常用初始化列表  或者显示调用 1.1同一个类中构造函数调用构造函数   尽量不要这样做,因为结果不确定!避免麻烦 可以把共用的代码封装成一个私有的成员函数,然后在构造函数内统一调用. 1.2子类构造函数调用基类构造函数 -----基类有默认构造函数时,可以在子类不写,则隐式调用 -----基类无/有默认构造函数时,在子类构造函数初始化列表处调用,则显示调用     基类类名(参数) class Base { public:

  • C++实践分数类中运算符重载的方法参考

    [项目-分数类中的运算符重载] (1)实现分数类中的运算符重载,在分数类中可以完成分数的加减乘除(运算后再化简).比较(6种关系)的运算. class CFraction { private: int nume; // 分子 int deno; // 分母 public: //构造函数及运算符重载的函数声明 }; //重载函数的实现及用于测试的main()函数 (2)在(1)的基础上,实现分数类中的对象和整型数的四则运算.分数类中的对象可以和整型数进行四则运算,且运算符合交换律.例如:CFrac

  • 递归删除二叉树中以x为根的子树

    名称:删除二叉树中以x为根的子树 说明:此程序的大部分内容,注释都解释的较为详细了.在这里需要提及一点的是此处递归函数flag传递的不是上篇中讲的引用,而是普通的变量,因为在向下传递参数(当前结点是否是x的信息)的过程中只要传递给对应的子树,并不需要传递给整个树的结点.在下一篇会做个关于递归传递参数的总结. //递归删除二叉树中以x为根的子树,(flag为标志) int DelRoot_x(BiTree &T, int x,int flag) { if(T == NULL) return 0;

  • C++实践数组类运算的实现参考

    [项目-数组类运算的实现] 设计数组类Array,为了实现测试函数中要求的功能,请补足相关的函数(构造.析构函数)和运算符重载的函数. 实现策略提示:可以将测试函数中的语句加上注释,取消一句的注释,增加相应的函数,以渐增地实现所有的功能,避免全盘考虑带来的困难. class Array { private: int* list; //用于存放动态分配的数组内存首地址 int size; //数组大小(元素个数) public: //成员函数声明 }; //要求测试函数能够运行出正确.合理的结果:

  • C++稀疏矩阵的各种基本运算并实现加法乘法

    代码: #include <iostream> #include<malloc.h> #include<cstdio> using namespace std; #define M 4 #define N 4 #define MaxSize 100 typedef int ElemType; typedef struct { int r; int c; ElemType d;///元素值 } TupNode; ///三元组定义 typedef struct { int

随机推荐