今天,解决了,多个点的最短路问题
用的dfs,配上了floyed计算出的广源距离
难点是要记录路线,dfs记录路线就很烦
但是好在结束了,经过无数的测试,确保没啥问题(应该把)
来看看我的代码
void dfs(int b[], int x, int* sum, int last, int sums, int a[], BFS& s, Floyd_AssistArray* fl) {
if (x == s.size) {
if (*sum > sums) {
*sum = sums;
printf("sun %d\n", *sum);
for (int ko = 2;ko <= s.size;ko++) {
b[ko] = a[ko];
printf("ssssss\n");
}
}
}
else {
for (int ko = 2;ko <= s.size;ko++) {
if (s.map[s.mapr[ko]] == 0&&fl->Shortest[last][s.mapr[ko]]!=nocnect) {
x++;
printf("sss%d\n", x);
sums += fl->Shortest[last][s.mapr[ko]];
printf("sum%d\n", sums);
s.map[s.mapr[ko]] == 1;
a[x] = s.mapr[ko];
dfs(b, x, sum, s.mapr[ko], sums, a, s, fl);
a[x] = 0;
sums-= fl->Shortest[last][s.mapr[ko]];
s.map[s.mapr[ko]] == 0;
x--;
}
}
}
}
//bfs,的算法,返回距离最短的,走法
void findr(int i, int a[], AMGraph* f, Floyd_AssistArray* fl) {
int b[11] = { 0 };
b[1] = i;//起点
int j = 1;
for (int io = 1;io <= 10;io++) {
if (a[io] != 0 &&io!=i) {
j++;
b[j] = io;
}
}
for (int gh = 1;gh <= j;gh++) {
printf("%d\n", b[gh]);
}
BFS s;
for (int j = 1;j <= 10;j++) {
s.map[j] = 0;
s.mapr[j] = b[j];
}
s.map[i] = 1;//给起点标记
s.mapr[1] = i;
s.size = j;
int sum = nocnect;
int c[11] = { 0 };
c[1] = i;
dfs(b, 1, &sum, i, 0, c, s, fl);
//print();
}
//处理信息可以看到,bfs函数传的东西有点多
没办法,我来解释一下,b数组是返回答案的数组,sum是返回最短距离的最终答案
x是搜到了第几个数(第几个点),last是记录上个点,要的是两点之间的距离,所以要记录上个点
sums是记录距离和
a数组是记录点的
BFS 是提供dfs要的变量,比如标记的地图
和原来的点集以及有几个点
Floyd_AssistArray* fl 我们要的距离
typedef struct {
int map[11];//打标记的
int mapr[11];//记录点
int size;//记录个数
}BFS;
//dfs的辅助数组辅助数组的核心内容
接下来就是界面
为了可以,直接点击输入点把界面又搞了一下
黑色代表景点,被选中了,也可以取消选中
跑完bfs的数组就要开始回溯了路路径了
PathStack ph;
ph.top = 0;
for (int h = 1;h <= s.size;h++) {
printf("%d\n", b[h]);
}
for (int jk = s.size;jk >= 2;jk--) {
int k = 0;
while (fl->PrePath[b[jk]][b[jk-1]] != b[jk - 1]) {
Push(&ph, b[jk]);
printf(" %d\n", b[jk]);
k = 1;
b[jk] = fl->PrePath[b[jk]][b[jk - 1]];
}
if (k == 0) {
Push(&ph, b[jk]);
printf(" %d\n", b[jk]);
}回溯到栈内,明天写了输出函数就可以用栈直接遍历了
胜利就在眼前了呀!!现在811行
明天基本上得有1k了,但是还是写的很不好哎呀我是真的菜
以上代码(的bug全部测试完了,痛真的太痛了)
