一个有向图D由顶点集V和边集E构成。如果D有n个顶点，那么顶点集为<img src="https://static.zxtiku.com/wangke/imgs/topic/e2e2c4f904aa745b738181b96166e548.png"/>，如果在D中从<img src="https://static.zxtiku.com/wangke/imgs/topic/43da0c98c11557b1395737fdd57e884b.png"/>到<img src="https://static.zxtiku.com/wangke/imgs/topic/2e69e6bfdae164892f9e9bf151f64dd3.png"/>有一条有向边，那么<img src="https://static.zxtiku.com/wangke/imgs/topic/ffc9527b5065b6458248b15456e819f0.png"/>属于E。有向图D可以用一个n行n列的0-1矩阵M来表示。如果D中的<img src="https://static.zxtiku.com/wangke/imgs/topic/ac764cc99a22d928d411bf87dfca9e1b.png"/>到<img src="https://static.zxtiku.com/wangke/imgs/topic/f9532c30ab70d9cf2b0090a76c2926c0.png"/>有一条有向边，那么矩阵M的第i行第j列元素<img src="https://static.zxtiku.com/wangke/imgs/topic/6409c1296ce7c87955403c19b767eeb2.png"/>；否则<img src="https://static.zxtiku.com/wangke/imgs/topic/f0a95f25de8e2e36547f75a902de8f71.png"/>。图的连通性是指从图的某些顶点到其他顶点存在一条由连续有向边构成的路径。一个著名的检查图的连通性的算法就是Warshall算法。假设M是图D的矩阵表示，考虑n+1个矩阵构成的序列<img src="https://static.zxtiku.com/wangke/imgs/topic/96462a1a37c607c22b4041663d6ffc5a.png"/>将矩阵<img src="https://static.zxtiku.com/wangke/imgs/topic/b98a62c471e0803035d4e8918c0eec7d.png"/>的i行j列元素记作<img src="https://static.zxtiku.com/wangke/imgs/topic/15db3b40201667ce201ffe56ff3b58bf.png"/>。对于<img src="https://static.zxtiku.com/wangke/imgs/topic/01c86e66f09df95d1f1737b1c2ddd6d9.png"/>当且仅当图中存在一条从<img src="https://static.zxtiku.com/wangke/imgs/topic/c7408d6a7e32dd797d076493d6d911a2.png"/>到<img src="https://static.zxtiku.com/wangke/imgs/topic/1d5ebd090b120ae7e912e4e4f6b1eb74.png"/>的路径，并且这条路径除端点外中间只经过<img src="https://static.zxtiku.com/wangke/imgs/topic/5907394282a046b0a3b884364eb5526b.png"/>中的顶点。不难看出<img src="https://static.zxtiku.com/wangke/imgs/topic/9412a0c5865fa7c28c3388f6cb50c2ba.png"/>就是M，而在<img src="https://static.zxtiku.com/wangke/imgs/topic/1487fb088a16362a8a3fc1c2f27d50ac.png"/>中如果<img src="https://static.zxtiku.com/wangke/imgs/topic/200ecf784d22f94aba6ea13435d5a0f6.png"/>，则说明D中<img src="https://static.zxtiku.com/wangke/imgs/topic/783cad2fc4fcbb89f3f1210d5ec9c502.png"/>和<img src="https://static.zxtiku.com/wangke/imgs/topic/1f72ff90f8f28afe2a8c9792a1d919bb.png"/>是连通的。Warshall算法从<img src="https://static.zxtiku.com/wangke/imgs/topic/ddf1f7f324bf87f21067445a061fb1f1.png"/>开始，顺序计算<img src="https://static.zxtiku.com/wangke/imgs/topic/09c59238c391ebfb69447b68df0bcf1d.png"/>,直到<img src="https://static.zxtiku.com/wangke/imgs/topic/071cc0369a927478b0da64f0f68b9aaf.png"/>为止。可以通过动态规划的迭代实现Warshall算法，用以下实例作为输入，给出实例的结果。假设某有向网络的结点是a,b,c,d，已知网络的矩阵表示是： ‎<img src="https://static.zxtiku.com/wangke/imgs/topic/8d5f87a77113a15c152e3145b9285f1f.png"/>‎