多源最短路径Floyd算法邻接矩阵形式C++实现,输入点数、边数和起点、终点、权值,输出最短路径及权值
#include <iostream> #define MAX_VEX 305 #define MAX_WEI 1000005 using namespace std; int A[MAX_VEX][MAX_VEX],Path[MAX_VEX][MAX_VEX]; //输出最短路径 void prn_pass(int j , int k){ if (Path[j][k]!=-1) { prn_pass(j,Path[j][k]); cout<<"-->"<<Path[j][k]; prn_pass(Path[j][k],k); } } int main(){ int N,M,i,j,k; int s,e,w; cin>>N>>M; for (i = 0;i < N;i++) for (j = 0;j < N;j++) { if (i == j) A[i][j] = 0; else A[i][j] = MAX_WEI; Path[i][j] = -1; } for (i = 0; i < M;i++) { cin>>s>>e>>w; A[s][e] = w; } //关键代码部分 for (k = 0;k < N;k++) for (i = 0;i < N;i++) for (j = 0;j < N;j++){ if (A[i][k] + A[k][j] < A[i][j]) { A[i][j] = A[i][k] + A[k][j]; Path[i][j] = k; } } //输出最短路径和权值 for (i = 0;i < N;i++) for (j = 0;j < N;j++){ if (i!=j) { cout<<i<<"到"<<j<<"的最短路径为:"; cout<<i; prn_pass(i,j); cout<<"-->"<<j<<endl; cout<<"最短路径长度为:"<<A[i][j]<<endl; } } return 0; }
您还没有登录,请您登录后再发表评论
Floyd算法直接使用二维数组求出所有顶点到所有顶点的最短路径。 D代表顶点到顶点的最短路径权值和的矩阵。 P代表对应顶点的最小路径的前驱矩阵。 以下程序在DEV C++中调试运行通过。 #include <stdio> #define ...
(1)运用图的存储方式采用邻接矩阵,将有向图的顶点,权值,最短路径等联系起来。 (2)调用Floyd算法 该算法主要是实现输出所有顶点之间最短路径长度的矩阵。通过不停地比较矩阵中每列最短路径长度的最大值,从而...
在文本中输入邻接矩阵的元素数量和邻接矩阵,输出联通矩阵和加权的值
给定一个邻接矩阵文本,利用Floyd算法求出两点之间的最短路径
图算法:图算法用于处理图结构的数据,如最短路径算法(如Dijkstra算法、Floyd-Warshall算法)、最小生成树算法(如Prim算法、Kruskal算法)等。 动态规划:动态规划是一种通过将问题分解成更小的子问题来解决复杂...
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
(6)求最短路径 弗洛伊德算法(shortpath_Floyd) 迪杰斯特拉算法(shortpath_DIJ) 9. 存储管理 (1)边界标识法 (Boundary_tag_method) (2)伙伴系统 (Buddy_system) (3)紧缩无用单元 (Storage_...
类型:邻接表式、邻接矩阵式;包含算法:dijkstra、floyd、SPFA、kruskal、prim、tarjan强连通分量、遍历、求哈密顿环、匈牙利算法求二分图最大匹配、连通性判断) 另外给喜爱算法的人推荐一本书:刘汝佳的《算法...
相关推荐
Floyd算法直接使用二维数组求出所有顶点到所有顶点的最短路径。 D代表顶点到顶点的最短路径权值和的矩阵。 P代表对应顶点的最小路径的前驱矩阵。 以下程序在DEV C++中调试运行通过。 #include <stdio> #define ...
(1)运用图的存储方式采用邻接矩阵,将有向图的顶点,权值,最短路径等联系起来。 (2)调用Floyd算法 该算法主要是实现输出所有顶点之间最短路径长度的矩阵。通过不停地比较矩阵中每列最短路径长度的最大值,从而...
在文本中输入邻接矩阵的元素数量和邻接矩阵,输出联通矩阵和加权的值
给定一个邻接矩阵文本,利用Floyd算法求出两点之间的最短路径
图算法:图算法用于处理图结构的数据,如最短路径算法(如Dijkstra算法、Floyd-Warshall算法)、最小生成树算法(如Prim算法、Kruskal算法)等。 动态规划:动态规划是一种通过将问题分解成更小的子问题来解决复杂...
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
(6)求最短路径 弗洛伊德算法(shortpath_Floyd) 迪杰斯特拉算法(shortpath_DIJ) 9. 存储管理 (1)边界标识法 (Boundary_tag_method) (2)伙伴系统 (Buddy_system) (3)紧缩无用单元 (Storage_...
类型:邻接表式、邻接矩阵式;包含算法:dijkstra、floyd、SPFA、kruskal、prim、tarjan强连通分量、遍历、求哈密顿环、匈牙利算法求二分图最大匹配、连通性判断) 另外给喜爱算法的人推荐一本书:刘汝佳的《算法...