最短路径 订阅
用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解,但由于它遍历计算的节点很多,所以效率低。 展开全文
用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解,但由于它遍历计算的节点很多,所以效率低。
信息
性    质
一类经典算法问题
外文名
shortest path
解决思路
由已知点/边向外扩展
中文名
最短路径
解决方法
SPFA算法、Dijkstra算法等
最短路径最短路径介绍
最短路径问题是图论研究中的一个经典算法问题, 旨在寻找图(由结点和路径组成的)中两结点之间的最短路径。 算法具体的形式包括:确定起点的最短路径问题 - 即已知起始结点,求最短路径的问题。 [1]  确定终点的最短路径问题 - 与确定起点的问题相反,该问题是已知终结结点,求最短路径的问题。在无向图中该问题与确定起点的问题完全等同,在有向图中该问题等同于把所有路径方向反转的确定起点的问题。确定起点终点的最短路径问题 - 即已知起点和终点,求两结点之间的最短路径。全局最短路径问题 - 求图中所有的最短路径。
收起全文
精华内容
参与话题
问答
  • 最短路径: 在一个带权图中,顶点V0到图中任意一个顶点Vi的一条路径所经过边上的权值之和,定义为该路径的带权路径长度,把带权路径最短的那条路径称为最短路径。 DiskStra算法: 求单源最短路径,即求一个顶点到...

    最短路径:

    在一个带权图中,顶点V0到图中任意一个顶点Vi的一条路径所经过边上的权值之和,定义为该路径的带权路径长度,把带权路径最短的那条路径称为最短路径。

    DiskStra算法:

    求单源最短路径,即求一个顶点到任意顶点的最短路径,其时间复杂度为O(V*V)

    如图所示:求顶点0到各顶点之间的最短路径

    代码实现:

    #include<stdio.h>
    #include<stdlib.h>
    #define MaxVexNum 50
    #define MaxInt 32767
    #define MaxEdgeNum 50
    //邻接矩阵
    typedef int VertexType;
    typedef int EdgeType;
    typedef struct AMGraph{
    	VertexType vexs[MaxVexNum];//顶点表 
    	EdgeType arcs[MaxVexNum][MaxVexNum];//邻接矩阵表 
    	int vexnum,edgenum;//顶点数,边数 
    }AMGraph; 
    
    void createGraph(AMGraph &g){//创建无向图 
    	printf("请输入顶点数:");
    	scanf("%d",&g.vexnum);
    	printf("\n请输入边数:");
    	scanf("%d",&g.edgenum);
    	
    	//初始化顶点表 
    	for(int i=0;i<g.vexnum;i++){
    		g.vexs[i]=i; 
    	} 
    	for(int i=0;i<g.vexnum;i++){
    		for(int j=0;j<g.vexnum;j++){
    			g.arcs[i][j]=MaxInt;
    			if(i==j) g.arcs[i][j]=0;
    		}
    	} 
    	printf("请输入边的信息以及边的权值(顶点是0~n-1)\n");
    	for(int i=0;i<g.edgenum;i++){
    		int x,y,w;
    		scanf("%d%d%d",&x,&y,&w);
    		g.arcs[x][y]=w;
    		//g.arcs[y][x]=w;
    	}
    }
    void PrintGraph(AMGraph g){
    	printf("邻接矩阵为:\n");
    	for(int i=0;i<g.vexnum;i++) {
    		printf("  %d",g.vexs[i]);
    	}
    	printf("\n");
    	for(int i=0;i<g.vexnum;i++){
    		printf("%d ",g.vexs[i]);
    		for(int j=0;j<g.vexnum;j++){
    			if(g.arcs[i][j]==32767){
    				printf("∞ "); 
    			}else{
    				printf("%d  ",g.arcs[i][j]);
    			}	
    		}
    		printf("\n");
    	} 
    }
    //Dijkstra算法,求单源最短路径
    void Dijkstra(AMGraph g,int dist[],int path[],int v0){
    	int n=g.vexnum,v;
    	int set[n];//set数组用于记录该顶点是否归并 
    	//第一步:初始化 
    	for(int i=0;i<n;i++){
    		set[i]=0;
    		dist[i]=g.arcs[v0][i];
    		if(dist[i]<MaxInt){//若距离小于MaxInt说明两点之间有路可通 
    			path[i]=v0;//则更新路径i的前驱为v 
    		}else{
    			path[i]=-1; //表示这两点之间没有边
    		 } 
    	}
    	set[v0]=1;//将初始顶点并入 
    	path[v0]=-1;//初始顶点没有前驱
    	
    	//第二步 
    	for(int i=1;i<n;i++){//共n-1个顶点 
    		int min=MaxInt;
    		//第二步:从i=1开始依次选一个距离顶点的最近顶点 
    		for(int j=0;j<n;j++){
    			if(set[j]==0&&dist[j]<min){
    				v=j;
    				min=dist[j];
    		}
    	}
    	//将顶点并入 
    	set[v]=1;	
    	//第三步:在将新结点并入后,其初始顶点v0到各顶点的距离将会发生变化,所以需要更新dist[]数组
    	for(int j=0;j<n;j++){
    		if(set[j]==0&&dist[v]+g.arcs[v][j]<dist[j]){
    			dist[j]=dist[v]+g.arcs[v][j];
    			path[j]=v;
    		}
    	} 	
     } 
     //输出 
     printf("       ");
     for(int i=0;i<n;i++) printf("%d  ",i);
      
     printf("\ndist[]:");
     for(int i=0;i<n;i++) printf("%d  ",dist[i]);
     
     printf("\npath[]:");
     for(int i=0;i<n;i++) printf("%d  ",path[i]);
    
    }
    
    int main(){
    	AMGraph g;
    	createGraph(g);
    	int dist[g.vexnum];
    	int path[g.vexnum];
    	Dijkstra(g,dist,path,0);
    } 

    Floyd算法:

    求各顶点之间的最短路径,其时间复杂度为O(V*V*V)

    如图所示,求<1,0>之间的最短路径:

    代码实现:

    #include<stdio.h>
    #include<stdlib.h>
    #define MaxVexNum 50
    #define MaxInt 32767
    #define MaxEdgeNum 50
    //邻接矩阵
    typedef int VertexType;
    typedef int EdgeType;
    typedef struct AMGraph{
    	VertexType vexs[MaxVexNum];//顶点表 
    	EdgeType arcs[MaxVexNum][MaxVexNum];//邻接矩阵表 
    	int vexnum,edgenum;//顶点数,边数 
    }AMGraph; 
    
    void createGraph(AMGraph &g){//创建无向图 
    	printf("请输入顶点数:");
    	scanf("%d",&g.vexnum);
    	printf("\n请输入边数:");
    	scanf("%d",&g.edgenum);
    	
    	//初始化顶点表 
    	for(int i=0;i<g.vexnum;i++){
    		g.vexs[i]=i; 
    	} 
    	for(int i=0;i<g.vexnum;i++){
    		for(int j=0;j<g.vexnum;j++){
    			g.arcs[i][j]=MaxInt;
    			if(i==j) g.arcs[i][j]=0;
    		}
    	} 
    	printf("请输入边的信息以及边的权值(顶点是0~n-1)\n");
    	for(int i=0;i<g.edgenum;i++){
    		int x,y,w;
    		scanf("%d%d%d",&x,&y,&w);
    		g.arcs[x][y]=w;
    		//g.arcs[y][x]=w;
    	}
    }
    void PrintGraph(AMGraph g){
    	printf("邻接矩阵为:\n");
    	for(int i=0;i<g.vexnum;i++) {
    		printf("  %d",g.vexs[i]);
    	}
    	printf("\n");
    	for(int i=0;i<g.vexnum;i++){
    		printf("%d ",g.vexs[i]);
    		for(int j=0;j<g.vexnum;j++){
    			if(g.arcs[i][j]==32767){
    				printf("∞ "); 
    			}else{
    				printf("%d  ",g.arcs[i][j]);
    			}	
    		}
    		printf("\n");
    	} 
    }
    
    //Floyd算法
    
    //递归输出两个顶点直接最短路径 
    void printPath(int u,int v,int path[][MaxVexNum]){
    	if(path[u][v]==-1){
    		printf("[%d %d] ",u,v);
    	}else{
    		int mid=path[u][v];
    		printPath(u,mid,path);
    		printPath(mid,v,path);
    	}
    }
    void Floyd(AMGraph g,int path[][MaxVexNum]){
    	int n=g.vexnum;
    	int A[n][n];
    	//第一步:初始化path[][]和A[][]数组 
    	for(int i=0;i<n;i++){
    		for(int j=0;j<n;j++){
    			A[i][j]=g.arcs[i][j];
    			path[i][j]=-1; 
    		}
    	}
    	//第二步:三重循环,寻找最短路径 
    	for(int v=0;v<n;v++){//第一层是代表中间结点 
    		for(int i=0;i<n;i++){
    			for(int j=0;j<n;j++){
    				if(A[i][j]>A[i][v]+A[v][j]){
    					A[i][j]=A[i][v]+A[v][j];
    					path[i][j]=v;
    				}
    			}
    		} 
    	} 
    } 
     
    int main(){
    	AMGraph g;
    	createGraph(g);
    	PrintGraph(g);
    	int path[MaxVexNum][MaxVexNum];
    	Floyd(g,path);
    
    	printPath(1,0,path);
    } 

    代码运行截图:

    展开全文
  • 最短路径

    千次阅读 2019-09-10 16:16:07
    在带权图中,把一个顶点从v0到图中任意一个顶点vi的一条路径(可能不止一条)所经过边上的权值之和,定义为该路径的带权路径长度,把带权路几个长度最短的那条路径称为最短路径。 带权有向图的最短路径分为两类 : ...

          在带权图中,把一个顶点从v0到图中任意一个顶点vi的一条路径(可能不止一条)所经过边上的权值之和,定义为该路径的带权路径长度,把带权路几个长度最短的那条路径称为最短路径。

    带权有向图的最短路径分为两类 :

    (1)单源最短路径,即求图中某一个顶点到其他各个顶点的最短路径。

    (2)求每对顶点间的最短路径

    (----可能有人看完者定义就受不了了,什么东西-----)

    看下图,你要去学校,有如下路线,假设权值为路程,你肯定会走第三条,因为路程最短;假设权值为所花费人民币,你仍有可能选择,第三条,因为花钱少。

    你是不觉得这有啥bb的,看下图假如你要从南宁去哈尔滨,你就不能一下找到最短路径。这就是研究这个问题的意义的价值。比如实时交通陆路线,工程中的修桥架线等都有用到。

    一、迪杰特斯拉算法(求单源最短路径算法)

         求带权有向图某个源点到其余各个顶点的最短路径。常用Dijksta算法。

    先来看实例

    对下图用该算法,求从顶点1到其余顶点的最短路径

    接着看下图

    顶点

    第1轮

    第2轮

    第3轮

    第4轮

    2

    10

    v1->v2

    8

    v1->v5->v2

    8

    v1->v5->v2

     

    3

    14

    v1->v5->v3

    13

    v1->v5->v4->v3

    9

    v1->v5->v2->v3

    4

    7

    v1->v5->v4

     

     

    5

    5

    v1->v5

     

     

     

    集合S

    {1,5}

    {1,5,4}

    {1,5,4,2}

    {1,5,4,2,3}

    初始,从v1出发,

    第一轮:检测v1与其余各个顶点的当前路程,v1要到v3,v4不可直接到达即为∞,到v2距离为10,到v5距离为5 ,选出v1->v5

    第二轮:检测与v5其余各个顶点的当前路程,v1->v5->2 为8,v1->v5->v3为14,v1->v5->v4为7,选出v1->v5->v4

    第三轮:检测与v4其余各个顶点的当前路程,v1->v5->v2为8,v1->v5->v4->v3为13,选出v1->v5->v2

    第四轮:检测与v4其余各个顶点的当前路程,v1->v5->v2为8,v1->v5->v4->v3为13,选出v1->v5->v2->v3

    再来看这该死的过程

    算法步骤;(1)初始化,集合S[]初始为{0},dist[i]=arcs[0][i],i=1,2,3...

                      (2)从顶点集合V-S出发,满足dist的初始值dist[j]=Min{dist[i] | vi∈V-S},vj 就是当前求得的一条从v0出发的最短路径的                         终点, 令S=S∪{j}

                   (3)修改从v0出发到集合V-S上任一顶点vk可达的最短路径:若dist[j]+arcs[j][k]<dist[k],则令dist[k]=dist[j]+arcs[j][k]。

                   (4)重复(2)(3)操作共n-1次,直到所有顶点都包含在S中。

    做个例题:

    求出下图从顶点1到其他各个顶点的最短路径

    顶点

    第1轮

    第2轮

    第3轮

    第4轮

    第5轮

    2

    5

    v1->v2

    5

    v1->v2

     

     

     

    3

    7

    v1->v2->v3

     

     

    4

    11

    v1->v5->v4

    11

    v1->v5->v4

    11

    v1->v5->v4

    11

    v1->v5->v4

    5

    4

    v1->v5

     

     

     

     

    6

    9

    v1->v5->v6

    9

    v1->v5->v6

    9

    v1->v5->v6

     

    集合S

    {1,5}

    {1,5,2}

    {1,5,2,3}

    {1,5,2,3,6}

    {1,5,2,3,6,

    这个表从第一列第一个往下开始看,直到该列完成。再从下一列第一个往下看,依次看。

    第一轮从1出发可以直接到达的是1和5,写上路径和值,其余写无穷;

    第一轮选出最短,得到v1->v5,所以v5加入集合S{1,5}

    第二轮,把上一轮得到结果的平移抄过去,已经加入集合S的不用抄。现在从5开始判断,5能到达2距离为6,现在的v1->v5->v2为10相比上一轮的v1->v2为5,所以那个为止仍取原来的。

    无论1还是5都不能直达3,所以写无穷。对于4,上一轮无法直达,现在5可直达4,此条路径v1->v5->v4为11。

    因为结点5已经在集合S中,所以此处为空。

    之前无法直达6,现在5可直达6,v1->v5->6为9。所以第二轮中选出最短的,得到v2加入集合S

    {1,5,2}

    第三轮:因为2已经在集合中,所以此处为空。因为2可直达3,v1->v2->v3为7,比原来的无穷小所以此处写v1->v2->v3

    因为5可直达4,v1->v5->v4为11,相比之前的11一样,所以此处仍为v1->v5->v4

    因为5已经在集合中,此处为空。

    因为5能直达6,和上一轮一样9,此处仍为 v1->v5->v6

    所以第三轮,选出最短v1->v2->v3,将3加入集合S 有{1,5,2,3}

    第四轮:因为2,3已在集合中,所以对应位置为空。看从3出发,能否得到更短的结果,不能。再看4,2可到4 ,v1->v2->v4为14,5可到4,v1->v5->v4为11 所以此处仍为v1->v5->v4

    因为5在集合中,所以此处为空。

    再看6,5可直达6,v1->v5->v6为9

    第四轮选出最短为9,将6加入集合S, 得到{1,5,2,3,6}

    第五轮:2,3已在集合中对应为空。此时达到4的最短为v1->v5->v4。5,6已在几何中,对应位置为空。

    第五轮选出最小,将4加入集合 得到

    {1,5,2,3,6,4}

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

    注:当边上有负权值,迪杰特斯拉算法不再适用。

    二、Floyd求各顶点之间最短路径

    求各顶点之间最短路径:已知一个各边权值均大于0的带权有向图,对每对顶点v_{i}\neq v_{j},要求找出vi与vj之间的最短路径和最短路径长度。

    还是来看题,

    上图为一个带权有向图,及其邻接矩阵.如下为执行过程。

    如图,

    写出A^{(0)},和Path^{(0)}

    接着写出A(1)和Path(1) ,将第一行和第一列全copy过来,检测经过顶点1能否改善各顶点间的路径长度

    若比原来短,则更改对应位置值,否则保留原来的值。

    例如,之前3->2的路径值为5,经过1为3->1->2的路径值为4,更改为4

    之前,2->4路径值为2,经过1为2->1->4的路径值为4为5,仍保留2.

    路径值更新的地方,对应的Path中对应位置值更改为同一列中的第一行的值

    接着写出A(2)和Path(2) ,将第二行和第二列copy过来,检测经过顶点2能否改善各顶点间的路径长度

     

    展开全文
  • 最短路径问题---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 ...从图中的某个顶点出发到达另外一个顶点的所经过的边的权重和最小的一条路径,称为最短路径 解决问题的算法:...

    前言
    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。 为实现并行最短路径计算,我们必须要解决如下问题: (1)数据获取:利用随机函数生成大约2000个节点及其节点之间的距离。本程序使用邻接矩阵来存储带权有向图的信息。矩阵大小2000*2000...
  • 小蜜蜂采蜜最短路径

    千次阅读 2019-04-04 15:26:03
    练习题: 蜂巢在坐标(0,0)的位置,有五处花丛,蜜蜂从蜂巢出发,要把五处花丛的花蜜采完再回到蜂巢,最短距离是多少。输入说明:一行输入,10个数分别是五处花丛的坐标(x1,y1,x2,y2,x3,y3,x4,y4,x5,y5) ...

    练习题:

    蜂巢在坐标(0,0)的位置,有五处花丛,蜜蜂从蜂巢出发,要把五处花丛的花蜜采完再回到蜂巢,最短距离是多少。输入说明:一行输入,10个数分别是五处花丛的坐标(x1,y1,x2,y2,x3,y3,x4,y4,x5,y5)

     

    import java.math.BigDecimal;
    
    public class Test {
    
        public static void main(String[] args) {
            //求最短路径
            long td=System.currentTimeMillis();
            int[][] a = {{0, 0}, {1, 1}, {2, 1}, {3, 1}, {4, 1}, {6, 2}};
            Test t = new Test();
            System.out.println((t.getMin(t.sum(a))));
            //保留4位小数
            System.out.println(new BigDecimal(t.getMin(t.sum(a))).setScale(4,BigDecimal.ROUND_HALF_DOWN));
            System.out.println("耗时:"+(System.currentTimeMillis()-td));
        }
    
        //计算所有可能出现的路径
        private double[] sum(int[][] b) {
            double[] result = new double[b.length];
            double x0=0;
            double x=0;
            for (int j = 0; j < b.length; j++) {
                for (int i = 0; i < b.length - 1; i++) {
                    //求得路径
                    if (i == 0&&j==1) {
                        x0 = Math.sqrt(Math.pow(b[j][0] - b[i][0], 2) + Math.pow(b[j][1] - b[i][1], 2));
                    } else {
                        x+= Math.sqrt(Math.pow(b[i][0] - b[i + 1][0], 2) + Math.pow(b[i][1] - b[i + 1][1], 2));
                    }
                }
                result[j] = x0 + x;
            }
            return result;
        }
    
        //计算最小路径
        private double getMin(double[] c) {
            for (int i = 0; i < c.length-1; i++) {
                if (c[i] > c[i + 1]) {
                    double mm = c[i];
                    c[i] = c[i + 1];
                    c[i + 1] = mm;
                }
            }
            return c.length > 0 ? c[0] : 0;
        }
    
    }
    

     

    展开全文
  • 算法题-遍历五个坐标的最短路径

    千次阅读 2019-03-29 11:05:51
    题目描述 平原上,一群蜜蜂离开蜂巢采蜜,要连续采集5片花丛后归巢,已知5片花丛...从出发到返回蜂巢最短路径的长度取整值,取整办法为舍弃小数点后面的值。 示例 输入 200 0 200 10 200 50 200 30 200 25 输出 4...
  • 本设计以VC++6.0作为程序开发环境,C语言作为程序开发语言,详细介绍了最短路径的求解算法及其C语言实现过程。系统主要实现了图的创建、单源点最短路径的计算功能。依照本系统可以解决实际生活中许多路径选择问题,...
  • 首先介绍这三个概念,很多人都听过最短路径了,但是最短路径树却很少听过,关于最短路径树的介绍也不太多。而最短路径树和最小生成树更是完全不同的两个概念。 最短路径就是从一个指定的顶点出发,计算从该顶点出发...
  • 最短路径 –在网络中,求两个不同顶点之间的所有路径中,边的权值之和最小的路劲。 单源最短路径 –从某固定源点出发的最短路径 无权图的最短路径 按照路径长度递增的顺序找出源点到各个顶点的最短路径 类似于...
  • Problem : 最短路径问题 欢迎各个大佬前来指教! 问题描述: 平面上有n个点(n&amp;amp;amp;lt;=100),每个点的坐标均在-10000~10000之间。其中的一些点之间有连线。若有连线,则表示可从一个点到达另一个点,...
  • #include "stdafx.h" #include #include #include #define MAX_VERTEX_NUM 20 #define INFINITY INT_MAX typedef struct MGraph { int vexnum, arcnum;... int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
  • 1. 我们在使用Dijkstra算法求解源点到其余顶点的最短路径的时候,在大多数情况下最短路径是只有一条的,但是也有可能存在着多条最短路径的情况,所以之前使用整型的pre[]数组来记录当前节点的前驱节点的方法就不再...
  • 从任意一条单边路径开始。所有两点之间的距离是边的权,如果两点之间没有边相连,则权为无穷大,这也是所谓的初始化工作; 对于每一对顶点 u 和 v,看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比己知的路径更短。...
  • 迪杰斯特拉算法是典型的单源最短路径算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法,在很多专业课程中都...
  • 最短路径问题 从图中的某一个顶点出发到达另一个顶点的所经过的边的权重和最小的一条路径,称为最短路径。 Dijkstra算法适用于求一个节点到其他节点的最短路径,主要特点是通过广度搜索(由近及远、层层扩展)来遍历...

空空如也

1 2 3 4 5 ... 20
收藏数 43,595
精华内容 17,438
关键字:

最短路径