warshall算法图解

1. Warshall算法求传递闭包，Python语言~

def __warshall(self, a):
assert (len(row) == len(a) for row in a)
n = len(a)
#请在下面编程实现Roy-Warshall求传递闭包的算法
#参数a：为一个关系矩阵
# 请删除pass后编程实现该方法功能
for i in range(n) :
for j in range(n):
if a[j][i] == 1:
for k in range(n):
a[j][k] = a[j][k] | a[i][k]
# 请在上面编写程序，不要修改下面代码
return a

2. Warshall算法的算法介绍

1、引言
Warshall在1962年提出了一个求关系的传递闭包的有效算法。其具体过程如下，设在n个元素的有限集上关系R的关系矩阵为M：
（1）置新矩阵A=M;
（2）置k=1;
（3）对所有i如果A[i,k]=1，则对j=1..n执行：
A[i,j]←A[i,j]∨A[k,j];
（4）k增1;
（5）如果k≤n，则转到步骤（3），否则停止。
所得的矩阵A即为关系R的传递闭包t(R)的关系矩阵。
在左孝凌等编着的《离散数学》中提到了该算法，但并未对此算法作出解释。下面本文将对该算法的思想作出一种比较通俗的解说。
2、对Warshall算法的解说
设关系R的关系图为G，设图G的所有顶点为v1,v2,…,vn，则t(R)的关系图可用该方法得到：若G中任意两顶点vi和vj之间有一条路径且没有vi到vj的弧，则在图G中增加一条从vi到vj的弧，将这样改造后的图记为G’，则G’即为t(R)的关系图。G’的邻接矩阵A应满足：若图G中存在从vi到vj路径，即vi与vj连通，则A[i,j]=1，否则A[i,j]=0。
这样，求t(R)的问题就变为求图G中每一对顶点间是否连通的问题。
定义一个n阶方阵序列A(0),A(1),A(2),…,A(n)，每个方阵中的元素值只能取0或1。A(m)[i,j]=1表示存在从vi到vj且中间顶点序号不大于m的路径（m=1..n），A(m)[i,j]=0表示不存在这样的路径。而A(0)[i,j]=1表示存在从vi到vj的弧，A(0)[i,j]=0表示不存在从vi到vj的弧。
这样，A(n)[i,j]=1表示vi与vj连通，A(n)[i,j]=0表示vi与vj不连通。故A(n)即为t(R)的关系矩阵。
那么应如何计算方阵序列A(0),A(1),A(2),…,A(n)呢？
很显然，A(0)=M（M为R的关系矩阵）。
若A(0)[i,1]=1且A(0)[1,j]=1，或A(0)[i,j]=1，当且仅当存在从vi到vj且中间顶点序号不大于1的路径，此时应将A(1)[i,j]置为1，否则置为0。
一般地，若A(k-1)[i,k]=1且A(k-1)[k,j]=1，或A(k-1)[i,j]=1，当且仅当存在从vi到vj且中间顶点序号不大于k的路径，此时应将A(k)[i,j]置为1，否则置为0（k=1..n）。用公式表示即为：
A (k)[i,j]=(A(k-1)[i,k]∧A(k-1)[k,j])∨A(k-1)[i,j] i,j,k=1..n
这样，就可得计算A(k)的方法：先将A(k)赋为A(k-1)；再对所有i=1..n，若A(k)[i,k]=1（即A(k-1)[i,k]=1），则对所有j=1..n，执行：
A (k)[i,j]←A(k)[i,j]∨A(k-1)[k,j]
但这与前述Warshall算法中的第（3）步还有一定距离。若将上式改为：
A(k)[i,j]←A(k)[i,j]∨A(k)[k,j] （即把A(k-1)[k,j]改为A(k)[k,j]）
就可将上标k去掉，式子就可进一步变为：
A[i,j]←A[i,j]∨A[k,j]
这样可以只用存储一个n阶方阵的空间完成计算，且与前述Warshall算法中第（3）步的式子一致。那么，可不可以把A(k-1)[k,j]改为A(k)[k,j]呢？答案是肯定的。下面将证明在计算A(k)的过程中A(k-1)[k,j]与A(k)[k,j]相等（A(k)被赋初值A(k-1)后）。考察计算A(k)的方法 只有当i=k时A(k)[k,j]的值才有可能改变，此时将式A(k)[i,j]←A(k)[i,j]∨A(k-1)[k,j]中的i换为k，得A(k)[k,j]←A(k)[k,j]∨A(k-1)[k,j]，对某一j，执行该式的赋值操作前A(k)[k,j]=A(k-1)[k,j]，因为计算A(k)开始时A(k)被赋为A(k-1)，故它们相或的结果等于A(k-1)[k,j]，故赋值操作不改变A(k)[k,j]的值。这样，就没有操作会改变A(k)[k,j]的值，故A(k-1)[k,j]与A(k)[k,j]相等。
综上，就可得到计算A(n)的算法，且该算法与前述的Warshall算法完全一致。
由上面的分析，不难看出，Warshall算法类似于求图中每对顶点间最短路径的Floyd算法。其实，用Floyd算法也能求关系的传递闭包，方法为令关系R的关系图G中的每条弧的权值都为1，这样得一有向网G1，设G1的邻接矩阵为D(-1)（若vi无自回路，则D(-1)(i,i)=∞），对G1用Floyd算法求其每对顶点间最短路径，得结果矩阵D(n-1)。因若G中vi与vj连通，当且仅当D(n-1)[i,j]≠∞，故将矩阵D中的∞都改为0，其它值都改为1，得矩阵A，则矩阵A即为t(R)的关系矩阵。Floyd算法和Warshall算法的时间复杂度都为O(n3)，但明显用Floyd算法求关系的传递闭包绕了弯子。
参考文献：
[1]左孝凌，李为鉴，刘永才，《离散数学》，上海：上海科学技术文献出版社，1982
[2]严蔚敏，吴伟民，《数据结构 C语言版》，北京：清华大学出版社，1997

3. floyd-warshanll算法是什么啊

Floyd-Warshall算法是解决任意两点间的最短路径的一种算法。
Floyd-Warshall算法的描述如下： for k:=1 to n do for i:=1 to n do for j:=1 to n do if dist[i,k]+dist[k,j]<dist[i,j] then dist[i,j]:=dist[i,k]+dist[k,j];
Floyd-Warshall 算法用来找出每对点之间的最短距离。它需要用邻接矩阵来储存边，这个算法通过考虑最佳子路径来得到最佳路径。
注意单独一条边的路径也不一定是最佳路径。
从任意一条单边路径开始。所有两点之间的距离是边的权，或者无穷大，如果两点之间没有边相连。
对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比己知的路径更短。如果是更新它。
不可思议的是，只要按排适当，就能得到结果。 // dist(i,j) 为从节点i到节点j的最短距离 For i←1 to n do For j←1 to n do dist(i,j) = weight(i,j) For k←1 to n do // k为“媒介节点” For i←1 to n do For j←1 to n do if (dist(i,k) + dist(k,j) < dist(i,j)) then // 是否是更短的路径？ dist(i,j) = dist(i,k) + dist(k,j)
这个算法的效率是O(V^3)。它需要邻接矩阵来储存图。
这个算法很容易实现，只要几行。
即使问题是求单源最短路径，还是推荐使用这个算法，如果时间和空间允许(只要有放的下邻接矩阵的空间，时间上就没问题)。
计算每一对顶点间的最短路径（floyd算法）
【例题】设计公共汽车线路(1) 现有一张城市地图，图中的顶点为城市，有向边代表两个城市间的连通关系，边上的权即为距离。现在的问题是，为每一对可达的城市间设计一条公共汽车线路，要求线路的长度在所有可能的方案里是最短的。
输入： n (城市数，1≤n≤20) e (有向边数1≤e≤210) 以下e行，每行为边（i,j）和该边的距离wij（1≤i,j≤n）
输出： k行，每行为一条公共汽车线路
分析：本题给出了一个带权有向图，要求计算每一对顶点间的最短路径。这个问题虽然不是图的连通性问题，但是也可以借鉴计算传递闭包的思想：在枚举途径某中间顶点k的任两个顶点对i和j时，将顶点i和顶点j中间加入顶点k后是否连通的判断，改为顶点i途径顶点k至顶点j的路径是否为顶点i至顶点j的最短路径（1≤i，j，k≤n）。 显然三重循环即可计算出任一对顶点间的最短路径。设 n—有向图的结点个数； path—最短路径集合。其中path[i，j]为vi至vj的最短路上vj的前趋结点序号(1≤i，j≤n)； adj—最短路径矩阵。初始时为有向图的相邻矩阵
我们用类似传递闭包的计算方法反复对adj矩阵进行运算，最后使得adj成为存储每一对顶点间的最短路径的矩阵 (1≤i，j≤n) Var adj：array[1‥n，1‥n] of real； path：array[1‥n，1‥n] of 0‥n；
计算每一对顶点间最短路径的方法如下：
首先枚举路径上的每一个中间顶点k（1≤k≤n）；然后枚举每一个顶点对（顶点i和顶点j，1≤i，j≤n）。如果i顶点和j顶点间有一条途径顶点k的路径，且该路径长度在目前i顶点和j顶点间的所有条途径中最短，则该方案记入adj[i，j]和path[i，j] adj矩阵的每一个元素初始化为∞；
for i←1 to n do {初始时adj为有向图的相邻矩阵，path存储边信息} for j←1 to n do if wij<>0 then begin adj[i，j]←wij； path[i，j]←j； end{then} else path[i，j]←0； for k←1 to n do {枚举每一个中间顶点} for i←1 to n do {枚举每一个顶点对} for j←1 to n do if adj[i，k]+adj[k，j]<adj[i，j]{若vi经由vk 至vj的路径目前最优，则记下} then begin adj[i，j]←adj[i，k]+adj[k，j]； path[i，j]←path[k，j]； end，{then} 计算每一对顶点间最短路径时间复杂度为W(n3)。算法结束时，由矩阵path可推知任一结点对i、j之间的最短路径方案是什么 Procere print(i，j)； begin if i=j then 输出i else if path[i，j]=0 then 输出结点i与结点j之间不存在通路 else begin print (i，path[i，j])； {递归i顶点至j顶点的前趋顶点间的最短路径} 输出j； end；{else} end；{print} 由此得出主程序 距离矩阵w初始化为0； 输入城市地图信息（顶点数、边数和距离矩阵w）； 计算每一对顶点间最短路径的矩阵path； for i←1 to n do {枚举每一个顶点对} for j←1 to n do if path[i，j]<>0 {若顶点i可达顶点j，则输出最短路径方案} then begin print（i，j）； writeln； end；{then}

4. Floyd算法的算法过程

1，从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。
2，对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比已知的路径更短。如果是更新它。
把图用邻接矩阵G表示出来，如果从Vi到Vj有路可达，则G[i,j]=d，d表示该路的长度；否则G[i,j]=无穷大。定义一个矩阵D用来记录所插入点的信息，D[i,j]表示从Vi到Vj需要经过的点，初始化D[i,j]=j。把各个顶点插入图中，比较插点后的距离与原来的距离，G[i,j] = min( G[i,j], G[i,k]+G[k,j] )，如果G[i,j]的值变小，则D[i,j]=k。在G中包含有两点之间最短道路的信息，而在D中则包含了最短通路径的信息。
比如，要寻找从V5到V1的路径。根据D，假如D(5,1)=3则说明从V5到V1经过V3，路径为{V5,V3,V1}，如果D(5,3)=3，说明V5与V3直接相连，如果D(3,1)=1，说明V3与V1直接相连。

5. 最短路径 | 深入浅出Dijkstra算法（一）

上次我们介绍了神奇的只有 五行的 Floyd-Warshall 最短路算法 ，它可以方便的求得 任意两点的最短路径， 这称为 “多源最短路”。

这次来介绍 指定一个点（源点）到其余各个顶点的最短路径， 也叫做 “单源最短路径”。 例如求下图中的 1 号顶点到 2、3、4、5、6 号顶点的最短路径。

与 Floyd-Warshall 算法一样，这里仍然 使用二维数组 e 来存储顶点之间边的关系， 初始值如下。

我们还需要用 一个一维数组 dis 来存储 1 号顶点到其余各个顶点的初始路程， 我们可以称 dis 数组为 “距离表”， 如下。

我们将此时 dis 数组中的值称为 最短路的“估计值”。

既然是 求 1 号顶点到其余各个顶点的最短路程， 那就 先找一个离 1 号顶点最近的顶点。

通过数组 dis 可知当前离 1 号顶点最近是 2 号顶点。 当选择了 2 号顶点后，dis[2]的值就已经从“估计值”变为了“确定值”， 即 1 号顶点到 2 号顶点的最短路程就是当前 dis[2]值。

为什么呢？你想啊， 目前离 1 号顶点最近的是 2 号顶点，并且这个图所有的边都是正数，那么肯定不可能通过第三个顶点中转，使得 1 号顶点到 2 号顶点的路程进一步缩短了。 因此 1 号顶点到其它顶点的路程肯定没有 1 号到 2 号顶点短，对吧 O(∩_∩)O~

既然选了 2 号顶点，接下来再来看 2 号顶点 有哪些 出边 呢。有 2->3 和 2->4 这两条边。

先讨论 通过 2->3 这条边能否让 1 号顶点到 3 号顶点的路程变短。 也就是说现在来比较 dis[3] 和 dis[2]+e[2][3] 的大小。其中 dis[3]表示 1 号顶点到 3 号顶点的路程，dis[2]+e[2][3]中 dis[2]表示 1 号顶点到 2 号顶点的路程，e[2][3]表示 2->3 这条边。所以 dis[2]+e[2][3]就表示从 1 号顶点先到 2 号顶点，再通过 2->3 这条边，到达 3 号顶点的路程。

我们发现 dis[3]=12，dis[2]+e[2][3]=1+9=10，dis[3]>dis[2]+e[2][3]，因此 dis[3]要更新为 10。这个过程有个专业术语叫做 “松弛” 。即 1 号顶点到 3 号顶点的路程即 dis[3]，通过 2->3 这条边 松弛成功。 这便是 Dijkstra 算法的主要思想： 通过 “边” 来松弛 1 号顶点到其余各个顶点的路程。

同理通过 2->4（e[2][4]），可以将 dis[4]的值从 ∞ 松弛为 4（dis[4]初始为 ∞，dis[2]+e[2][4]=1+3=4，dis[4]>dis[2]+e[2][4]，因此 dis[4]要更新为 4）。

刚才我们对 2 号顶点所有的出边进行了松弛。松弛完毕之后 dis 数组为：

接下来，继续在剩下的 3、4、5 和 6 号顶点中，选出离 1 号顶点最近的顶点。通过上面更新过 dis 数组，当前离 1 号顶点最近是 4 号顶点。此时，dis[4]的值已经从“估计值”变为了“确定值”。下面继续对 4 号顶点的所有出边（4->3，4->5 和 4->6）用刚才的方法进行松弛。松弛完毕之后 dis 数组为：

继续在剩下的 3、5 和 6 号顶点中，选出离 1 号顶点最近的顶点，这次选择 3 号顶点。此时，dis[3]的值已经从“估计值”变为了“确定值”。对 3 号顶点的所有出边（3->5）进行松弛。松弛完毕之后 dis 数组为：

继续在剩下的 5 和 6 号顶点中，选出离 1 号顶点最近的顶点，这次选择 5 号顶点。此时，dis[5]的值已经从“估计值”变为了“确定值”。对5号顶点的所有出边（5->4）进行松弛。松弛完毕之后 dis 数组为：

最后对 6 号顶点的所有出边进行松弛。因为这个例子中 6 号顶点没有出边，因此不用处理。 到此，dis 数组中所有的值都已经从“估计值”变为了“确定值”。

最终 dis 数组如下，这便是 1 号顶点到其余各个顶点的最短路径。

OK，现在来总结一下刚才的算法。 Dijkstra算法的基本思想是：每次找到离源点（上面例子的源点就是 1 号顶点）最近的一个顶点，然后以该顶点为中心进行扩展，最终得到源点到其余所有点的最短路径。

基本步骤如下：

在 博客 中看到两个比较有趣的问题，也是在学习Dijkstra时，可能会有疑问的问题。

当我们看到上面这个图的时候，凭借多年对平面几何的学习，会发现在“三角形ABC”中，满足不了 构成三角形的条件(任意两边之和大于第三边)。 纳尼，那为什么图中能那样子画？

还是“三角形ABC”，以A为起点，B为终点，如果按照平面几何的知识， “两点之间线段最短”， 那么，A到B的最短距离就应该是6(线段AB)，但是，实际上A到B的最短距离却是3+2=5。这又怎么解释？

其实，之所以会有上面的疑问，是因为 对边的权值和边的长度这两个概念的混淆， 。之所以这样画，也只是为了方便理解（每个人写草稿的方式不同，你完全可以用别的方式表示，只要便于你理解即可）。

PS：数组实现邻接表可能较难理解，可以看一下 这里

参考资料：

Dijkstra算法是一种基于贪心策略的算法。每次新扩展一个路程最短的点，更新与其相邻的点的路程。当所有边权都为正时，由于不会存在一个路程更短的没扩展过的点，所以这个点的路程永远不会再被改变，因而保证了算法的正确性。

根据这个原理， 用Dijkstra算法求最短路径的图不能有负权边， 因为扩展到负权边的时候会产生更短的路径，有可能破坏了已经更新的点路径不会发生改变的性质。

那么，有没有可以求带负权边的指定顶点到其余各个顶点的最短路径算法（即“单源最短路径”问题）呢？答案是有的， Bellman-Ford算法 就是一种。（我们已经知道了 Floyd-Warshall 可以解决“多源最短路”问题，也要求图的边权均为正）

通过 邻接矩阵 的Dijkstra时间复杂度是 。其中每次找到离 1 号顶点最近的顶点的时间复杂度是 O(N)，这里我们可以用 优先队列（堆） 来优化，使得这一部分的时间复杂度降低到 。这个我们将在后面讨论。

6. floyd算法能不能保证有最优解

Floyd算法又称为弗洛伊德算法，插点法，是一种用于寻找给定的加权图中顶点间最短路径的算法。

算法过程:

把图用邻接距阵G表示出来，如果从Vi到Vj有路可达，则G[i,j]=d，d表示该路的长度；否则G[i,j]=空值。

定义一个距阵D用来记录所插入点的信息，D[i,j]表示从Vi到Vj需要经过的点，初始化D[i,j]=j。
把各个顶点插入图中，比较插点后的距离与原来的距离，G[i,j] = min( G[i,j], G[i,k]+G[k,j] )，如果G[i,j]的值变小，则D[i,j]=k。

在G中包含有两点之间最短道路的信息，而在D中则包含了最短通路径的信息。
比如，要寻找从V5到V1的路径。根据D，假如D(5,1)=3则说明从V5到V1经过V3，路径为{V5,V3,V1}，如果D(5,3)=3，说明V5与V3直接相连，如果D(3,1)=1，说明V3与V1直接相连。

7. Warshall算法求传递闭包

#include <stdio.h>
#include <stdlib.h>
#define N 20
#define M 20

main()
{
int i,j,k,m,n;
int r1[M],r2[M],a[N],mr[N][N]={0};

FILE * fp;
printf("程序自动调用c:/stone2.txt文件内相应数据\n");
fp=fopen("c:\\stone2.txt","r");
fscanf(fp,"%d",&n); /*读取集合元素个数*/
for(i=0;i<n;i++) /*读取集合元素*/
fscanf(fp,"%d",&a[i]);
fscanf(fp,"%d",&m); /*读取关系个数*/
for(k=0;k<m;k++)
fscanf(fp,"%d,%d",&r1[k],&r2[k]); /*读取关系*/

fclose(fp);

printf("自反闭包r(R):\n{");
for(i=0;i<n;i++) printf("<%d,%d>,",a[i],a[i]); /*输出自反闭包*/
for(k=0;k<m;k++)
{
if(r1[k]!=r2[k]) printf("<%d,%d>,",r1[k],r2[k]);
else continue;
}
printf("\b}\n");

printf("对称闭包s(R):\n{"); /*输出对称闭包*/
for(k=0;k<m;k++)
{
if(r1[k]!=r2[k]) printf("<%d,%d>,<%d,%d>,",r1[k],r2[k],r2[k],r1[k]);
else printf("<%d,%d>,",r1[k],r2[k]);
}
printf("\b}\n");

k=0;
for(i=0;i<n,k<m;i++)
{
if(r1[k]!=a[i]) continue;
else
{
for(j=0;j<n,k<m;j++) /*关系转换成矩阵*/
{
if(r2[k]!=a[j]) continue;
else
{
mr[i][j]=1;
k++; i=0;j=0;
break;
}
}
}
}

printf("关系所对应的关系矩阵:\n");
for(i=0;i<n;i++)
{ /*打印关系矩阵*/
for(j=0;j<n;j++)
printf("%5d",mr[i][j]);
printf("\n");
}
for(k=0;k<n;k++)
for(i=0;i<n;i++) /*warshall*/
for(j=0;j<n;j++)
mr[i][j]+=mr[i][j]+mr[i][k]*mr[k][j];

for(i=0;i<n;i++)
for(j=0;j<n;j++)
{ /*把mr[]非0项赋值为1*/
if(!mr[i][j]) continue;
else mr[i][j]=1;
}

printf("传递闭包对应关系矩阵:\n");
for(i=0;i<n;i++)
{ /*输出传递闭包对应的关系矩阵*/
for(j=0;j<n;j++)
printf("%5d",mr[i][j]);
printf("\n");
}

system("PAUSE");

}
自己写的,三个闭包都有,包括传递闭包,看注释就知道了,还是用文件读写,方便数据输入

8. 最短路径的解决方法

用于解决最短路径问题的算法被称做“最短路径算法”， 有时被简称作“路径算法”。 最常用的路径算法有：
Dijkstra算法
SPFA算法Bellman-Ford算法
Floyd算法Floyd-Warshall算法
Johnson算法
A*算法
所谓单源最短路径问题是指：已知图G=（V，E），我们希望找出从某给定的源结点S∈V到V中的每个结点的最短路径。
首先，我们可以发现有这样一个事实：如果P是G中从vs到vj的最短路，vi是P中的一个点，那么，从vs沿P到vi的路是从vs到vi的最短路。