devbox
秋刀鱼在做梦
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

【数据结构】图论中求最短路径——迪杰斯特拉算法（Dijkstra）、弗洛伊德算法（Floyd）

作者：秋刀鱼在做梦 | 2024-06-29 10:26:23

赞

踩

【数据结构】图论中求最短路径——迪杰斯特拉算法（Dijkstra）、弗洛伊德算法（Floyd）

目录

最短路径 (*)

生活中最短路径问题例如：
交通网络：给定了该网内的n个城市以及这些市之间的相通公路的距离，能否找到城市A城市B之间一条最近的通路呢？

  1. 从A地到B地换车次数最少的路径
  2. 从A地到B地最短的路径（距离最短，行驶时间最短，费用最低）
  1. 迪杰斯特拉(Dijkstra)算法–从一个源点到其它各点的最短路径
  2. 弗洛伊德(Floyd)算法–每一对顶点之间的最短路径
  3. Bellman-Ford算法

迪杰斯特拉算法（Dijkstra）

该算法只适用于静态网络网络上边的权值不能为负数

基本思想：设集合S中存放已找到最短路径的顶点，集合 T ＝ V − S T ＝V-S T＝V−S存放当前还未找到最短路径的顶点。
1.初态: S中 只包含源点 v0，v0到其余 各点的弧 为各点当前各点的“最短”路径。
2.从T中选取当前各点的“最短”路径长度中最短的顶点u加入到S中。
3.S加入新的顶点u后，考察顶点 v 0 v_0 v0​到T中剩余顶点的最短路径长度是否可以优化更新：T中各顶点新的最短路径长度值为原来的最短路径长度值、顶点u的最短路径长度值加上u到该顶点的路径长度值中的较小值。
4.重复2，3，直到T的顶点全部加入到S中、或源点到剩余顶点的路径都是∞为止。

在这里插入图片描述

一、图的存储：邻接矩阵和邻接表都可以

#define max 100
typedef struct {
	int arcs[max][max];
	int vexnum,arcnum;
}AGraphs;
Agraphs G；//定义图存储结构  邻接矩阵的存储形式

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

二、区分已经求出最短路径的点

方法一:设一个一维数组int final[max];
final[i]=1表示从源点到顶点i的最短路径已经求出，i在S中
final[i]=0表示从源点到顶点i的最短路径尚未求出，i在V-S中

方法二：利用邻接矩阵主对角线的位置G.arcs[i][i]表示i是否在S中
G.arcs[i][i]=1表示从源点到顶点i的最短路径已经求出，i在S中
G.arcs[i][i]=0表示从源点到顶点i的最短路径尚未求出，i在V-S中

三、表示源点到顶点i的最短路径

一维数组int D[max]表示最短路径的长度
D[i] ：从源点到点 v i v_i vi​的最短路径的长度
初态为：若从源点 到 v i v_i vi​有弧，则D[i]为弧上的权值；否则置 D[i]为∞ ，即：D[i]=G.arcs[k][i]; //说明：k为源点

二维数组int P[max][max]表示最短路径包含的顶点

P[i][ ] ：从源点到点 v i v_i vi​的最短路径

P[i][j]=0 ： v j v_j vj​不在从源点 到点 v i v_i vi​的最短路径上

P[i][j]=1 ： v j v_j vj​位于从源点 到点 v i v_i vi​的最短路径上。

迪杰斯特拉算法（Dijkstra）的算法原理：


void ShortestPath(AGraphs G,int k,int P[][], int D[]){ 
	int i,w, j,min;
	
	for (i=0;i<G.vexnum; i ++){  
	
		final[i]=0; //初始化
		
		D[i]=G.arcs[k][i];//最短路径长度
		
		for(w=0;w<G.vexnum; w ++) 
			P[i][w]=0;//初始化
			
		if (D[i]<INFINITY){ //短路径包含的顶点
			P[i][k]=1; 
			P[i][i]=1; 
		}
			
	}
	
	D[k]=0; //初始点
	
	final[k]=1;
	
	for(i=1; i<G.vexnum; i ++){  
	
		min=INFINITY;//初始化为 无穷大
		
		for (w=0;w<G.vexnum; w ++)
			if (!final[w]&&D[w]<min){//
				j=w; 
				min=D[w];
			} 
			
		if(min== INFINITY) //
			return;
			
		final[j]=1; //标记为选入
		
		for(w=0;w<G.vexnum; w ++)
			if(!final[w]&&(min+G.arcs[j][w]<D[w])){ 
				D[w]=min+G.arcs[j][w];
				P[w]=P[j]; //？？
				P[w][w]=1;  
			}
			
	}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48

弗洛伊德算法（Floyd）

在这里插入图片描述

图的存储：邻接矩阵和邻接表都可以

#define max 100
typedef struct {
	int arcs[max][max];
	int vexnum,arcnum;
}AGraphs;
Agraphs G；//定义图存储结构  邻接矩阵的存储形式

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

弗洛伊德算法（Floyd）的算法原理：

void s1(int D[][],int p[][][], Agraphs G){   

	int i,j,k;
	
	for(i=0;i<G. vexnum;i++) 
		for(j=0;j<G. vexnum;j++){  
			D[i][j]=G.arcs[i][j];
			for(k=0;k<G.vnum;k++) 
				p[i][j][k]=0; //初始化
				if(D[i][j]<INFINITY){ 
					p[i][j][i]=1; //初始化
					p[i][j][j]=1; //初始化
				}
		}
		
	for (k=0;k<G. vexnum;k++) 
		for (i=0;i<G. vexnum;i++)
			for(j=0;j<G vexnum;j++) 
				if(D[i][k]+D[k][j]<D[i][j]){//是否K 加入能够减小路径长度
					D[i][j]=D[i][k]+D[k][j];//如果可以 就加入
					for(w=0;w<G. vexnum;w++) 
						p[i][j][w]=p[i][k][w]||p[k][j][w];//然后确定路径上的元素
				}
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24

弗洛伊德算法的（c语言）完整实例：

//算法6.11　弗洛伊德算法

#include  <iostream>
using  namespace  std;

#define  MaxInt  32767       //表示极大值，即∞
#define  MVNum  100           //最大顶点数

typedef  char  VerTexType;  //假设顶点的数据类型为字符型  
typedef  int  ArcType;   //假设边的权值类型为整型  

int  Path[MVNum][MVNum];                                                //最短路径上顶点vj的前一顶点的序号
int  D[MVNum][MVNum];                                                //记录顶点vi和vj之间的最短路径长度

//------------图的邻接矩阵---------------
typedef  struct{  
        VerTexType  vexs[MVNum];    //顶点表  ？
        ArcType  arcs[MVNum][MVNum];//邻接矩阵  
        int  vexnum,arcnum;         //图的当前点数和边数  
}AMGraph;



int  LocateVex(AMGraph  G  ,  VerTexType  v){
        //确定点v在G中的位置
        for(int  i  =  0;  i  <  G.vexnum;  ++i)
                if(G.vexs[i]  ==  v)
                        return  i;
                return  -1;
}//LocateVex

void  CreateUDN(AMGraph  &G){  
        //采用邻接矩阵表示法，创建有向网G  
        int  i , j  , k;
        //cout  <<"请输入总顶点数，总边数，以空格隔开:";
        cin  >>  G.vexnum  >>  G.arcnum;                                                        //输入总顶点数，总边数

        //cout  <<  "输入点的名称，如a"  <<  endl;

        for(i  =  0;  i  <  G.vexnum;  ++i){      
                //cout  <<  "请输入第"  <<  (i+1)  <<  "个点的名称:";
                cin  >>  G.vexs[i];                                                                        //依次输入点的信息  
        }
        for(i  =  0;  i  <  G.vexnum;  ++i){                                                        //初始化邻接矩阵，边的权值均置为极大值MaxInt  
                for(j  =  0;  j  <  G.vexnum;  ++j){    
                        if(j  !=  i)
                            G.arcs[i][j]  =  MaxInt;    
                        else
                            G.arcs[i][j]  =  0;
                }//for
        }//for  //初始化

        //cout  <<  "输入边依附的顶点及权值，如a  b  3"  <<  end；

        for(k  =  0;  k  <  G.arcnum;++k){                                                //构造邻接矩阵  
            VerTexType  v1  ,  v2;
            ArcType  w;

        //cout  <<  "请输入第"  <<  (k  +  1)  <<  "条边依附的顶点及权值:";
            cin  >>  v1  >>  v2  >>  w;                                                      //输入一条边依附的顶点及权值
            i  =  LocateVex(G,  v1);    j  =  LocateVex(G,  v2);        //确定v1和v2在G中的位置，即顶点数组的下标  
            G.arcs[i][j]  =  w;                                                                //边<v1,  v2>的权值置为w  
        }//for
}//CreateUDN  

/*
【样例输入】

4 5

A B C D 

A B 2 

A C 4

B C 3

B D 5

C D 1

A D

【样例输出】

5

*/

void  ShortestPath_Floyed(AMGraph  G){   

int i, j, k;

	for( i=0;i<G.vexnum;i++ )
	{
		for( j=0;j<G.vexnum;j++ )
		{
			D[i][j] = G.arcs[i][j];	// 距离矩阵初始化
			
                        Path[i][i] = i;		// 路径矩阵初始化
                        
                        if(G.arcs[i][j]!=MaxInt){
                                Path[i][j]=i;
                        }
		}
	}


	for( k=0;k<G.vexnum;k++ )     
	{
		for( i=0;i<G.vexnum;i++ )
		{
			for( j=0;j<G.vexnum;j++ )
			{
				if( D[i][k] + D[k][j] < D[i][j] )
				{
					D[i][j] = D[i][k] + D[k][j];   // 动态更新距离矩阵
					Path[i][j] = Path[k][j];       // 动态更新路径矩阵
				}
			}
		}
	}

        //test   看每个矩阵的结果

        // 	printf("\nG.arc矩阵的结果如下：\n");
	// for( i=0;i<G.vexnum;i++ )     // 输出
	// {
	// 	for( j=0;j<G.vexnum;j++ )
	// 	{
	// 		printf("%d  ",G.arcs[i][j]);
	// 	}
	// 	printf("\n");
	// }

        // 	printf("\n距离矩阵的结果如下：\n");
	// for( i=0;i<G.vexnum;i++ )     // 输出
	// {
	// 	for( j=0;j<G.vexnum;j++ )
	// 	{
	// 		printf("%d  ",D[i][j]);
	// 	}
	// 	printf("\n");
	// }

	// printf("\n路径矩阵的结果如下：\n");
	// for( i=0;i<G.vexnum;i++ )     // 输出
	// {
	// 	for( j=0;j<G.vexnum;j++ )
	// 	{
	// 		printf("%d  ",Path[i][j]);
	// 	}
	// 	printf("\n");
	// }

}


void  DisplayPath(AMGraph  G  ,  int  begin  ,int  temp  ){
        //显示最短路径
        if(Path[begin][temp]  !=  -1){
                DisplayPath(G  ,  begin  ,Path[begin][temp]);
                cout  <<  G.vexs[Path[begin][temp]]  <<  "-->";
        }
}//DisplayPath

int  main(){
        //cout  <<  "************算法6.11　弗洛伊德算法**************"  <<  endl  <<  endl;
        AMGraph  G;
        char  start  ,  destination;
        int  num_start  ,  num_destination;

        CreateUDN(G);
        
        //test
        //cout  <<  "有向网G创建完成！"  <<  endl;
        //test

        //需要完成的函数
        ShortestPath_Floyed(G);
        //需要完成的函数

        //test
        //cout  <<  "请依次输入路径的起点与终点的名称：";
        //test

        cin  >>  start  >>  destination;
        num_start  =  LocateVex(G  ,  start);
        num_destination  =  LocateVex(G  ,  destination);

        //DisplayPath(G  ,  num_start  ,  num_destination);
        //cout  <<  G.vexs[num_destination]  <<  endl;

        cout  <<  D[num_start][num_destination]  <<  endl;

        return  0;
}//main 


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151
  • 152
  • 153
  • 154
  • 155
  • 156
  • 157
  • 158
  • 159
  • 160
  • 161
  • 162
  • 163
  • 164
  • 165
  • 166
  • 167
  • 168
  • 169
  • 170
  • 171
  • 172
  • 173
  • 174
  • 175
  • 176
  • 177
  • 178
  • 179
  • 180
  • 181
  • 182
  • 183
  • 184
  • 185
  • 186
  • 187
  • 188
  • 189
  • 190
  • 191
  • 192
  • 193
  • 194
  • 195
  • 196
  • 197
  • 198
  • 199
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/秋刀鱼在做梦/article/detail/769022
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号