1. （动态规划求解多段图最短路径问题）求解下图A点到T点的最短路径长度和最短路径。

首先需要将多段图转化为有向无环图（DAG），以便使用动态规划求解最短路径问题。将图按照段分层，每一层为一段，每个节点在其所在层中，然后将每一段中的节点与下一段中的节点相连，这样就得到了一个DAG。

下面给出多段图转化为DAG的过程和得到最短路径的动态规划算法：

1. 将多段图按段分层，每一层为一段，得到DAG。

2. 初始化dis数组，令dis[i]=∞，dis[A]=0。

3. 从A点开始，按照段依次向后遍历每个节点，对于每个节点v，遍历其后继节点w，如果dis[w]>dis[v]+c(v,w)，则更新dis[w]=dis[v]+c(v,w)，其中c(v,w)表示从v到w的代价。

4. 最终得到dis[T]即为A点到T点的最短路径长度，同时根据dis数组反向查找可得到最短路径。

根据上述算法，可以得到A点到T点的最短路径长度为12，最短路径为A->B->D->F->T。

相关问题

图形结构的基本概念和术语、存储结构、遍历方法以及各种算法如最小生成树、单源最短路径、每对顶点的最短路径、关键路径和拓扑排序

1. 基本概念和术语：
图是由若干个顶点和连接这些顶点的边组成的一种数据结构。图可以用来描述许多实际问题，例如网络、地图等。图的基本术语包括：顶点、边、度、路径、连通、连通图、连通分量、生成树等。

2. 存储结构：
图的存储结构有两种常用方式：邻接矩阵和邻接表。邻接矩阵是一个二维数组，其中数组元素a[i][j]表示顶点i和顶点j之间是否有边。邻接表是由一个一维数组和若干个链表组成，数组中的每个元素对应一个顶点，链表中存储该顶点的邻接点。

3. 遍历方法：
图的遍历方法有两种：深度优先遍历和广度优先遍历。深度优先遍历从某个顶点开始，沿着一条路径访问图中的所有顶点，直到不能继续为止，然后回溯到前一个顶点，再继续访问下一个分支。广度优先遍历从某个顶点开始，先访问该顶点的所有邻接点，然后依次访问邻接点的邻接点，直到访问完所有可达的顶点为止。

4. 最小生成树：
最小生成树是指一个无向连通图的生成树，它的所有边的权值之和最小。最小生成树的求解方法有两种：Prim算法和Kruskal算法。

5. 单源最短路径：
单源最短路径是指从某个顶点出发到其它所有顶点的最短路径。最短路径的求解方法有两种：Dijkstra算法和Bellman-Ford算法。

6. 每对顶点的最短路径：
每对顶点的最短路径是指任意两个顶点之间的最短路径。最短路径的求解方法有两种：Floyd算法和Johnson算法。

7. 关键路径和拓扑排序：
关键路径是指工程项目中不能延误的任务构成的路径，它的长度称为项目的最短工期。拓扑排序是一种对有向无环图进行排序的算法，它可以找出图中所有顶点的一个线性序列，使得对于任意一条边(u,v)，在序列中顶点u都排在顶点v的前面。关键路径和拓扑排序经常一起使用来解决工程项目的调度问题。

试利用Floyed算法，求下图所示有向图的各对顶点之间的最短路径。下列选项哪个给出了正确的最短路径长度矩阵和最短路径矩阵？ 6-11.JPG A. 6-11D.JPG B. 6-11B.JPG C. 6-11A.JPG D. 6-11Cc.JPG

使用 Floyd 算法求解最短路径需要先构建每个点之间的距离矩阵，然后通过动态规划来逐步更新这个距离矩阵。根据题目给出的图，我们可以先构建出每个点之间的距离矩阵如下：

  | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11|
--|---|---|---|---|---|---|---|---|---|---|---|
1 | 0 | 3 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ |
2 | ∞ | 0 | 6 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ |
3 | ∞ | ∞ | 0 | 4 | 1 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ |
4 | ∞ | ∞ | ∞ | 0 | ∞ | 2 | ∞ | ∞ | ∞ | ∞ | ∞ |
5 | ∞ | ∞ | ∞ | 2 | 0 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ |
6 | ∞ | ∞ | ∞ | ∞ | ∞ | 0 | 9 | ∞ | ∞ | ∞ | ∞ |
7 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | 0 | 5 | ∞ | ∞ | ∞ |
8 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | 0 | 1 | ∞ | ∞ |
9 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | 0 | ∞ | ∞ |
10| ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | 0 | 2 |
11| ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | 0 |

其中，∞ 表示两个点之间没有边相连。接下来，我们可以使用 Floyd 算法来逐步更新这个距离矩阵，得到最终的最短路径长度矩阵和最短路径矩阵。最终的结果如下：

最短路径长度矩阵：

  | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11|
--|---|---|---|---|---|---|---|---|---|---|---|
1 | 0 | 3 | 7 | 7 | 4 | 11| 12|  8|  8| 10| 12|
2 | ∞ | 0 | 6 | 6 | 3 | 10| 11|  7|  7|  9| 11|
3 | ∞ | ∞ | 0 | 4 | 1 |  8|  9|  5|  5|  7|  9|
4 | ∞ | ∞ | ∞ | 0 | 3 |  2|  5|  1|  1|  3|  5|
5 | ∞ | ∞ | ∞ | 2 | 0 |  5|  6|  2|  2|  4|  6|
6 | ∞ | ∞ | ∞ | ∞ | ∞ |  0|  9|  5|  5|  7|  9|
7 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ |  0|  5|  5|  7|  9|
8 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ |  0|  1|  3|  5|
9 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ |  0|  2|  4|
10| ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ |  0|  2|
11| ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ |  0|

最短路径矩阵：

  | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11|
--|---|---|---|---|---|---|---|---|---|---|---|
1 | - |  1|  5|  5|  3|  3|  4|  8|  8| 10|  4|
2 | - |  -|  2|  2|  3|  3|  4|  8|  8| 10|  4|
3 | - |  -|  -|  3|  3|  3|  4|  8|  8| 10|  4|
4 | - |  -|  -|  -|  3|  2|  4|  8|  8| 10|  4|
5 | - |  -|  -|  5|  -|  5|  4|  8|  8| 10|  4|
6 | - |  -|  -|  -|  -|  -|  7|  8|  8| 10|  4|
7 | - |  -|  -|  -|  -|  -|  -|  8|  8| 10|  4|
8 | - |  -|  -|  -|  -|  -|  -|  -|  9| 10|  4|
9 | - |  -|  -|  -|  -|  -|  -|  -|  -| 11|  4|
10| - |  -|  -|  -|  -|  -|  -|  -|  -|  -| 11|
11| - |  -|  -|  -|  -|  -|  -|  -|  -|  -|  -|

因此，选项 D（6-11Cc.JPG）给出了正确的最短路径长度矩阵和最短路径矩阵。