Warshall算法

来自计算思维百科
跳转至: 导航搜索
Warshall算法1.png

在一个有向图中,我们需要确定一条最短的通路,通过这条通路可以到达所有节点。这条通路就称为传递闭包。

基本概念

有向图的传递闭包表达的就是每个顶点之间的可达性,这种可达路径是最短的。当然,可以从每个起点开始深度或广度优先遍历,能遍历到的顶点就说明从这个点到它可达,这样来生成传递闭包。这样做对图进行了多次遍历,我们希望找到更好一点的办法,这样的算法的确存在,成为Warshall算法。它是以S.Warshall的名字命名的。

应用范围

Warshall算法应用十分广泛。在物流管理方面、计算机内的自动编译程序构造、供电系统抗震可靠性分析,公交查询系统、图转换系统依赖检测以及计算机网络方面的应用等多方面都有很大的贡献。

使用方法及步骤

给定一个有向图:

Warshall算法2.png

1. 写出其邻接矩阵R0

Warshall算法3.png

2. 通过一次加入一个点来构造出最后的闭包(n个点,n次)。用R0表示初始矩阵,用R1 ,R2 ,…, Rk,…, Rn反映依次加入中间节点编号不大于k的路径 。具体使用过程如下

Warshall算法4.png

该矩阵反映了给定有向图的初始状态,其中被红框标记的行和列用于计算R1

Warshall算法5.png

从上述矩阵中可以计算R1,根据Warshall算法:如果Rk-1中一个元素rij为0,那么只有当在这个矩阵中的第i行第k列的元素rik和rkj都为1时,那么rij在Rk中才可变为1;如果Rk-1中一个元素rij为1, 那么rij在Rk中仍为1。因此可以求得:

Warshall算法6.png

3. 依次按2的方法加入编号2、编号3、编号4的点,可以得到最后的传递闭包为:

Warshall算法7.png

最后的R4即为上述有向图的传递闭包,表示的意义为从每个顶点到其他顶点的可达性。

应用案例

应用1-设计公共汽车线路

案例:现有一张城市地图,图中的顶点为城市,有向边代表两个城市间的连通关系,现在的问题是,为每一对可达的城市间设计一条公共汽车线路。下图给出该城市的联通图。

Warshall算法8.png

解决步骤:

根据上述使用方法可以得出各个矩阵为:

Warshall算法9.png

可以看出从a城市可以到达b,c,d城市,故只需要在a城市设立公交首站即可。

应用2-物流点设置问题

案例:一个物流公司打算在xx省开拓业务,预计业务将遍布全省的8个城市,考虑到建设成本,不可能在每个城市都开设物流点,该如何设置最少的物流点使得业务可以遍布8个城市?

解决步骤:同案例1

可以体现的计算思维

从上面的过程可以发现在求解过程中都是为了充分利用资源而进行有效的规划,体现了计算思维中的规划思想。