就是求所有顶点对的最短路径长度
#include <iostream>
#include <vector>
using namespace std;
typedef struct{
int vexs[10];
int edges[10][10];
int n;
int e;
}MGraph;
#define INFINITE 2048
void CreateGraphM(MGraph *G){
int N1,N2;
cout<<"Enter the number of vertexs and edges: "<<endl;
cin>>(G->n)>>(G->e);
for(int i=0;i<G->n;i++)
cin>>(G->vexs[i]);
for(int i=0;i<G->n;i++)
for(int j=0;j<G->n;j++)
G->edges[i][j]=-1;
cout<<"EDGES: "<<endl;
for(int k=0;k<G->e;k++){
int weight;
cin>>N1>>N2>>weight;
G->edges[N1-1][N2-1]=weight;
}
return;
}
vector< vector<int> > Floyed_Warshall(MGraph *G){
vector< vector<int> > Dist(G->n,vector<int>(G->n));
for(int i=0;i<G->n;i++)
for(int j=0;j<G->n;j++)
Dist[i][j] = G->edges[i][j];
for(int i=0;i<G->n;i++)
Dist[i][i] = 0;
for(int i=0;i<G->n;i++)
for(int j=0;i<G->n;i++)
for(int k=0;i<G->n;i++)
if(Dist[j][i] + Dist[i][k] < Dist[j][k] && \
Dist[j][i] != -1 && \
Dist[i][k] != -1)
Dist[j][k] = Dist[j][i] + Dist[i][k];
return Dist;
}
int main()
{
vector< vector<int> > Dist;
MGraph *G = new MGraph;
CreateGraphM(G);
Dist = Floyed_Warshall(G);
cout<<endl;
for(int i=0;i<G->n;i++)
for(int j=0;j<G->n;j++)
if(Dist[i][j]!=-1 && i!=j)
cout<<i+1<<" "<<j+1<<" "<<Dist[i][j]<<endl;
cout<<endl;
delete G;
return 0;
}
分享到:
相关推荐
使用c++编写的floyd-warshall算法,还有《算法导论》上的另外一种动态规划解法。
最短路径(Floyd-Warshall)
Floyd-Warshall算法是解决任意两点间的最短路径的一种算法。通常可以在任何图中使用,包括有向图、带负权边的图。
2.领域:Floyd-Warshall算法 3.仿真效果:仿真效果可以参考博客同名文章《基于Floyd-Warshall算法的ISOMAP最短路径方法matlab仿真》 4.内容:基于Floyd-Warshall算法的ISOMAP最短路径方法matlab仿真。Floyd-...
Floyd-Warshall算法的C语言实现
Floyd-Warshall 算法【算法概述】假如我们要找任意有向图或无向图中两个点之间的最短距离,使用Dijstra算法或者Bellman Fold算法时间复
2021-1-14学习报告-王宇哲(最少转机与floyd-warshall)1
Floyd-Warshall算法DP流程详解.docx
代码实现了Floyd-Warshall算法,它接受一个带权重的有向图作为输入,计算出任意两个节点之间的最短路径。 在示例代码中,使用graph二维数组表示图的邻接矩阵,Integer.MAX_VALUE表示两个节点之间不存在直接连接。...
基于C++实现的每对结点之间的最短路径(Floyd-Warshall算法)
解决图论中Warshall-Floyd 算法,Kruskal 避圈法,匈牙利算法,求最佳匹配的算法,求最大流的Ford--Fulkerson 标号算法,求解最小费用流问题的matlab程序
Floyd-Warshall 算法计算给定邻接矩阵的所有对最短路径矩阵。 该算法是 O(n^3),在大多数实现中,您会看到 3 个嵌套的 for 循环。 这在 Matlab 中效率很低,所以在这个版本中,两个内部循环被向量化(因此,它运行得...
做ACM最短路问题普遍算法的Floyd-Dijkstra-Spfa板子..
Floyd-Warshall算法---创建此项目是为了完成CPCS-324最终项目的第一阶段--- 编程语言:JAVA 该程序使用Floyd-Warshall算法在连接的加权图中查找所有对的最短路径即从任何一个顶点到所有其他顶点的最短路径使用的图形...
-- 输入权重(或初始距离)矩阵必须具有节点未连接的 Inf 值和对角线上的 0。 -- 输出是短路径的距离矩阵 D 和前任矩阵 P 使得 P(i,j) 是从 i 到 j 的最短路径上 j 之前的节点,因此如果要构建路径,则必须读取 P向...
floyd-warshall-cython Floyd-Warshall 算法的有效 Cython 实现,用于在加权有向图中查找所有顶点对之间的最短路径距离。 见接触随时提出任何问题: 阿米特·莫斯科维奇·艾格峰。
#Floyd-Warshall 与 MPI 并行 Floyd-Warshall 算法通过 Fox 算法使用MPI 的并行实现(在C 中)。 要编译,只需在文件夹中运行make命令。 在运行之前,您需要使用集群配置定义一个文件。 要运行程序,您需要在矩阵...
php-floydwarshall Floyd-Warshall算法PHP实现 如维基百科所述:“在计算机科学中,FloydWarshall算法是一种用于在加权有向图中找到最短路径的图分析算法。该算法的一次执行将在所有顶点对之间找到最短路径。”
Y2VisualGraph 在加权图中寻找最短路径的 Floyd-Warshall 算法演示