Floyd
Floyd算法
算法思想
一次解决全图
1
2
3
4
5
6using AMGraph = struct {
int arcnum{ 0 };
int vexnum{ 0 };
VerTexType vertices[MVNum];
ArcType arcs[MVNum][MVNum];
};插点的循环
1
2
3
4
5
6
7
8
9
10for (k = 0; k < G.vexnum; k++) // 第一个
for(v=0;v<G.vexnum;v++)
for(w=0;w<G.vexnum;w++)
{
if (C[v][w] >C[v][k] +C[k][w])
{
C[v][w] = C[v][k] +C[k][w];
P[v][w] = P[v][k]; //相当于就是在里面加点 最后一个我们读取矩阵
}
}
代码细节
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/*****************************************************************//**
* \file Floyd.cpp
* \brief For Ms.Winter
* 3/27/2023
* \author 86158
* \date March 2023
*********************************************************************/
// Floyd
//关键思想就是不断的插入点来分析
using namespace std;
//
using Path = int[MVNum][MVNum];
using ShortPathTable = int[MVNum][MVNum];
// 最精妙的思想 一次求完所有的点 所以这是一个n^3复杂度
// 同样使用邻接矩阵
using VerTexType = char;
using ArcType = int;
using AMGraph = struct {
int arcnum{ 0 };
int vexnum{ 0 };
VerTexType vertices[MVNum];
ArcType arcs[MVNum][MVNum];
};
void Floyd(const AMGraph& G,Path P,ShortPathTable C)
{
int v, w, k;
for(v=0;v<G.vexnum;v++)
for (int w = 0; w < G.vexnum; w++)
{
C[v][w] = G.arcs[v][w];
P[v][w] = w; // 注意这个初始化
}
// 非常巧妙的循环也是关键
for (k = 0; k < G.vexnum; k++) // 第一个
for(v=0;v<G.vexnum;v++)
for(w=0;w<G.vexnum;w++)
{
if (C[v][w] >C[v][k] +C[k][w])
{
C[v][w] = C[v][k] +C[k][w];
P[v][w] = P[v][k]; //相当于就是在里面加点 最后一个我们读取矩阵
}
}
}
// 注意我们的这个路径矩阵 与迪杰斯特拉一样 然后是列来读取
// 数值 横着读取
void Dispath(const AMGraph& G, Path P, ShortPathTable C)
{
int k = 0;
cout << "各点的最短路径如下\n";
for (int v = 0; v < G.vexnum-1; v++)
for (int w = v + 1; w < G.vexnum; w++) // 只读取一般矩阵 也很好哦
{
cout << "v" << v << "-v" << w << " weight: " << C[v][w];
k = P[v][w];
cout << " Path: " << v;
while (k != w)
{
k = P[k][w];
cout << "->" << k;
}
cout << "->" << w << endl;
}
}
总结
最后其实就是这种插点的思想
- Post title：Floyd
- Post author：Winter
- Create time：2023-03-27 22:35:37
- Post link：https://spikeihg.github.io/2023/03/27/Floyd/
- Copyright Notice：All articles in this blog are licensed under BY-NC-SA unless stating additionally.