floyd算法简单化表示过程

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了floyd算法简单化表示过程，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1571字，纯文字阅读大概需要3分钟。

内容图文

无论是在有向图还是无向图中，寻找两个点的最短路径，会用到floyd算法。通俗一点，floyd算法关键是找中间者来传递，例如matric[0][2]>matric[0][1]+matric[1][2]，算0到2的最短路径就经过了1，1就是中间者。如果有N个数，则会更新N次。

此时，点a 为0，点b为1，点c为2。

 

#include "stdafx.h"
#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#define Max 100
#define inf 0x3f3f3f3f     //int类型的无穷大表示
using namespace std;
class Solution
{
private:
	int vexnum;    //顶点数
	int edgenum;   //边数
	int matric[Max][Max];   //邻接矩阵
public:
	Solution(int v, int e) {
		vexnum = v;
		edgenum = e;
		for(int i=0;i<v;i++)
			for (int j = 0; j < v; j++)
			{
				if (i == j)
					matric[i][j] = 0;
				else
				    matric[i][j] = inf;
			}
	}
	void Assignment();   //为邻接矩阵赋值，大小为边的权值
	void Floyd();     //计算两点间最小路径长度
	void Print();   //打印最后两点间的最短路径
};
void Solution::Floyd()   //计算两点间最小路径长度
{
	int i = 0, j = 0, k = 0;
	for(i=0;i<vexnum;i++)
		for (j = 0; j < vexnum; j++)
		{
			for (k = 0; k < vexnum; k++)
			{
				if (matric[j][k] > matric[j][i] + matric[i][k])
					matric[j][k] = matric[j][i] + matric[i][k];
			}
		}
}
void Solution::Assignment()
{
	cout << "请输入图中有向边的起点、终点和权值" << endl;
	int start, end, weight;
	int i, j;
	for (i = 0; i < edgenum; i++)
	{
		cin >> start >> end >> weight;
		matric[start][end] = weight;
	}
}
void Solution::Print()
{
	for (int i = 0; i < vexnum; i++)
	{
		for (int j = 0; j < vexnum; j++)
		{
         printf("%2d ",matric[i][j]);
		}
	cout << endl;
	}		
}
int main()
{
	int v, e;
	cout << "请输入顶点数，边数" << endl;
	cin >> v >> e;
	Solution s(v, e);
	s.Assignment();
	s.Floyd();
	s.Print();
	system("pause");
}

 运行结果如下所示：

内容总结

以上是互联网集市为您收集整理的floyd算法简单化表示过程全部内容，希望文章能够帮你解决floyd算法简单化表示过程所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---