利用动态规划方法求解每对结点之间的最短路径问题（all pairs shortest

问题单项选择题

利用动态规划方法求解每对结点之间的最短路径问题（all pairs shortest path problem）时，设有向图G=共有n个结点，结点编号1～n，设C是G的成本邻接矩阵，用D^k（i，j）即为图G中结点i到j并且不经过编号比k还大的结点的最短路径的长度（Dⁿ（i，j）即为图G中结点i到j的最短路径长度），则求解该问题的递推关系式为（）。

A．D^k(i，j)；D^k-1(i，j)+C(i，j)

B．D^k(i，j)：minD^k-1(i，j),D^k-1(i，j)+C(i，j)

C．D^k(i，j)：D^k-1(i，k)+D^k-1(i，j)

D．D^k(i，j)；minD^k-1(i，j),D^k-1(i，k)+D^k-1(k，j)

答案

参考答案：D

解析：

[分析]

设P^k(i，j)表示从i到j并且不经过编号比k还大的结点的最短路径，那么P^k(i，j)有以下两种可能：

①P^k(i，j)经过编号为k的结点，此时P^k(i，j)可以分为从i到k和从k到j的两段，易知产P^k(i，j)的长度为D^k-1(i，k)+D^k-1(k，j)。

②P^k(i，j)不经过编号为k的结点，此时产P^k(i，j)的长度为D^k-1(i，j)。