任意两点最短路 Floyd-Warshall算法传递闭包

Floyd-Warshall算法是求解任意两点最短路的有力武器。其也适用于存在负边的情况。

DP思路，假定只使用前K个点时i到j的最短距离为d[k][i][j]
那末，使用前K+1个点就能够分成两种情况
①i到j的最短路用到了第K+1个点(d[k+1][i][j] = d[k][i][j])
②i到j的最短路没有用到第K+1个点(d[k+1][i][j] = d[k][i][k]+d[k][k][j]);
所以，d[k+1][i][j] = min(d[k][i][j],d[k][i][k]+d[k][k][j])

使用转动数组，就能够写成2维数组的情势
d[i][j] = min(d[i][j],d[i][k]+d[k][j])

Floyd算法可以在O(V^3)的时间内解出，判断图中是不是有负圈，只需要检查是不是存在d[i][i]是负数的顶点i就能够了。

代码

//d[i][j]表示i->j的权值，不存在时设为INF 但是d[i][i]设为0

for(int k = 0 ; k < V ; k ++) {

    for(int i = 0 ; i < V ; i ++) {

        for(int j = 0 ; j < V ; j ++) {

            d[i][j] = min(d[i][j],d[i][k]+d[k][j]);

        }

    }

}

由于实现起来非常简单，如果复杂度在可以承受的范围以内，单源最短路也能够使用Floyd-Warshall算法来进行求解。

在有向图中，如果需要判断每两个点是不是存在路径，那末也能够用Floyd算法来进行传递闭包。
只需要改成d[i][j] = d[i][j] || (d[i][k]&&d[k][j])便可(预处理也要变化)

算法

波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络，如有侵权请邮件联系站长！
2. 分享目的仅供大家学习和交流，您必须在下载后24小时内删除！
3. 不得使用于非法商业用途，不得违反国家法律。否则后果自负！
4. 本站提供的源码、模板、插件等等其他资源，都不包含技术服务请大家谅解！
5. 如有链接无法下载、失效或广告，请联系管理员处理！
6. 本站资源售价只是赞助，收取费用仅维持本站的日常运营所需！
7. 本站源码并不保证全部能正常使用，仅供有技术基础的人学习研究，请谨慎下载
8. 如遇到加密压缩包，请使用WINRAR解压,如遇到无法解压的请联系管理员！

波比源码 » 任意两点最短路 Floyd-Warshall算法传递闭包

分享到：

47 评论

波员 Pbsemt

2022年11月29日 at 下午2:39

levofloxacin uk levofloxacin 500mg pill
波员 Dimvfo

2022年12月8日 at 下午8:57

lamotrigine 50mg pills order retin without prescription order retin
波员 Zcggwy

2022年12月15日 at 下午10:56

accutane 40mg generic azithromycin tablet ivermectin over counter
波员 Pnfnsj

2022年12月18日 at 下午2:32

buy generic buspirone 5mg buspirone 5mg pill ditropan online
波员 Knpdau

2022年12月21日 at 上午12:00

buy prograf pill buy trandate 100mg without prescription order urso sale
波员 Bhbwbc

2022年12月23日 at 下午2:46

oral sertraline 50mg lexapro 10mg uk order viagra pills
波员 Fnxxhh

2022年12月30日 at 上午9:27

purchase azithromycin pill order prednisolone order neurontin 800mg online
波员 Lkwmfw

2022年12月31日 at 下午1:31

furosemide 40mg price buy lasix 40mg order plaquenil 400mg generic
波员 Ktwbzv

2023年1月2日 at 下午8:27

metformin drug glycomet 1000mg oral cialis medication
波员 Ytekgo

2023年1月7日 at 下午1:08

order metoprolol online levitra 20mg sale buy levitra 10mg for sale
波员 Rguwao

2023年1月9日 at 上午1:55

buy vardenafil sale purchase vardenafil methylprednisolone 8mg without prescription
波员 Kaomum

2023年1月11日 at 上午10:05

brand cialis 40mg tadalafil ca real viagra sites
波员 Wosrnk

2023年1月11日 at 下午1:47

aristocort 10mg us loratadine 10mg uk desloratadine 5mg over the counter
波员 Pzoqug

2023年1月15日 at 上午5:15

order zyloprim pill zetia 10mg pills zetia drug
波员 Qiensf

2023年1月15日 at 下午7:08

methotrexate 2.5mg oral methotrexate price metoclopramide without prescription
波员 Vtasap

2023年1月17日 at 下午2:19

order baclofen 25mg online cheap tizanidine cheap buy ketorolac
波员 Qctdpl

2023年1月20日 at 下午2:09

tamsulosin cost flomax cost order aldactone 25mg sale
波员 Eglfwn

2023年1月25日 at 上午2:57

viagra order online buy sildenafil 100mg generic cialis 10mg uk
波员 Dzwnrl

2023年1月29日 at 上午10:58

buy deltasone 40mg pills order amoxicillin 500mg online cheap amoxil 1000mg for sale
波员 Ypcnib

2023年1月29日 at 下午5:25

cheap viagra pill viagra 100 mg purchase cialis without prescription
波员 Iptnxi

2023年2月1日 at 下午5:47

buy lasix pill order generic doxycycline 100mg order hydroxychloroquine generic
波员 Friihc

2023年2月7日 at 下午4:53

purchase lamisil without prescription cheap terbinafine 250mg trimox 500mg ca
波员 Xmvpuw

2023年2月8日 at 下午10:52

buy naprosyn 250mg generic buy prevacid 15mg generic buy lansoprazole without prescription
波员 Mhcver

2023年2月13日 at 下午6:55

cheap cialis sale best over the counter ed pills tadalafil brand name
波员 Qvcpqz

2023年2月17日 at 上午10:03

gambling games real online blackjack online blackjack gambling
波员 Jmhrit

2023年2月23日 at 下午5:50

clobetasol cream clobetasol medication buy amiodarone 100mg for sale
波员 Auivuv

2023年2月23日 at 下午6:07

olmesartan 10mg us divalproex 250mg usa order divalproex 250mg pill
波员 Zizhcm

2023年2月24日 at 上午4:57

generic acetazolamide 250 mg order azathioprine 50mg generic imuran 25mg pill
波员 Ikpitn

2023年2月25日 at 下午4:03

cost lanoxin generic telmisartan order molnupiravir without prescription
波员 Vcjpdn

2023年2月28日 at 上午12:07

buy carvedilol 25mg without prescription buy elavil 10mg sale buy elavil 10mg generic
波员 Xkwpnh

2023年2月28日 at 上午8:18

order amoxicillin generic purchase stromectol online cheap ivermectin 0.5%
波员 Ojoyjp

2023年3月1日 at 下午10:16

order dapoxetine 90mg without prescription dapoxetine pills buy domperidone 10mg generic
波员 Ygfely

2023年3月3日 at 上午12:10

order pamelor 25 mg online cheap order paroxetine 10mg paroxetine 10mg uk
波员 Yjugwb

2023年3月3日 at 上午10:18

cheap indocin 50mg buy indocin without prescription cenforce 100mg for sale
波员 Nvqepf

2023年3月5日 at 上午12:01

buy doxycycline 200mg online methylprednisolone cost methylprednisolone cost in usa
波员 Vjfhaz

2023年3月6日 at 下午12:17

brand tadalafil 20mg amoxicillin 250mg tablet purchase amoxicillin pills
波员 Jyvper

2023年3月8日 at 下午2:24

nexium 20mg for sale clarithromycin pills buy lasix 40mg online cheap
波员 Wlopsw

2023年3月9日 at 上午2:11

buy cialis 40mg pills Cialis delivery sildenafil 100mg pills
波员 Pvmetg

2023年3月10日 at 上午2:20

minocycline medication neurontin 800mg canada buy terazosin 1mg generic
波员 Iifecn

2023年3月11日 at 下午11:35

glucophage 500mg drug verapamil 120mg over the counter nolvadex sale
波员 Nspgyq

2023年3月12日 at 下午12:11

order provigil 200mg online cheap promethazine medication phenergan ca
波员 Myofpq

2023年3月13日 at 下午9:05

clomid 50mg us order clomid 100mg for sale order generic prednisolone 10mg
波员 Mzeawc

2023年3月14日 at 上午6:32

buy deltasone 10mg online cheap buy accutane 40mg pills cost amoxicillin 1000mg
波员 Kzczeo

2023年3月15日 at 下午6:00

buy accutane online cheap acillin order ampicillin 500mg sale
波员 Zqtmta

2023年3月16日 at 上午3:42

fildena 50mg price cheapest ed pills online propecia 5mg uk
波员 Njdavu

2023年3月17日 at 下午4:21

ivermectin tablets uk prednisone order online buy deltasone 5mg generic
波员 Fwtqnx

2023年3月20日 at 上午3:33

purchase albuterol inhaler levothroid ca clavulanate price