百度空间 | 百度首页 
 
查看文章
 
DP归纳(改写自OIBH)全点对最短路径问题(APSP)
2008年11月11日 星期二 下午 04:02

全点对最短路径问题(All-Pairs Shortest Paths),即寻找从任意点p到任意其他点q的最短路径,与单源最短路径不同,它计算的是集合中任意两个点对的最短路径,所以复杂度是N^3的

方程模型

F[I,J]=MIN( F[I,K]+F[K,J],F[I,J] ),初值F[I,J]=∞,F[I,J]=G[I,J](如果I,J两点读入时有直连的话)

I<>J<>K

注意K应放在最外重循环

如果F[I,J]用布尔型的话可以判断两者是否连通


类别:dp归纳 | 浏览() | 评论 (0)
 
最近读者:
 
网友评论:
发表评论:
姓 名:
网址或邮箱: (选填)
内 容:
验证码: 请点击后输入四位验证码,字母不区分大小写
      

     

©2009 Baidu