本文共 2456 字，大约阅读时间需要 8 分钟。

因为刚开始想着，既然在图中表示，就要用到图的存储结构等等吧，所以 ?

首先，要复习一下图的相关知识（学完数据结构后过了不长的时间，已经还给老师了?）

1、图的存储结构：

       邻接矩阵表示法 和 邻接表表示法(详见 )。

2、图的基本算法：

       计算图的顶点数量，计算图的边数量，返回第i个顶点的值，插入一个顶点，删除一个顶点，插入一条边，删除一条边，深度优先遍历图，广度优先遍历图。

       拓扑排序

接着，来看下面这道多段图中的最短路径问题（The shortest path in multistage graphs）：

问题描述：

       建立一个从源点S到终点T的多段图，设计一个动态规划算法求出从S到T的最短路径值，并输出相应的最短路径。 

解决思路（老师讲课）：

       首先，暴力法是遍历从 S 到 T 的所有路径，依次比较。

       但我们可以使用更优的方法 —— 动态规划。

       很容易看出，这是一个多阶段决策的问题，S —— A、B、C —— D、E、F —— T 分别是四个阶段，如下图所示：

       按照 自底向上(bottom-up) 的方法，d(S, T) = min{ 1 + d(A, T), 2 + d(B, T), 5 + d(C, T) }；这满足 动态规划 的 最优子结构 的性质，即，问题的最优解包含其子问题的最优解。

算法实现（老师讲课）：

/*伪代码*/d[1] = 0for j = 2 to n:    for all 
   
     ∈E :        d[j] = min{ d[i] + w [i,j] }return d[n]
   

有向无环图中的最短路径问题（The shortest path in dags）：

问题描述：

       建立一个从源点S到终点E的有向无环图，设计一个动态规划算法求出从S到E的最短路径值，并输出相应的最短路径。

解决思路（老师讲课）：

       有向无环图不像多段图，有明确的分阶段，它能转换成多段图进行求解吗？

       也可以，因为，有向无环图 可以通过 拓扑排序 将其转换为 线性结构。

       Notice that, the special distinguishing feature of a dag is that its nodes can be linearized; that is, they can be arranged on a line so that all edges go from left to right. 如下图所示：

        （回到了这篇文章开头的地方）。

算法实现：

       从图中可以看出：

/*伪代码*/initialize all dist(.) values to    dist(s) = 0for each v V\{s}, in linearized order;    dist(v)=min {dist(u) + (u,v)}

       所以我本来想着要用着邻接表啊一些数据结构的知识，便复习了一番，最终代码太繁琐，在deadline之前调不完了……

……so，先暂空着……

However，

       在网上查找相关代码的时候，发现了如下的代码，自己又改了一部分：

#include 
   
    #include 
    
     using namespace std;int main(){	cout << "请输入图的顶点数目：" << endl;	int vexnum;	cin >> vexnum;	vector
     
       cost(vexnum, 0);			//cost[i]表示从顶点i到终点n-1的最短路径长度	vector
      
        path(vexnum, 0);			//path[i]表示从顶点i到终点n-1的路径上顶点i的下一个顶点	cout << "请输入图的边数：" << endl;	int edgenum;	cin >> edgenum;	vector
       
        
         > edge(vexnum, vector
         
          (vexnum, 0)); //edge[i][j]存储多段图中的边 cout << "请依次输入图中各边的起点终点和路径长度：" << endl; int start; int end; int length; for (int i = 0; i < edgenum; ++i) { cin >> start >> end >> length; edge[start][end] = length; } for (int i = vexnum-2; i >= 0; --i) { cost[i] = INT_MAX; for (int j = i; j < vexnum; ++j) { if (edge[i][j] != 0) { //等于零表示之间没有路 if (edge[i][j] + cost[j] < cost[i]) { //此时找到一条更短的路 path[i] = j; //更新path[i] cost[i] = edge[i][j] + cost[j]; //更新从该节点出发的最短路径 } } } } cout << "最短路径长度是：" << cost[0] << endl; cout << "最短路径为：" << endl; int i = 0; cout << "0 ---> "; while (1) { cout << path[i]; i = path[i]; if (i == vexnum-1) { break; } cout << " ---> "; } cout << endl; return 0;}
         
        
       
      
     
    
   

       其实，这种代码，适用于上述两种最短路径的情况，只要确定了各顶点的序号，输入就OK啦！

转载地址：http://pttai.baihongyu.com/