【数据结构】图论中求最短路径——迪杰斯特拉算法（Dijkstra）、弗洛伊德算法（Floyd）_迪杰斯特拉算法如何区分已求路径和待求路径?

作者：笔触狂放9 | 2024-07-18 16:08:20

踩

迪杰斯特拉算法如何区分已求路径和待求路径?

最短路径 (*)

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

从A地到B地换车次数最少的路径
从A地到B地最短的路径（距离最短，行驶时间最短，费用最低）

迪杰斯特拉(Dijkstra)算法–从一个源点到其它各点的最短路径
弗洛伊德(Floyd)算法–每一对顶点之间的最短路径
Bellman-Ford算法

迪杰斯特拉算法（Dijkstra）

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

基本思想：设集合S中存放已找到最短路径的顶点，集合 $T ＝ V - S$ 存放当前还未找到最短路径的顶点。
1.初态: S中 只包含源点 v0，v0到其余 各点的弧 为各点当前各点的“最短”路径。
2.从T中选取当前各点的“最短”路径长度中最短的顶点u加入到S中。
3.S加入新的顶点u后，考察顶点 $v_0$ 到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$ 有弧，则D[i]为弧上的权值；否则置 D[i]为∞ ，即：D[i]=G.arcs[k][i]; //说明：k为源点

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

P[i][ ] ：从源点到点 $v_i$ 的最短路径

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

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

迪杰斯特拉算法（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/笔触狂放9/article/detail/846578