南通优普网站建设企业网站建设如何选择网络公司

今天,解决了,多个点的最短路问题

用的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全部测试完了,痛真的太痛了)