弗洛伊德算法(Floyd-Warshall)
admin
2024-04-14 15:18:25
0次

预计阅读时间:10分钟

一、简介

       弗洛伊德算法又名插点法,是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法。

       弗洛伊德算法是一种在具有正或负边缘权重但没有负周期的加权图中找到最短路径的算法。算法的单个执行将找到所有顶点对之间的最短路径的长度(加权)。 虽然它不返回路径本身的细节,但是可以通过对算法的简单修改来重建路径。 该算法的版本也可用于查找关系R的传递闭包,或在加权图中所有顶点对之间的最宽路径。

二、核心思路

路径矩阵

        即通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。 

        从图的带权临接A=[a(i,j)] n×n开始,迭代地进行n次更新,即由矩阵D(0)=A,按一个公式,构造出矩阵D(1);又用同样地公式由D(1)构造出D(2);……;最后又用同样的公式由D(n-1)构造出矩阵D(n)。矩阵D(n)的i行j列元素便是i号顶点到j号顶点的最短路径长度,称D(n)为图的距离矩阵,同时还可引入一个后继节点矩阵path来记录两点间的最短路径。

状态转移方程

map[i,j]:=min{map[i,k]+map[k,j],map[i,j]};

        map[i,j]表示i到j的最短距离,K是穷举i,j的断点,map[n,n]初值应该为0,或者按照题目意思来做。

        当然,如果这条路没有通的话,还必须特殊处理,比如没有map[i,k]这条路。

过程

  1. 从任意一条单边路径开始。所有两点之间的距离是边的权,如果两点之间没有边相连,则权为无穷大。
  2. 对于每一对顶点 u 和 v,看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比已知的路径更短。如果是更新它。

三、优缺点及时间空间复杂度 

优点:简单。

缺点:时间复杂度比较高。

时间复杂度:O(n^3)

空间复杂度:O(n^2)

四、参考代码 

声明:以下内容来自Floyd算法_百度百科

#include
#include
using namespace std;
const int &INF=100000000;
void floyd(vector > &distmap,//可被更新的邻接矩阵,更新后不能确定原有边vector > &path)//路径上到达该点的中转点
//福利:这个函数没有用除INF外的任何全局量,可以直接复制!
{const int &NODE=distmap.size();//用邻接矩阵的大小传递顶点个数,减少参数传递path.assign(NODE,vector(NODE,-1));//初始化路径数组 for(int k=1; k!=NODE; ++k)//对于每一个中转点for(int i=0; i!=NODE; ++i)//枚举源点for(int j=0; j!=NODE; ++j)//枚举终点if(distmap[i][j]>distmap[i][k]+distmap[k][j])//不满足三角不等式{distmap[i][j]=distmap[i][k]+distmap[k][j];//更新path[i][j]=k;//记录路径}
}
void print(const int &beg,const int &end,const vector > &path)//传引用,避免拷贝,不占用内存空间//也可以用栈结构先进后出的特性来代替函数递归 
{if(path[beg][end]>=0){print(beg,path[beg][end],path);print(path[beg][end],end,path);}else cout<<"->"<>n_num>>e_num;vector > path,distmap(n_num,vector(n_num,INF));//默认初始化邻接矩阵for(int i=0,p,q; i!=e_num; ++i){cout<<"输入第"<>p>>q;cin>>distmap[p][q];}floyd(distmap,path);cout<<"计算完毕,可以开始查询,请输入出发点和终点:";cin>>beg>>end;cout<<"最短距离为"<

以上就是本文的全部内容啦!感谢阅读!

相关内容

热门资讯

蜻蜓订购APP贵金属订购非法期...   蜻蜓订购APP以"投资平台"名义对外宣传,主打贵金属期货(订购)交易。该平台一方面强调自身"正规...
悟空订购APP非法期货交易欺骗...   近期,有投资者反映,“悟空订购APP”等平台以白银、贵金属订购为名,宣传所谓“高收益”“低门槛”...
小赢淘金APP期货投资骗局,平...   “小赢淘金”之流,最擅长的就是用“注册送现金”、“充值返券”的糖衣炮弹来引流。别天真地以为那是福...
八方淘金APP非法期货交易欺骗...   警惕!八方生财、每日淘金、小赢淘金、悟空订购、蜻蜓订购、斗金订购等APP均涉嫌非法期货交易!  ...
智易购APP贵金属订购交易骗局...   很多人看到“3元起投”“充值送福利”“操作简单”“随时提现”这类宣传,很容易把智易购APP当成普...
喜玛银庄APP商品订购投资骗局...   喜玛银庄APP白银、铂金“现货订购”骗局警示:无资质平台涉嫌非法期货交易,投资者爆仓后如何维权?...
吉鑫乐享APP炒贵金属订购交易...   近期,多名投资者反映在“吉鑫乐享APP”进行贵金属投资时遭遇严重亏损,甚至血本无归。看似正规的“...
易掘金APP虚假期货投资骗局,...   “易掘金”的APP它打着“高收益、灵活投资”的旗号,宣称通过“商品订购”就能轻松赚钱,吸引了不少...
在大吉订购APP订购交易亏损被...   近期,不少投资者反映在“大吉订购App”上投资白银、铂金等商品遭遇严重亏损。该平台宣称提供现货订...
铂银壹号APP商品订购交易亏损...   许多中小投资者误以为网上的“商品现货订购”是合规合法的理财渠道,殊不知这背后隐藏着巨大的合规风险...
兴鑫淘金APP贵金属订购交易亏...   白银、贵金属或其他商品类投资,除国家批准的正规期货交易场所及持牌期货公司外,市面上大量第三方交易...
铂银掘金APP无资质的违规平台...   铂银掘金等平台的投资者,往往是被“注册送现金”“充值返现券”“首单免亏”等广告话术吸引,进而下载...
八方淘金APP订购交易不合规,...   “八方淘金APP”“铂银掘金APP”“铂银壹号APP”等软件被指以“现货订购”为名,实际采用高杠...
在指尖订购APP订购商品亏损被...   指尖订购APP这类平台,表面是“订购交易”,实则是披着电商外衣的非法期货陷阱。绝大多数投资者被蒙...
在犀贝易购APP做商品订购交易...   市面上打着“现货投资”“贵金属交易”旗号的APP并不少,但真正合规、受监管的平台并不多。犀贝易购...
易达淘金APP虚假商品订购交易...   易达淘金APP存在严重的虚假宣传与违规交易行为。该平台打着“商品订购”的旗号,实则通过不合规的交...
大浪淘金APP白银订购亏损被骗...   大浪淘金APP最隐蔽的套路,在于其完全封闭的内盘交易系统。表面上,它宣称与国际贵金属市场接轨;实...
一品好购APP上订购白银出现亏...   一品好购APP原名“一品订购”,运营方为上海宝智未来信息技术有限公司。近期不少投资者反映在该平台...
九州订购APP贵金属订购投资骗...   九州订购APP正通过抖.音、快手、今日头条等平台大量投放投资广告,用“5元起投”“充值返现”“0...
坚锅淘金APP交易软件并不正规...   当前,市面上大量所谓的“现货商城订购”交易软件,早已偏离了正常的实物商品买卖,演变为高杠杆、高手...