高考问答装在口袋里的爸爸评价:Warshall算法
来源：百度文库 编辑：高考问答 时间：2024/05/13 20:18:14
Warshall算法的定义是什么?
举例说明Warshall算法
举例说明Warshall算法
Warshall算法是计算稠密有向图的传递闭包的首选。
通过计算传递闭包后，可以测试有向图中任何顶点是否可以从其它顶点到达的能力。
经典形式
for(i=0;i<V;++i)
for(s=0;s<V;++s)
for(t=0;t<V;++t)
if(A[s][i] && A[i][t]) A[s][t]=1;
用接邻矩阵A表示有向图，可以定义为 bool A[V][V];
V是A中的总结点数
A[i][j]=1表示从i到j有一条边，
A[i][j]=0表示i到j没有边；