warshall算法

‘壹’ 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}

‘贰’ 最短路径问题5种类型

最短路径问题5种类型有Dijkstra算法、A*算法、SPFA算法、Bellman-Ford算法和Floyd-Warshall算法，

扩展知识：

用于解决最短路径问题的算法被称做“最短路径算法”，有时被简称作“路径算法”。最常用的路径算法有：
Dijkstra算法、A*算法、SPFA算法、Bellman-Ford算法和Floyd-Warshall算法，本文主要介绍其中的三种。
最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。
算法具体的形式包括：确定起点的最短路径问题：即已知起始结点，求最短路径的问题。
确定终点的最短路径问题：与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。
确定起点终点的最短路径问题：即已知起点和终点，求两结点之间的最短路径。

‘叁’ 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");

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