floyd 求最长路小环打路径怎么做

来源：蜘蛛抓取(WebSpider) 时间：2011-10-25 00:22 标签： floyd 求最长路
　　最小环：从一个点出发,经过一条简单路径回到起点成为环.图的最小环就是所有环中长度最小的.
　　怎样求最小环呢?
　　1传统的解决方法(dijkstra):&&&&&&& 任意一个最小环环的权值，我们都可以看成两个有边相连的结点i、j的直接距离加上i、j间不包含边(边i-&j)的最短路径。求最短路径我们第一个想到的就Dijkstra算法。而Dijkstra所求的是一个点到所有点的最短距离。用Dijkstra所求的i、j的最短距离一定是i、j的直接距离(如果i，j连通)，所以我们需要先将i、j的边从图中删除(若i，j不连通，则不用删除)，再用Dijkstra求新图中i、j的最短距离即可。所以我们每次在图中选取一条边，把它从图中删掉．然后对删掉的那条边所对应的2点进行Dijkstra，也就是m次Dijkstra。
　　2.floyd求最小环:
&&&&&&&&抛开Dijkstra算法，进而我们想到用Floyd算法。我们知道，Floyd算法在进行时会不断更新矩阵dist(k)。设dist[k，i，j]表示从结点i到结点j且满足所有中间结点，它们均属于集合{1，2，? ，k}的一条最短路径的权。其中dist[0，i,j ]即为初始状态i到j的直接距离。对于一个给定的赋权有向图， 求出其中权值和最小的一个环。我们可以将任意一个环化成如下形式：u-&k-&v -&(x1-& x2-& ? xm1)-& u(u与k、k与v都是直接相连的)，其中v -&(x1-& 2-& ? m)-& u是指v到u不经过k的一种路径。
&&&&&&& 在u，k，v确定的情况下，要使环权值最小， 则要求 (x1一&x2-&?一&xm)-&u路径权值最小．即要求其为v到u不经过k的最短路径，则这个经过u，k，v的环的最短路径就是：[v到u不包含k的最短距离]+dist[O，u，k]+dist[O，k，v]。我们用Floyd只能求出任意2点间满足中间结点均属于集合{1，2，? ，k}的最短路径，可是我们如何求出v到u不包含k的最短距离呢?&&&&&&&& 现在我们给k加一个限制条件：k为当前环中的序号最大的节点(简称最大点)。因为k是最大点，所以当前环中没有任何一个点&k，即所有点都&k。因为v-&(x1-&x2-&......xm)-&u属于当前环，所以x1，x2，? ，xm&k，即x1，x2．?。xm&k一1。这样，v到u的最短距离就可以表示成dist[k一1 ,u,v]。dist[k一1,v,u]表示的是从v到u且满足所有中间结点均属于集合{1，2，? ，k一1}的一条最短路径的权。接下来，我们就可以求出v到u不包含k的最短距离了。这里只是要求不包含k，而上述方法用的是dist[k一1，v，u]，求出的路径永远不会包含k+l，k+2，? 。万一所求的最小环中包含k+1，k+2，? 怎么办呢?的确，如果最小环中包含比k大的节点，在当前u,k,v所求出的环显然不是那个最小环。然而我们知道，这个最小环中必定有一个最大点kO，也就是说，虽然当前k没有求出我们所需要的最小环，但是当我们从k做到kO的时候，这个环上的所有点都小于kO了．也就是说在k=kO时一定能求出这个最小环。我们用一个实例来说明：假设最小环为1&3&4&5&6&2&1。的确，在u=l，v=4，k=3时，k&6，dist[3，4，1]的确求出的不是4&5&6&2&1这个环，但是，当u=4，v=6，k=5或u=5，v=2，k=6时，dist[k，v，u]表示的都是这条最短路径.所以我们在Floyd以后，只要枚举u．v，k三个变量即可求出最小环。时间复杂度为O(n3)。我们可以发现，Floyd和最后枚举u，v,k三个变量求最小环的过程都是u,v,k三个变量，所以我们可以将其合并。这样，我们在k变量变化的同时，也就是进行Floyd算法的同时，寻找最大点为k的最小环。
1 #include&cstdio&
2 #include&cstring&
3 #include&algorithm&
4 #define _Clr(x, y) memset(x, y, sizeof(x))
5 #define INF 0xfffffff
6 #define N 110
7 using namespace
9 int mat[N][N], dist[N][N];
10 int next[N][N]; // next[i][j]表示ｉ到ｊ经历的第一个点。
11 int path[N];
12 int cnt,
14 void Floyd()
int mins=INF;
for(int k=1; k&=n; k++)
for(int i=1; i&k; i++)
for(int j=i+1; j&k; j++)
int tmp = dist[i][j]+mat[i][k]+mat[k][j];
if(tmp & mins)// 更新最小环的权值
while(p!=j) // 记录最小环的路径
path[cnt++] =
p = next[p][j];
path[cnt++] =
path[cnt++] =
for(int i=1; i&=n; i++)
for(int j=1; j&=n; j++)
if(dist[i][k]+dist[k][j] & dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
next[i][j] = next[i][k];
if(mins==INF)
puts("No solution.");
for(int i=0; i& i++)
printf("%d%s", path[i], i==cnt-1 ? "\n":" ");
56 void Init()
for(int i=1; i&=n; i++)
for(int j=1; j&=n; j++)
mat[i][j] = dist[i][j] = INF;
next[i][j] =
65 int main()
int m, a, b,
while(~scanf("%d%d", &n, &m))
while(m--)
scanf("%d%d%d", &a, &b, &c);
if(c & mat[a][b])
mat[a][b] = mat[b][a] =
dist[a][b] = dist[b][a] =
阅读(...) 评论()下次自动登录
现在的位置:
& 综合 & 正文
图（Graph）——最小生成树、最短路径、Kruskal、Dijkstra、Floyd
4. 最小生成树
4.1 生成树
（1）定义：所有顶点均由边连接在一起，但不存在回路的图叫该图的生成树
（2）深度优先生成树与广度优先生成树
一个图可以有许多棵不同的生成树
所有生成树具有以下共同特点：
生成树的顶点个数与图的顶点个数相同
生成树是图的极小连通子图
4.2 最小生成树
生成树的每条边上的权值之和最小。
实例：在N个城市之间修路，总路线的总和最小问题。
4.2.1 Prim方法
设N=(V,{E})是连通网，TE是N上最小生成树中边的集合：
（1）初始令U={u0},(u0属于V), TE=NULL
（2）在所有u属于U,v属于V-U的边(u,v)属于E中，找一条代价最小的边(u0,v0)
（3）将(u0,v0)并入集合TE，同时v0并入U
（4）重复上述操作直至U=V为止，则T=(V,{TE})为N的最小生成树
4.2.2 Kruskal
设连通网N=(V,{E})，令最小生成树
（1）初始状态为只有n个顶点而无边的非连通图T=(V,{NULL})，每个顶点自成一个连通分量
（2）在E中选取代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中；否则，舍去此边，选取下一条代价最小的边
（3）依此类推，直至T中所有顶点都在同一连通分量上为止
5.拓扑排序和 关键路径
5.1 拓扑排序
拓扑排序的基础：有向无环图，它是描述一项工程进度的有效工具。
5.1.1 AOV网
用顶点表示活动，用弧表示活动间优先关系的有向图称为顶点表示活动的网(Activity On Vertex network)，简称AOV网
5.1.2 拓扑排序算法
（1）在有向图中选一个没有前驱的顶点且输出之
（2）从图中删除该顶点和所有以它为尾的弧
（3）重复上述两步，直至全部顶点均已输出；或者当图中不存在无前驱的顶点为止
5.2 关键路径
在AOV网中，完成工程的最短时间：从开始点到完成点的最长路径长度——关键路径。
Ve(j)——表示事件Vj的最早发生时间
Vl(j)——表示事件Vj的最迟发生时间
e(i)——表示活动ai的最早开始时间
l(i)——表示活动ai的最迟开始时间
l(i)-e(i)——表示完成活动ai的时间余量
6. 最短路径
最短路径：路径上所有边的权值之和最小。
6.1 某顶点到其它个点的最短路径
Dijkstra算法：
（1）初使时令 S={V0},T={其余顶点}，T中顶点对应的距离值
（2）若存在&V0,Vi&，为&V0,Vi&弧上的权值
（3）若不存在&V0,Vi&，为无穷
（4）从T中选取一个其距离值为最小的顶点W，加入S
（5）对T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的距离值比不加W的路径要短，则修改此距离值
（6）重复上述步骤，直到S中包含所有顶点，即S=V为止
6.2 每对顶点之间的最短路径
Floyd算法：
（1）初始时设置一个n阶方阵，令其对角线元素为0，若存在弧&Vi,Vj&，则对应元素为权值；否则为无穷
（2）逐步试着在原直接路径中增加中间顶点，若加入中间点后路径变短，则修改之；否则，维持原值
（3）所有顶点试探完毕，算法结束
&&&&推荐文章:
【上篇】【下篇】<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"
您的访问请求被拒绝 403 Forbidden - ITeye技术社区
您的访问请求被拒绝
亲爱的会员，您的IP地址所在网段被ITeye拒绝服务，这可能是以下两种情况导致：
一、您所在的网段内有网络爬虫大量抓取ITeye网页，为保证其他人流畅的访问ITeye，该网段被ITeye拒绝
二、您通过某个代理服务器访问ITeye网站，该代理服务器被网络爬虫利用，大量抓取ITeye网页
请您点击按钮解除封锁&&#xe621; 上传我的文档
&#xe602; 下载
&#xe60c; 收藏
毕业于医学院校，在医院工作，有相对丰富的护理经验
&#xe602; 下载此文档
正在努力加载中...
java Floyd算法求解最短路径问题(完整程序代码)(16页)
下载积分：2000
内容提示：java Floyd算法求解最短路径问题(完整程序代码)(16页)
文档格式：DOCX|
浏览次数：11|
上传日期： 16:54:07|
文档星级：&#xe60b;&#xe612;&#xe612;&#xe612;&#xe612;
该用户还上传了这些文档
java Floyd算法求解最短路径问题(完整程序代码)(16页)
官方公共微信

我要回帖

更多关于 floyd 求最长路 的文章

 

随机推荐