|
在vs环境下进行的操作 用两种方法分别模拟实现公园导航 1.Dijkstra算法 按路径长度递增次序来产生最短路径算法； dist【】距离， path【】前结点 ①初始化 ②找最小距离 ③修正a到c，a到b再到c的距离 2。Floyd算法 邻接矩阵迭代 Dijkstra算法可实现单源点到其他所有点的的最短路径，也可用于所有点到所有点，较为灵活，但相对较复杂（一开始模拟时以为是所有点到所有点） Floyd算法主要是所有点到所有点，但较好理解 在用Dijkstra算法时，一开始函数定义为Dijkstra(MGraph * g, int v）参数g为地图，v为单元点，但函数内部的数组s[]运行后报错Run-Time Check Failure #2 - Stack around the variable 's' was corrupted.推测为下标越界或溢出，但逻辑本身应该是没问题的，我也不知为何。 但将数组置为全局则不报错；推测变量在栈区（最多只可以开2M）？，而之后放到全局区可以开的空间大很多，就不会溢出？ 报错参考https://blog.csdn.net/chenyujing1234/article/details/8261914 两种方法求管道修建最低成本 1.prim算法（时间复杂度O（n^2））n,为顶点数 将图分为两个顶点集，一个为已选顶点，一个为未选顶点，每次从 未选顶点集合里面 抽出 到 已选顶点集合里面 的 最小权；直到所有被选。 2.kruskal算法（算法实现略过） 边的算法，将边归并，适合稀疏网 #include <iostream> #include <windows.h> #define MAX 50 #define INF 32767 //顶点类型 typedef struct { int num;//景点编号 char info[MAX];//景点名称 char introduction[MAX];//景点简介 }vertexType; //图的定义 typedef struct { int deges[MAX][MAX];//邻接矩阵 int n, e;//顶点数，弧数 vertexType vexs[MAX];//存放顶点信息 }MGraph; void menu1();//菜单 MGraph *create(MGraph *g, int(*a)[MAX]);//建图 void disp(MGraph* g);//输出图 void Dijkstra(MGraph *g, int v,int s[]);//Dijkstra算法 void ppath(MGraph *g, int path[], int i, int v);//计算最短路径长度 void DisPath(MGraph *g, int dist[], int path[], int s[], int n, int v);//输出从V出发的所有最短路径 void Floyd(MGraph *g);//Floyd算法 void Dispath(MGraph *g, int A[][MAX], int path[][MAX]);//输出所有最短路径 void Prim(MGraph *g, int v);//普里姆算法求管道修建最低成本 int s[MAX]; int main() { int c; int change = 1; MGraph *g = NULL; int A[MAX][MAX] = { {0,45,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,400,INF,INF,INF,210,150}, {45,0,70,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF}, {INF,70,0,40,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF}, {INF,INF,40,0,50,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF}, {INF,INF,INF,50,0,40,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF}, {INF,INF,INF,INF,40,0,350,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF}, {INF,INF,INF,INF,INF,350,0,30,INF,INF,36,INF,INF,INF,INF,INF,INF,INF,INF}, {INF,INF,INF,INF,INF,INF,30,0,38,34,INF,INF,INF,INF,INF,INF,INF,INF,INF}, {INF,INF,INF,INF,INF,INF,INF,38,0,INF,INF,INF,INF,INF,22,INF,INF,INF,INF}, {INF,INF,INF,INF,INF,INF,INF,34,INF,0,15,INF,INF,INF,INF,INF,INF,INF,INF}, {INF,INF,INF,INF,INF,INF,36,INF,INF,15,0,INF,INF,15,INF,INF,18,INF,INF}, {400,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,0,34,INF,INF,INF,INF,INF,INF}, {INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,34,0,35,24,36,INF,INF,INF}, {INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,15,INF,35,0,INF,INF,INF,INF,INF}, {INF,INF,INF,INF,INF,INF,INF,INF,22,INF,INF,INF,24,INF,0,INF,INF,INF,INF}, {INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,36,INF,INF,0,INF,INF,40}, {INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,18,INF,INF,INF,INF,INF,0,95,INF}, {210,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,95,0,45}, {150,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,40,INF,45,0} }; menu1(); g = create(g, A); while (change) { int u = 0; printf(" 请选择(1-5)："); scanf_s("%d", &c); switch (c) { case 1: disp(g); break; case 2:printf("\n求单源景点的最短路径:\n\n"); printf("\n 请输入出发点:"); scanf_s("%d", &u); Dijkstra(g, u, s); printf("\n"); break; case 3:printf("\n求任意两景点之间的最短路径:\n\n"); Floyd(g); printf("\n"); break; case 4:change = 0; printf("已退出！"); break; } } printf("\n"); return 0; } //邻接矩阵创建图 MGraph * create(MGraph * g, int(*a)[MAX]) { int i = 0; g = (MGraph*)malloc(sizeof(MGraph)); g->n = 19; g->e = 24; FILE *fp1; fopen_s(&fp1,"F:\\v4.txt","r+"); while (!feof(fp1)) { g->vexs[i].num = i; fscanf_s(fp1,"%s %s",g->vexs[i].info, _countof(g->vexs[i].info),g->vexs[i].introduction, _countof(g->vexs[i].introduction)); i++; } for (int j = 0; j < g->n; j++) { for (int k = 0; k < g->n; k++) { g->deges[j][k] = *(a[j] + k); } } return g; } //输出图 void disp(MGraph * g) { int i, j, k = 0; printf(" 公园的景点：\n"); for (i = 0; i < g->n; i++) printf("%d:%s\n", i, g->vexs[i].info); printf("\n输出公园地图的信息(邻接矩阵表示)：\n"); printf(" 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18\n"); for (i = 0; i < g->n; i++) { printf(" %-3d|", i); //输出格式 for (j = 0; j < g->n; j++) { k++; if (g->deges[i][j] == INF) //两顶点之间无边的处理 printf("∞ "); else printf("%-3d ", g->deges[i][j]); //两顶点之间有边的处理 if (k % 19 == 0) { printf(" |\n"); } //输出格式 } } } //狄杰斯特拉算法从顶点v到其余各顶点的最短路径 void Dijkstra(MGraph * g, int v, int s[]) { int dist[MAX], path[MAX];//路径每个点存放之前的一个点,dist存放2个点之间的距离; int mindis;//最小距离 int i, j, k, u, n = g->n; for (i = 0; i < n; i++) { dist[i] = g->deges[v][i]; s[i] = 0; if (g->deges[v][i] < INF) { path[i] = v; } else { path[i] = -1; } } s[v] = 1; path[v] = 0; for (i = 0; i < n; i++) { mindis = INF; u = -1; for (j = 0; j < n; j++) { if (s[j] == 0 && dist[j] < mindis) { mindis = dist[j]; u = j; } } s[u] = 1; for (k = 0; k < n; k++) { if (s[k] == 0) { if (g->deges[u][k] < INF && dist[u] + g->deges[u][k] < dist[k]) { dist[k] = dist[u] + g->deges[u][k]; path[k] = u; } } } } printf(" \n 输出最短路径:\n"); DisPath(g, dist, path, s, n, v); //输出最短路径 } //v到i的最短路径,输出中间路径 void ppath(MGraph * g, int path[], int i, int v) { int k; k = path[i]; if (k == v) { return; } ppath(g, path, k, v); printf("%s ——>", g->vexs[k].info); } //由path计算v到所有点最短路径 void DisPath(MGraph * g, int dist[], int path[], int s[], int n, int v) { int i; printf(" --------------------------------------------------------------\n"); for (i = 0; i < n; i++) { if (s[i] == 1) { if (i != v) { Sleep(150); printf("从%s到%s的最短路径长度为:%d \t路径为:", g->vexs[v].info, g->vexs[i].info, dist[i]); printf("%s ——>", g->vexs[v].info); ppath(g, path, i, v); printf("%s \n", g->vexs[i].info); } } else { printf(" 从%d到%d不存在路径\n", v, i); } } printf("\n--------------------------------------------------------------\n\n"); } //Floyd算法 void Floyd(MGraph * g) { int i, j, k; int a[MAX][MAX]; int path[MAX][MAX]; //初始化a&path； for (i = 0; i < g->n; i++) { for (j = 0; j < g->n; j++) { a[i][j] = g->deges[i][j]; if (g->deges[i][j] < INF && i != j) { path[i][j] = i; } else { path[i][j] = -1; } } } for (k = 0; k < g->n; k++) { for (i = 0; i < g->n; i++) { for (j = 0; j < g->n; j++) { if (a[i][k] + a[k][j] < a[i][j]) { a[i][j] = a[i][k] + a[k][j]; path[i][j] = path[k][j]; } } } } Dispath(g, a, path); } //重载由path计算v到所有点最短路径 void Dispath(MGraph * g, int A[][MAX], int path[][MAX]) { int i, j, k, s; int apath[MAX],d; for (i = 0; i < g->n; i++) { for (j = 0; i < g->n; j++) { if (A[i][j] != INF && i != j) { printf(" 从%d到%d的路径为:", i, j); k = path[i][j]; d = 0; apath[d] = j;//添加起点 while (k != -1 && k != i) { d++; apath[d] = k; k = path[i][k]; } d++; apath[d] = i;//添加终点 printf("%d", apath[d]);//输出起点 for (s = d - 1; s >= 0; s--)//输出路径上的中间顶点 printf(",%d", apath[s]); printf("\t\t路径长度为:%d\n", A[i][j]); } } } } //菜单 void menu1() { printf("\n"); printf(" ******公园导游程序设计******\n"); printf(" ============================================\n"); printf(" 1.公园景点介绍\n"); printf(" 2.求单源景点的最短路径\n"); printf(" 3.求任意两景点之间的最短路径\n"); printf(" 4.退出 :\n"); printf(" =============================================\n"); } //普里姆算法求管道修建最低成本 void Prim(MGraph * g, int v) { int min, sum = 0; int lowcost[MAX];//低成本 int closest[MAX];//临近点 int u, i, j, k, n = g->n; for (i = 0; i < n; i++) { lowcost[i] = g->edges[v][i]; closest[i] = v; } for (i = 1; i < n; i++) { min = INF; for (j = 0; j < n; j++) { if (lowcost[j] != 0 && lowcost[j] < min) { min = lowcost[j]; u = j; } } printf(" 线路:%s->%s", g->vexs[closest[u]].info,g->vexs[u].info); Sleep(200); printf(" \t\t距离:%-dm .\n", min); Sleep(30); sum = sum + min; lowcost[u] = 0; for ( k = 0; k < n; k++) { if (g->edges[u][k] != 0 && g->edges[u][k] < lowcost[k]) { lowcost[k] = g->edges[u][k]; closest[k] = u; } } } printf("\n 线路总距离为：%dm!", sum); } |