离散数学中Warshall算法简析
最近学了离散数学的图论，突然感觉离散数学的作⽤⼗分强⼤，相信学好离散数学中的算法，编程的魅⼒也不⾔⽽喻。闲话不多说，这篇博客中记录的是Warshall算法的简单解析及C++代码实现。
问题引出：在⼀个图结构中，常常需要两个节点之间有没有⼀条通路（通路长任意），也就是任意两点之间的可达情况，我们很⾃然会联想到⽤邻接矩阵来求可达矩阵，从⽽得出两点之间的可达情况。如： 微型空调
在这个图中，可以写出其邻接矩阵为：
0 1 1 1
1 0 0 0
时域 频域
1 0 0 1
1 0 1 0
记为矩阵A。那么很明显在图中，V2与V1存在直接通路（即长是1），V1与V4之间也有直接通路，但是V2与V4之间没有长度是1的通路，但是存在边长是2的通路，然⽽这在矩阵A中没有相应的体现，因为矩阵元素M（2，4） == 0，于是我们任意图中⼀点Vk，只要满⾜V（2k）乘以V（k4）！= 0[注意：括号中指的是下标]，则证明V2可以借助Vk（此图中指的是V1）与V4连通。
以此类推，当想得到任意⼀点与其他各点通路是2的连接的时候（这⾥指的是Vi，Vj两点）就可以逐个计算满⾜：V（ik）乘以V（kj）！= 0的，⽽V（ik）乘以V（kj）正好是求矩阵A乘以矩阵A的过程，所以矩阵A的平⽅就可以反应出通过边长为2图中各点之件的可达情况，以此类推，A的3次⽅、A的4次⽅……，分别表⽰了边长是3、边长是4……的可达情况，现在把所有可能长度的通路可达情况加起来（即A1⽅+ A2⽅ + A3⽅ +……），就可以得到近似可达矩阵。
为什么这⾥说是近似的可达矩阵？因为⼀个复杂的图中（如互联⽹模型），通路的长度成千上百都可能，那到底应该加到A的⼏次⽅才算有保证呢？很明显，这个算法存在局限性，对于简单的图还凑合，复杂的图就没有全⾯的保障了。Warshall算法就是为了求⼀个可靠的可达矩阵。
算法的⾃⼰的语⾔描述：依次遍历邻接矩阵中的所有元素（M[i,j]），⽐如按照先列后⾏进⾏，如果M[i，j] ！= 0，那么就把i⾏加到第j⾏上。
算法的代码描述：
#include <iostream>
using namespace std;
#define COLUMNS 4公共设施服务半径
#define ROWS 4
void Warshall(int nearArra[ROWS][COLUMNS]);
int main()
{
//定义邻接矩阵
//此处⼿动输⼊图的矩阵表⽰数据
int nearArra[4][4] = { { 1, 1, 0, 0 },
疯狂英语中学版{ 0, 0, 1, 0 },
{ 0, 1, 0, 0 },
{ 0, 1, 0, 0 } };
Warshall(nearArra);
//输出...
for (int i = 0; i < 4; i++) {马来亚的青春
for (int j = 0; j < 4; j++) {
if (nearArra[i][j] != 0) {
cout << 1 << " ";
}
else {
cout << 0 << " ";
}
}
cout << endl;
}
system("pause");
return 0;
}
void Warshall(int nearArra[ROWS][COLUMNS]) {
//Warshall算法求运⽤邻接矩阵求图中所有可能的通路（即可达矩阵）
//参数：图的邻接矩阵
for (int i = 0; i < COLUMNS; i++) {
for (int j = 0; j < ROWS; j++) {
if (0 != nearArra[j][i]) {
//若此位置是1，此位置对应的列序号的⾏（即i）加到当前位置的⾏（即j）上
for (int k = 0; k < COLUMNS; k++) {
nearArra[j][k] += nearArra[i][k];
}
}
}
}
}
还是代码更容易理解些，就是⾸先运⽤于⼆重循环做矩阵的遍历，然后如果满⾜条件就开始执⾏I⾏加到j⾏的操作，最终在主函数中输出。（注意这⾥是给定⼀个矩阵）代码输⼊
。经过算法处理后矩阵是：
当然这只是单纯的⽅法，他有许多其他的应⽤，后续研究时会继续更新，有错误和疑问及时讨论，希望⼤家⽀持！最后附上⼀个不错的关⽂章：
速度生活
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议