最短路径算法——弗洛伊德（Floyd）算法_floyd算法求最短路径

//Floyd算法(多源最短路径算法) 
bool Floyd(){
	for(int k = 1 ; k < this->Nv+1 ; k++){	//k代表中间顶点 
		for(int i = 1  ; i < this->Nv+1 ; i++){//i代表起始顶点 
			for(int j = 1 ; j < this->Nv+1 ; j++){//j代表终点 
				if(this->dist[i][k] + this->dist[k][j] < this->dist[i][j]){
					this->dist[i][j] = this->dist[i][k] + this->dist[k][j];
					if(i == j && this->dist[i][j] < 0){//发现了负值圈 
						return false;
					}
					this->path[i][j] = k;
				}					
			}
		}
	}
	return true; 
}

   
   

   
   
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

#include <iostream>
#include <cstring>
#include <stack>
#include <queue>
using namespace std;
1
2
3
4
5

const int MAX = 65535;

class Graph{
private:
int** G; // 邻接矩阵
int** dist; // 距离数组
int** path; // 路径数组
int Nv; // 顶点数
public:
//构造函数
Graph(int nv, int ne){
this->Nv = nv;
G = new int*[nv+1];
dist = new int*[nv+1];
path = new int*[nv+1];
for(int i = 0 ; i < nv+1 ; i++){
G[i] = new int[nv+1];
dist[i] = new int[nv+1];
path[i] = new int[nv+1];
memset(path[i],-1,sizeof(path[0][0])*(nv+1));
for(int j = 0 ; j < nv+1 ; j++){
this->G[i][j] = this->dist[i][j] = MAX;
}
this->G[i][i] = this->dist[i][i] = 0;
}
cout<<“请输入边与权重:”<<endl;
for(int i = 0 ; i < ne ; i++){
int v1,v2,weight;
cin>>v1>>v2>>weight;
this->G[v1][v2] = this->G[v2][v1] = weight;
this->dist[v1][v2] = this->dist[v2][v1] = weight;
}
}

	//Floyd算法(多源最短路径算法) 
	bool Floyd(){
		for(int k = 1 ; k < this->Nv+1 ; k++){	//k代表中间顶点 
			for(int i = 1  ; i < this->Nv+1 ; i++){//i代表起始顶点 
				for(int j = 1 ; j < this->Nv+1 ; j++){//j代表终点 
					if(this->dist[i][k] + this->dist[k][j] < this->dist[i][j]){
						this->dist[i][j] = this->dist[i][k] + this->dist[k][j];
						if(i == j && this->dist[i][j] < 0){//发现了负值圈 
							return false;
						}
						this->path[i][j] = k;
					}					
				}
			}
		}
		return true; 
	}
	
	// 分治法寻找start到end最短路径的中间结点 
	void Find(queue<int> &q ,int start,int end){
		int mid = this->path[start][end];
		if(mid == -1){
			return;
		}
		Find(q,start,mid);
		q.push(mid);
		Find(q,mid,end);
	}

	//打印start顶点到end顶点的路径 
	void Print_Path(int start,int end){
		queue<int> queue;
		queue.push(start);
		this->Find(queue,start,end); 
		queue.push(end);
		cout<<queue.front();
		queue.pop();
		while(!queue.empty()){
			cout<<"->"<<queue.front();
			queue.pop();
		}
		cout<<endl;
	}
	
	void Print_Floyd(){
		int i,j,k;
		for(int i = 1 ; i < this->Nv+1 ; i++){
			for(int j = 1 ; j < this->Nv+1 ; j++){
				cout<<this->path[i][j]<<" ";
			}
			cout<<endl;
		} 
		cout<<"	length		path"<<endl; 
		for(i = 1 ; i < this->Nv+1 ; i++){
			for(j = i+1 ; j < this->Nv+1 ; j++){
				cout<<i<<"->"<<j<<"	";
				cout<<this->dist[i][j]<<"		"; 	
				this->Print_Path(i,j);
			}
			cout<<endl;
		}
	}
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

};

int main()
{
cout<<“请输入顶点数与边长数:”<<endl;
int nv,ne;
cin>>nv>>ne;
Graph graph(nv,ne);
if(graph.Floyd()){
cout<<“各个顶点的最短路径为：”<<endl;
graph.Print_Floyd();
}

return 0;
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
• 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

截图如下：

                                </div>
            <link href="https://csdnimg.cn/release/phoenix/mdeditor/markdown_views-e9f16cbbc2.css" rel="stylesheet">
                </div>
1
2
3