C语言编写最短路径算法（含迪杰斯特拉、弗洛伊德）

共2个文件

cpp：2个

版权申诉

5星 · 超过95%的资源 43 浏览量 2022-04-26 17:34:25 上传评论 3 收藏 2KB ZIP 举报

在计算机科学领域，寻找图中两点间的最短路径是一个核心问题，这在各种网络路由、交通规划、资源分配等场景中都有广泛应用。本压缩包文件包含两种著名的最短路径算法的C语言实现：迪杰斯特拉算法（Dijkstra's Algorithm）和弗洛伊德算法（Floyd-Warshall Algorithm）。这两种算法各有特点，适用于不同的问题场景。 1. 迪杰斯特拉算法：迪杰斯特拉算法是由荷兰计算机科学家艾兹格·迪杰斯特拉在1956年提出的，它用于寻找单源最短路径。该算法基于贪心策略，每次选取当前已知最短路径到达的顶点，并更新其相邻未访问节点的距离。其基本步骤如下： - 初始化：将起点的距离设为0，其他所有点的距离设为无穷大。 - 按照距离从小到大的顺序选择未访问的顶点。 - 更新与选中顶点相邻的未访问顶点的距离，如果通过当前顶点到达这些顶点的路径更短，则进行更新。 - 标记选中的顶点为已访问。 - 重复以上步骤，直到所有顶点都被访问。 2. 弗洛伊德算法：弗洛伊德算法由美国数学家罗伯特·弗洛伊德在1962年提出，用于求解所有对之间的最短路径。与迪杰斯特拉算法不同，弗洛伊德算法可以处理负权边的最短路径问题，但它不适用于有负权环的情况。算法步骤如下： - 初始化：创建一个n×n的矩阵，表示所有顶点之间的初始距离。对于每对顶点(u, v)，如果存在直接连接的边，则矩阵元素dist[u][v]为边的权重；否则，如果u和v不直接相连，dist[u][v]为无穷大。 - 对于所有的中间节点k（1 <= k <= n），检查每一对顶点(u, v)，如果路径(u, k, v)的总长度小于路径(u, v)的长度，则更新dist[u][v]。 - 遍历所有中间节点后，矩阵dist中存储的就是所有顶点对之间的最短路径。 C语言是一种强大的编程语言，特别适合实现这些基础算法，因为它语法简洁，效率较高。在这个压缩包中，"迪杰斯特拉最短路径.cpp"和"弗洛伊德最短路径.cpp"是两个C语言源文件，分别实现了这两种算法。通过阅读和学习这些代码，你可以更好地理解这两个算法的工作原理，同时提升你的C语言编程能力。在实际应用中，根据问题的具体需求，可以选择合适的算法。例如，如果图中没有负权边且需要寻找从单一源点到所有其他点的最短路径，迪杰斯特拉算法是个好选择；而如果需要解决所有对之间最短路径的问题，或者图中可能存在负权边，那么弗洛伊德算法更为合适。通过深入学习这两种算法，不仅可以提高编程技能，还可以增强在实际问题中应用算法的能力。

资源详情

资源评论

资源推荐

收起资源包目录

最短路径算法.zip （2个子文件）

弗洛伊德最短路径.cpp 2KB

迪杰斯特拉最短路径.cpp 2KB

#include<stdio.h> #include<stdlib.h> #define MaxVexNum 50 #define MaxInt 32767 #define MaxEdgeNum 50 //邻接矩阵 typedef int VertexType; typedef int EdgeType; typedef struct AMGraph{ VertexType vexs[MaxVexNum];//顶点表 EdgeType arcs[MaxVexNum][MaxVexNum];//邻接矩阵表 int vexnum,edgenum;//顶点数，边数 }AMGraph; void createGraph(AMGraph &g){//创建无向图 printf("请输入顶点数："); scanf("%d",&g.vexnum); printf("\n请输入边数："); scanf("%d",&g.edgenum); //初始化顶点表 for(int i=0;i<g.vexnum;i++){ g.vexs[i]=i; } for(int i=0;i<g.vexnum;i++){ for(int j=0;j<g.vexnum;j++){ g.arcs[i][j]=MaxInt; if(i==j) g.arcs[i][j]=0; } } printf("请输入边的信息以及边的权值(顶点是0~n-1)\n"); for(int i=0;i<g.edgenum;i++){ int x,y,w; scanf("%d%d%d",&x,&y,&w); g.arcs[x][y]=w; //g.arcs[y][x]=w; } } void PrintGraph(AMGraph g){ printf("邻接矩阵为:\n"); for(int i=0;i<g.vexnum;i++) { printf(" %d",g.vexs[i]); } printf("\n"); for(int i=0;i<g.vexnum;i++){ printf("%d ",g.vexs[i]); for(int j=0;j<g.vexnum;j++){ if(g.arcs[i][j]==32767){ printf("∞ "); }else{ printf("%d ",g.arcs[i][j]); } } printf("\n"); } } //Floyd算法 //递归输出两个顶点直接最短路径 void printPath(int u,int v,int path[][MaxVexNum]){ if(path[u][v]==-1){ printf("[%d %d] ",u,v); }else{ int mid=path[u][v]; printPath(u,mid,path); printPath(mid,v,path); } } void Floyd(AMGraph g,int path[][MaxVexNum]){ int n=g.vexnum; int A[n][n]; //第一步：初始化path[][]和A[][]数组 for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ A[i][j]=g.arcs[i][j]; path[i][j]=-1; } } //第二步：三重循环，寻找最短路径 for(int v=0;v<n;v++){//第一层是代表中间结点 for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ if(A[i][j]>A[i][v]+A[v][j]){ A[i][j]=A[i][v]+A[v][j]; path[i][j]=v; } } } } } int main(){ AMGraph g; createGraph(g); PrintGraph(g); int path[MaxVexNum][MaxVexNum]; Floyd(g,path); printPath(1,0,path); }