您的位置:首页 > 教育 > 培训 > 郑州富士康招聘官网_免费素材库_搜索引擎营销优缺点_全渠道营销成功案例

郑州富士康招聘官网_免费素材库_搜索引擎营销优缺点_全渠道营销成功案例

2025/5/22 15:32:41 来源:https://blog.csdn.net/2305_78057683/article/details/143202220  浏览:    关键词:郑州富士康招聘官网_免费素材库_搜索引擎营销优缺点_全渠道营销成功案例
郑州富士康招聘官网_免费素材库_搜索引擎营销优缺点_全渠道营销成功案例

迪杰斯特拉算法无向图代码如下:

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>  
#include <stdlib.h>  
#define MaxInt 32767
#define MVNum 100
int* D, * S, * Path;
typedef struct
{char vexs[MVNum];int arcs[MVNum][MVNum];int vexnum, arcnum;
}AMGraph;
int Locate(AMGraph G, char u)
{int i;for (i = 0; i < G.vexnum; i++){if (G.vexs[i] == u){return i;}}return -1;
}
void CreateUDN(AMGraph* G)
{int i, j, k, w;printf("请输入顶点数+边数\n");scanf("%d %d", &G->vexnum, &G->arcnum);getchar();printf("请输入顶点的名称:\n");for (i = 0; i < G->vexnum; i++){printf("请输入第%d个点的名称:", i + 1);scanf(" %c", &G->vexs[i]);}//初始化这个邻接矩阵的二维数组都为极大值for (i = 0; i < G->vexnum; i++){for (j = 0; j < G->vexnum; j++){G->arcs[i][j] = MaxInt;}}printf("请输入边依附的顶点+权值\n");for (k = 0; k < G->arcnum; k++){char v1, v2;printf("请输入第%d条边依附的顶点+权值:", k + 1);scanf(" %c %c %d", &v1, &v2, &w);i = Locate(*G, v1);j = Locate(*G, v2);G->arcs[i][j] = w;G->arcs[j][i] = G->arcs[i][j];}
}
void ShortestPath_DIJ(AMGraph G, int v0)
{int v, i, w, min;int n = G.vexnum;//顶点总数D = (int*)malloc(sizeof(int) * n);//权值S = (int*)malloc(sizeof(int) * n);//课本中S数组是bool类型,我们可以用int类型,然后0为false 非0为true就好了Path = (int*)malloc(sizeof(int) * n);//前驱索引for (v = 0; v < n; v++){S[v] = 0;D[v] = G.arcs[v0][v];if (D[v] < MaxInt){Path[v] = v0;}else {Path[v] = -1;}}//v = 6S[v0] = 1;D[v0] = 0;for (i = 1; i < n; i++)//除去v0,循环n-1次{min = MaxInt;for (w = 0; w < n; w++){//第一个for循环,寻找出D[w]的极小值权值if (!S[w] && D[w] < min){v = w;min = D[w];}}S[v] = 1;for (w = 0; w < n; w++){//第二个for循环,是寻找当前v相邻的顶点//判断它相邻的顶点是v0直达划算,还是通过v中转划算if (!S[w] && (D[v]+G.arcs[v][w]) < D[w]){D[w] = D[v] + G.arcs[v][w];Path[w] = v;}}}
}
void DisplayPath(AMGraph G, int begin, int temp)//源点 终点
{if (Path[temp] != -1)//为-1就是v0或者是和v0没有关系的,没得打印{DisplayPaht(G, begin, Path[temp]);printf("%c --> ", G.vexs[Path[temp]]);}
}
int main()
{printf("************算法6.10 迪杰斯特拉算法**************\n\n");AMGraph G;int i, j, num_start, num_destination;char start, destination;CreateUDN(&G);printf("\n");printf("*****无向网G创建完成!*****\n");for (i = 0; i < G.vexnum; i++)//6{for (j = 0; j < G.vexnum; j++)//6{if (j!=G.vexnum-1)//5 !=5   0 1 2 3 4 打印前四列{if (G.arcs[i][j] != MaxInt){printf("%d\t", G.arcs[i][j]);}else{printf("∞\t");}}else//打印第五列后换行{if (G.arcs[i][j] != MaxInt){printf("%d\n", G.arcs[i][j]);}else {printf("∞\n");}}}}printf("\n");printf("请输入起点和终点(vi,vj)的名称:");scanf(" %c %c", &start, &destination);num_start = Locate(G, start);num_destination = Locate(G, destination);ShortestPath_DIJ(G, num_start);//从0出发寻找到 1 2 3 4 5 的最短路径,然后通过保存前驱索引在Path数组中printf("最短路径为: "); DisplayPath(G, num_start, num_destination);printf("%c", G.vexs[num_destination]);free(D);free(S);free(Path);return 0;
}

 迪杰斯特拉算法无向图:

 迪杰斯特拉算法无向图终端输入:

************算法6.10 迪杰斯特拉算法**************

请输入顶点数+边数
6 8
请输入顶点的名称:
请输入第1个点的名称:0
请输入第2个点的名称:1
请输入第3个点的名称:2
请输入第4个点的名称:3
请输入第5个点的名称:4
请输入第6个点的名称:5
请输入边依附的顶点+权值
请输入第1条边依附的顶点+权值:0 2 10
请输入第2条边依附的顶点+权值:0 4 30
请输入第3条边依附的顶点+权值:0 5 100
请输入第4条边依附的顶点+权值:1 2 5
请输入第5条边依附的顶点+权值:2 3 50
请输入第6条边依附的顶点+权值:3 5 10
请输入第7条边依附的顶点+权值:4 3 20
请输入第8条边依附的顶点+权值:4 5 60

*****无向网G创建完成!*****
∞       ∞       10      ∞       30      100
∞       ∞       5       ∞       ∞       ∞
10      5       ∞       50      ∞       ∞
∞       ∞       50      ∞       20      10
30      ∞       ∞       20      ∞       60
100     ∞       ∞       10      60      ∞

请输入起点和终点(vi,vj)的名称:0 5
最短路径为: 0 --> 4 --> 3 --> 5

 通过 迪杰斯特拉算法可以看出源点为0 终点为5 它们的最短路径就是0 - 4 - 3 -5,如果要知道0与1 2 3 4 的最短路径,读者们自行复制代码去运行,然后看图检验是否是正确,这里演示的0 5 是这个无向网最复杂的一个路径

迪杰斯特拉算法有向图代码:

	for (k = 0; k < G->arcnum; k++){char v1, v2;printf("请输入第%d条边依附的顶点+权值:", k + 1);scanf(" %c %c %d", &v1, &v2, &w);i = Locate(*G, v1);j = Locate(*G, v2);G->arcs[i][j] = w;//G->arcs[j][i] = G->arcs[i][j];}

只需要在CreateAMGraph函数中,注销G->arcs[j][i] = G->arcs[i][j];即可,因为有向图并不是对称的

迪杰斯特拉算法有向图:

 迪杰斯特拉算法有向图终端输入:

************算法6.10 迪杰斯特拉算法**************

请输入顶点数+边数
6 8
请输入顶点的名称:
请输入第1个点的名称:0
请输入第2个点的名称:1
请输入第3个点的名称:2
请输入第4个点的名称:3
请输入第5个点的名称:4
请输入第6个点的名称:5
请输入边依附的顶点+权值
请输入第1条边依附的顶点+权值:0 2 10
请输入第2条边依附的顶点+权值:0 4 30
请输入第3条边依附的顶点+权值:0 5 100
请输入第4条边依附的顶点+权值:1 2 5
请输入第5条边依附的顶点+权值:2 3 50
请输入第6条边依附的顶点+权值:3 5 10
请输入第7条边依附的顶点+权值:4 3 20
请输入第8条边依附的顶点+权值:4 5 60

*****有向网G创建完成!*****
∞       ∞       10      ∞       30      100
∞       ∞       5       ∞       ∞       ∞
∞       ∞       ∞       50      ∞       ∞
∞       ∞       ∞       ∞       ∞       10
∞       ∞       ∞       20      ∞       60
∞       ∞       ∞       ∞       ∞       ∞

请输入起点和终点(vi,vj)的名称:0 5
最短路径为: 0 --> 4 --> 3 --> 5

 

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com