floyd算法
题目来源：codeup链接
在本题中，读入一个有向图的带权邻接矩阵（即数组表示），建立有向图并按照以上描述中的算法求出每一对顶点间的最短路径长度。
输入
输入的第一行包含1个正整数n，表示图中共有n个顶点。其中n不超过50。
以后的n行中每行有n个用空格隔开的整数。对于第i行的第j个整数，如果大于0，则表示第i个顶点有指向第j个顶点的有向边，且权值为对应的整数值；如果这个整数为0，则表示没有i指向j的有向边。当i和j相等的时候，保证对应的整数为0。
输出
共有n行，每行有n个整数，表示源点至每一个顶点的最短路径长度。如果不存在从源点至相应顶点的路径，输出-1。对于某个顶点到其本身的最短路径长度，输出0。
请在每个整数后输出一个空格，并请注意行尾输出换行。
样例输入
4
0 3 0 1
0 0 4 0
2 0 0 0
0 0 1 0
样例输出
0 3 2 1
6 0 4 7
2 5 0 3
3 6 1 0
提示
在本题中，需要按照题目描述中的算法完成弗洛伊德算法，并在计算最短路径的过程中将每个顶点是否可达记录下来，直到求出每一对顶点的最短路径之后，算法才能够结束。
相对于迪杰斯特拉算法，弗洛伊德算法的形式更为简单。通过一个三重循环，弗洛伊德算法可以方便的求出每一对顶点间的最短距离。
另外需要注意的是，为了更方便的表示顶点间的不可达状态，可以使用一个十分大的值作为标记。而在题目描述中的算法示例使用了另外一个三维数组对其进行表示，这使原本的O(n3)时间复杂度增长到了O(n4)，这也是需要自行修改的部分。
#include <iOStream>
using namespace std;
const int maxn = 100;
const int INF = 0x3fffffff;
int dis[maxn][maxn];
int n, m; //顶点数，边数
void Floyd()
{
for (int k = 0; k < n; k++)
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (dis[i][k] != INF && dis[k][j] != INF && dis[i][k] + dis[k][j] < dis[i][j])
{
dis[i][j] = dis[i][k] + dis[k][j];
}
}
}
}
}
int main()
{
cin >> n;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
cin >> dis[i][j];
if(dis[i][j]==0)
{
dis[i][j] = INF;
}
}
dis[i][i] = 0;
}
Floyd();
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (i == j)
{
cout << 0 << ' ';
}
else
{
if (dis[i][j] != INF)
{
cout << dis[i][j] << ' ';
}
else
{
cout << -1 << ' ';
}
}
}
cout << endl;
}
return 0;
}
相关阅读
有些网页的内容不能够直接复制，很不方便。 chrome 有款插件 Enable Copy 非常简单地解决了此问题。单击插件地址直接安装即可。 安
C# 多线程 Parallel.ForEach 和 ForEach 效率问题研究
最近要做一个大数据dataTable循环操作，开始发现 运用foreach，进行大数据循环，并做了一些逻辑处理。在循环中耗费的时间过长。后来换
Access denied for user 'root'@'localhost'问题
问题场景在阿里云上部署了一台服务器，CentOS6.8系统环境，安装了MySql+Nginx+Git+vsftpd等软件，在本地Linux终端以非root账户SSH远程
轮询调度算法(Round-Robin Scheduling)
http://blog.163.com/s_u/blog/static/1330836720105233102894/ 毫无疑问，随着互联网、移动网络接入成本的降低，互联网正在日益深入
论文：CornerNet: Detecting Objects as Paired Keypoints论文链接：https://arxiv.org/abs/1808.01244代码链接：https://github.com/u