Floyd-Warshall算法（求解任意两点间的最短路） 详解 + 变形 之 poj 2253 Frogger

/* 好久没有做有关图论的题了，复习一下。 --------------------------------------------------------- 任意两点间的最短路（Floyd-Warshall算法） 动态规划: dp[k][i][j] := 节点i可以通过编号1,2...k的节点到达j节点的最短路径。 使用1,2...k的节点，可以分为以下两种情况来讨论： （1）i到j的最短路正好经过节点k一次 dp[k-1][i][k] + dp[k-1][k][j] （2）i到j的最短路完全不经过节点k dp[k-1][i][j] 故：dp[k][i][j] = min(dp[k-1][i][k] + dp[k-1][k][j], dp[k-1][i][j]) 空间可优化：dp[i][j] = min(dp[i][k] + dp[k][j], dp[i][j]) 初始值： dp[0][i][j] = 0 (i == j) dp[0][i][j] ：= 边i->j的权值 如果i和j之间不存在边，dp[i][j] = INF (0x3f3f3f3f) 时间复杂度：O(|V|^3) 可以处理边是负数的情况，判断图中是否有负圈，只需检查是否存在dp[i][i]是负数的顶点i就可以了。 --------------------------------------------------------------------------------- poj 2253 Frogger 对于此题，求的是： To execute a given sequence of jumps, a frog's jump range obviously must be at least  as long as the longest jump occuring in the sequence. The frog distance (humans also call it minimax distance) between two stones therefore is defined as the minimum necessary jump range over all possible paths between the two stones.  即：/* 好久没有做有关图论的题了，复习一下。 -------------------------