大佬教程收集整理的这篇文章主要介绍了[C++] 多源最短路径(带权有向图):【Floyd算法(动态规划法)】 VS nX Dijkstra算法(贪心算法),大佬教程大佬觉得挺不错的,现在分享给大家,也给大家做个参考。
/** * 弗洛伊德(Floyd)算法: 1 解决问题: 多源最短路径问题 求每一对顶点之间的最短路径 BACkground: 带权有向图 2 算法思想: 动态规划(DP,Dynamic ProgrAMMing) 3 时间复杂度: O(n^3) */ #include<stdio.h> #include<iostream> using namespace std; // 1 定义图模型(邻接矩阵表示法)的基本存储结构体 # define MaxInt 32767 // 表示极大值 即 ∞ (无穷大) # define MVNum 100 // 最大顶点数 typedef int VertexType; // 假设顶点的数据类型为整型 typedef int arcType; // 假设Vi与Vj之边的权值类型为整型 typedef struct { VertexType vexs[MVNum]; // 顶点表 (存储顶点信息) ArcType arcs[MVNum][MVNum]; // 邻接矩阵 int vexnum,arcnum; // 图的当前顶点数与边数 }AMGraph; // Adjacent Matrix Graph 邻接矩阵 // 2 定义Floyd算法的辅助数据结构体 ArcType D[MVNum][MVNum]; // 记录顶点Vi和Vj之间的最短路径长度 int Path[MVNum][MVNum]; // 最短路径上顶点Vj的前一顶点的序号 /////////////////////// ↓算法区↓ /////////////////////// void ShortestPath_Floyd(AMGraph G){ //step1 初始化各对结点的已知路径和距离 for(int i=0;i<G.vexnum;i++){ for(int j=0;j<G.vexnum;j++){ D[i][j] = G.arcs[i][j]; //D[i][j] 初始化 if(D[i][j]<MaxInt && i!=j){ // 【易漏】 i != j (防止产生自回环) Path[i][j] = i; // 若 Vi与Vj之间存在弧(有序顶点对): 将Vj的前驱置为 Vi } else { Path[i][j] = -1; } } } //step2 动态规划(Dp)动态更新: <Vi,Vj>更短的最短路径的距离和路径 for(int k=0;k<G.vexnum;k++){ // 【易错】 中间结点Vk的循环 是在最外层 for(int i=0;i<G.vexnum;i++){ for(int j=0;j<G.vexnum;j++){ if(D[i][k] + D[k][j] < D[i][j]){ // 若从Vi【经Vk】到Vj的一条路径更短 D[i][j] = D[i][k] + D[k][j]; // 更新D[i][j] Path[i][j] = Path[k][j]; // 【易错】 更改Vj的前驱为 Vk } } } } } // 初始化(邻接矩阵)带权有向图的图模型 void InitAMGraph(AMGraph &G){ cout<<"Please Input Vertexs number:"; cin>>G.vexnum; cout<<"\nPlease Directed Edge number:"; cin>>G.arcnum; for(int i=0;i<MVNum;i++){ for(int j=0;j<MVNum;j++){ if(i!=j){ // 【易错】 初始化<Vi,Vj>时: <Vi,Vj> 路径长度无穷大 (i!=j) G.arcs[i][j] = MaxInt; } else { // 【易错】 初始化<Vi,Vi>【自回环】路径长度为0 (i==i) G.arcs[i][j] = 0; } } } for(int i=0;i<G.vexnum;i++){ G.vexs[i] = i; } cout<<"\nPlease Input All Directed Edges and their Weight Now."; int i,j; int weight; for(int k=0;k<G.arcnum;k++){ cout<<"\n("<<(k+1)<<") Directed Edges(i,j,weight): "; cin>>i; cin>>j; cin>>weight; G.arcs[i][j] = weight; } cout<<endl; } void OutputD(AMGraph G){ for(int i=0;i<G.vexnum;i++){ for(int j=0;j<G.vexnum;j++){ cout<<"Shortest Distance Weight of the Pair of Directed Vertices ("<<i<<","<<j<<"): "<<D[i][j]<<endl; } } } void OutputPath(AMGraph G){ for(int i=0;i<G.vexnum;i++){ for(int j=0;j<G.vexnum;j++){ cout<<"Path("<<i<<","<<j<<"): "<<Path[i][j]<<endl; } } // int fullPath[G.vexnum]; //逆序记录 <Vi,Vj>的最短路径的序号 ; 最大路径长度不会超过 G.vexnum // for(int i=0;i<G.vexnum;i++){ // for(int j=0;j<G.vexnum;j++){ // cout<<"Shortest Distance Path of the Pair of Directed Vertices ("<<i<<","<<j<<"): "; // for(int p=0;i<G.vexnum;p++){ // 初始化记录最短路径的临时表 // fullPath[p]= -1; // -1 表示结束符 // } // int m=i,n=j; // int cusor=G.vexnum-1; // while( (cusor>=0) && (Path[m][n]!=i || Path[m][n]!=Maxint) ){ // fullPath[cusor] = Path[m][n]; // Vj的前驱 // n = fullPath[cusor]; // 【重难点】 源点m不变, 终点n更新为j的前驱 // cusor--; // 要保证 cusor>=0 // } // //输出全路径 // cout<<" "<<i<<">"; // cusor++; // 当前cusor的位置是源点i的前一个空置空间,值为-1 // while(fullPath[cusor] != -1){ // cout<<fullPath[cusor]<<">" // } // } // } } int main(){ AMGraph G; InitAMGraph(G);//易错处 ShortestPath_Floyd(G); // 【重/难点】易错处 OutputD(G); OutputPath(G); return 0; } */
Please Input Vertexs number:4 Please Directed Edge number:8 Please Input All Directed Edges and their Weight Now. (1) Directed Edges(i,weight): 0 1 1 (2) Directed Edges(i,weight): 1 3 2 (3) Directed Edges(i,weight): 2 0 3 (4) Directed Edges(i,weight): 0 3 4 (5) Directed Edges(i,weight): 2 1 5 (6) Directed Edges(i,weight): 3 2 6 (7) Directed Edges(i,weight): 2 3 8 (8) Directed Edges(i,weight): 1 2 9 Shortest Distance Weight of the Pair of Directed Vertices (0,0): 0 Shortest Distance Weight of the Pair of Directed Vertices (0,1): 1 Shortest Distance Weight of the Pair of Directed Vertices (0,2): 9 Shortest Distance Weight of the Pair of Directed Vertices (0,3): 3 Shortest Distance Weight of the Pair of Directed Vertices (1,0): 11 Shortest Distance Weight of the Pair of Directed Vertices (1,1): 0 Shortest Distance Weight of the Pair of Directed Vertices (1,2): 8 Shortest Distance Weight of the Pair of Directed Vertices (1,3): 2 Shortest Distance Weight of the Pair of Directed Vertices (2,0): 3 Shortest Distance Weight of the Pair of Directed Vertices (2,1): 4 Shortest Distance Weight of the Pair of Directed Vertices (2,2): 0 Shortest Distance Weight of the Pair of Directed Vertices (2,3): 6 Shortest Distance Weight of the Pair of Directed Vertices (3,0): 9 Shortest Distance Weight of the Pair of Directed Vertices (3,1): 10 Shortest Distance Weight of the Pair of Directed Vertices (3,2): 6 Shortest Distance Weight of the Pair of Directed Vertices (3,3): 0 Path(0,0): -1 Path(0,1): 0 Path(0,2): 3 Path(0,3): 1 Path(1,0): 2 Path(1,1): -1 Path(1,2): 3 Path(1,3): 1 Path(2,0): 2 Path(2,1): 0 Path(2,2): -1 Path(2,3): 1 Path(3,0): 2 Path(3,1): 0 Path(3,2): 3 Path(3,3): -1
以上是大佬教程为你收集整理的[C++] 多源最短路径(带权有向图):【Floyd算法(动态规划法)】 VS nX Dijkstra算法(贪心算法)全部内容,希望文章能够帮你解决[C++] 多源最短路径(带权有向图):【Floyd算法(动态规划法)】 VS nX Dijkstra算法(贪心算法)所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错,欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。