百度网站建设产品,专业网站设计开发网站,爱站网站,wordpress 开店今天,解决了,多个点的最短路问题
用的dfs,配上了floyed计算出的广源距离
难点是要记录路线,dfs记录路线就很烦
但是好在结束了,经过无数的测试,确保没啥问题(应该把)
来看看我的代码 void dfs(int b[], int x, int* sum, int last, int sums, int a[], BFS s, Floyd_A…今天,解决了,多个点的最短路问题
用的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]] 0fl-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全部测试完了,痛真的太痛了)
