一个有向图D由顶点集V和E构成。如果D有n个顶点，那么顶点集为【图片】，如果在D中从【图片】到【图片】有一条有向边，那么【图片】属于E。有向图D可以用一个n行n列的0-1矩阵M来表示。如果D中的【图片】到【图片】有一条有向边，那么矩阵M的第i行第j列元素；否则【图片】。图的连通性是指从图的某些顶点到其他顶点存在一条由连续有向边构成的路径。一个著名的检查图的连通性的算法就是Warshall算法。假设M是图D的矩阵表示，考虑n+1个矩阵构成的序列【图片】将矩阵【图片】的i行j列元素记作【图片】。对于【图片】当且仅当图中存在一条从【图片】到【图片】的路径，并且这条路径除端点外中间只经过【图片】中的顶点。不难看出【图片】就是M，而在【图片】中如果【图片】，则说明D中【图片】和【图片】是连通的。Warshall算法从【图片】开始，顺序计算【图片】,直到【图片】为止。可以通过动态规划的迭代实现Warshall算法，用以下实例作为输入，给出实例的结果。假设某有向网络的结点是a,b,c,d，已知网络的矩阵表示是：【图片】