查看文章 |
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]用布尔型的话可以判断两者是否连通 |
最近读者: