原文链接：http://www.tbk.ren/article/69.html

动态规划（dynamic programming）是运筹学的一个分支，是求解决策过程（decision process）最优化的数学方法。

最短距离的 Floyd-Warshall算法，就是一个动态规划的算法：

将顶点编号，假设依次为0,1,2…n-1,现在假设DP[i][j][k]表示从i出发，结束于j的满足经过结点的编号至多为k的最短路径，由此性质易知，在易知DP[i][j][k]时，若要求DP[i][j][k+1]，有两种情况要考虑：

1、DP[i][j][k+1]所表征的路径经过结点k+1，此时DP[i][j][k+1] = DP[i][k+1][k] + DP[k+1][j][k]

2、DP[i][j][k+1]所表征的路径不经过结点k+1,此时DP[i][j][k+1] = DP[i][j][k]，不用更新表项

属于哪种情况只需进行一次比较选择较小的即可，当第n-1轮循环结束，表项中的值DP[i][j]就代表了顶点i , j之间的最短距离，由算法的描述易知，时间复杂度必然是O(N3),但是空间复杂度可以通过复用DP数组减少到O(N2)。

下面是Floyd-Warshall算法的伪代码实现：

require(igraph)

gData = data.frame(

  p1 = c(

    'A' , 'A' , 

    'B1', 'B1', 'B1', 'B2', 'B2', 'B2', 

    'C1', 'C1', 'C2', 'C2', 'C3', 'C3', 'C4', 'C4', 

    'D1', 'D1', 'D2', 'D2', 'D3', 'D3', 

    'E1', 'E1', 'E2', 'E2', 'E3', 'E3', 

    'F1', 'F2'

  ),

  p2 = c(

    'B1', 'B2', 

    'C1', 'C2', 'C3', 'C2', 'C3', 'C4', 

    'D1', 'D2', 'D1', 'D2', 'D2', 'D3', 'D2', 'D3', 

    'E1', 'E2', 'E2', 'E3', 'E2', 'E3', 

    'F1', 'F2', 'F1', 'F2', 'F1', 'F2', 

    'G' , 'G'

  ),

  weight = c(

    5, 3, 

    1, 3, 6, 8, 7, 6,  

    6, 8, 3, 5, 3, 3, 8, 4,  

    2, 2, 1, 2, 3, 3,  

    3, 5, 5, 2, 6, 6,  

    4, 3

  )

);

g = graph.data.frame(gData, directed = TRUE)

plot(

  g, 

  edge.width = E(g)$weight, 

  edge.label = E(g)$weight, 

  layout=layout.fruchterman.reingold

)

AGShortest <- get.shortest.paths(g, 'A', 'G')$vpath[[1]]

V(g)[AGShortest]$color <- 'green'

E(g)$color <- 'grey'

E(g, path=AGShortest)$color <- 'red'

E(g, path=AGShortest)$width <- 3

plot(

  g, 

  edge.width = E(g)$weight, 

  edge.label = E(g)$weight, 

  layout=layout.fruchterman.reingold

)

R得到的图形结果：

http://s8/mw690/002pzk91gy6H9J5ZEdF77&690