好贷网好贷款

Floyd算法

发布时间:2016-12-4 14:21:06 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"Floyd算法",主要涉及到Floyd算法方面的内容,对于Floyd算法感兴趣的同学可以参考一下。

      最近在准备招聘的时候看到了华为的一道关于floyd算法的题,故在想总结一下这个算法以加深我对这个算法的理解。      Floyd算法又称为弗洛伊德算法,插点法,是一种用于寻找给定的加权图中顶点间最短路径的算法。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。该算法的核心思想主要由三重循环构成,故该算法的时间复杂度为O(n^3).      其状态转移方程如下: map[i,j]:=min{map[i,k]+map[k,j],map[i,j]}     map[i,j]表示i到j的最短距离,k是i,j的穷举断点。     其实说到底这个算法并不难,就是通过简单的穷举来吧加权图中所有的顶点都遍历一次,并更新每个顶点间的最短距离。     算法剖析:        Floyd算法的基本思想如下:从任意节点A到任意节点B的最短路径不外乎2种可能: 1是直接从A到B, 2是从A经过若干个节点X到B。 所以,我们假设dis(AB)为节点A到节点B的最短路径的距离,对于每一个节点X,我们检查dis(AX) + dis(XB) < dis(AB)是否成立,如果成立,证明          从A到X再到B的路径比A直接到B的路径短,我们便设置dis(AB)= dis(AX) +dis(XB),这样一来,当我们遍历完所有节点X,dis(AB)中记录的便是A到        B的最短路径的距离。 注意点 三个循环的求中间点的K的循环必须放在外面。 因为如果放在内层,对于A—B之间的经过AX和BX的还没有求到最小值,所以A—B最后不是最小值 好吧,下面我们就以华为的一道上机考试题作为代码示例。(代码参考网上的一位网友的,个人认为写得不错。) 题目: 地铁换乘       已知2条地铁线路,其中A为环线,B为东西向线路,线路都是双向的。经过的站点名分别如下,两条线交叉的换乘点用T1、T2表示。编写程序,      任意输入两个站点名称,输出乘坐地铁最少需要经过的车站数量(含输入的起点和终点,换乘站点只计算一次)。      地铁线A(环线)经过车站:A1 A2 A3 A4 A5 A6 A7 A8 A9 T1 A10 A11 A12 A13 T2 A14 A15 A16 A17 A18      地铁线B(直线)经过车站:B1 B2 B3 B4 B5 T1 B6 B7 B8 B9 B10 T2 B11 B12 B13 B14 B15 #include <cstdlib> #include <iostream> #include <string> /* Author : 俗人 Time : 2013/9/2 description : 地铁换乘问题 已知2条地铁线路,其中A为环线,B为东西向线路,线路均为双向, 换乘点为 T1,T2,编写程序,任意输入两个站点名称,输出乘坐地铁 最少所需要经过的车站数量 A(环线):A1...A9 T1 A10...A13 T2 A14...A18 B(直线):B1...B5 T1 B6...B10 T2 B11...B15 样例输入:A1 A3 样例输出:3 */ using namespace std; //无向图的数据结构 struct Graph { int arrArc[100][100]; //邻接矩阵 int verCount; //点数 int arcCount; //边数 }; //FLOYD算法 求任意两点最短路径矩阵 void floyd(Graph *p,int dis[100][100]){ for(int k = 1;k <= p->verCount;k++) for(int i = 1; i <= p->verCount;i++) for(int j = 1;j <= p->verCount;j++) { //存在更近的路径,则更新 if(dis[i][j]>dis[i][k]+dis[k][j]) dis[i][j]=dis[i][k]+dis[k][j]; } } //站名字符串转节点编号 int char_to_int(string s){ string s1[38] = {"A0","A1","A2","A3","A4","A5","A6","A7","A8","A9","A10", "A11","A12","A13","A14","A15","A16","A17","A18", "B1","B2","B3","B4","B5","B6","B7","B8","B9","B10", "B11","B12","B13","B14","B15","T1","T2"} ; for(int i=1 ; i <= 38;i ++){ if (s == s1[i]) return i; } return -1; } int main(int argc, char *argv[]) { Graph g; g.verCount = 37; g.arcCount = 35; cout<<"number of ver:"<<g.verCount<<" number of arc:" <<g.arcCount<<endl; //初始化邻接矩阵 for(int i = 1;i<=g.verCount;i++) { for(int j = 1;j<=g.verCount;j++) { //i到本身的距离为0 //不同节点值为不可达 if(i==j) g.arrArc[i][i]= 0; else g.arrArc[i][j] = 65535; } } //输入A环线个点相连情况 每个边权重都为1 int a[21] = {1,2,3,4,5,6,7,8,9,34,10,11,12,13,35,14,15,16,17,18,1}; for(int i=0;i<20;i++) { g.arrArc[a[i]][a[i+1]] = 1; g.arrArc[a[i+1]][a[i]] = 1; } //输入B线个点相连情况 每个边权重都为1 int b[17] = {19,20,21,22,23,34,24,25,26,27,28,35,29,30,31,32,33}; for(int i=0;i<16;i++) { g.arrArc[b[i]][b[i+1]] = 1; g.arrArc[b[i+1]][b[i]] = 1; } //计算邻接矩阵 floyd(&g,g.arrArc); cout << "请输入起始站点:" <<endl; string start; string end; cin >> start >> end; cout << g.arrArc[char_to_int(start)][char_to_int(end)] <<endl; system("PAUSE"); return EXIT_SUCCESS; }

上一篇:sql plus不能初始化以及sqlplus自动关闭的问题
下一篇:华为2013 大连理工 输入5个身高值[160~190之间]

相关文章

关键词: Floyd算法

相关评论