项目结束倒数2
今天,解决了,多个点的最短路问题
用的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全部测试完了,痛真的太痛了)