各顶点之间的最短路径- Floyd算法
利用的是动态规划的思想
代码实现：
//....准备工作，根据图的信息初始化矩阵A和path(如上图) for(int k=0;k<n;k++){ for(int i=0;i<n;i++){ for(int j=0;j<nj++){ if(A[i][j]>A[i][k]+A[k][j]){ A[i][j]=A[i][k]+A[k][j]; path[i][j]=k; } } } }
看一个难一点的例子：
最终得到：
如何寻找路径：
上面有说过D算法解决不了含有负数权的图，但是呢，Floyd 是可以的
总结三种算法
6.4.3有向无环图
有向无环图：若一个有向图中不存在环，则称为有向无环图，简称DAG图。
如下图
如下图右，有环路不能称为有向无环图。
描述表达式（有向无环图的第一个应用）
刚才讲解了什么？关于有向无环图如何描述表达式。他们之间的转化
首先是如何通过表达式转化为（有向无环）图。
方法：
step1:把各个操作数不重复的排成一排。
step2:标出各个运算符的生效顺序（先后顺序有点出入无所谓）
step3:按顺序加入运算符，注意分层。
step4:从底向上逐层检查同层的运算符时候可以合体。
举个例子：
把上图转化为有向无环图：（不会看-图章节视频12）
答案如下：
咱们看下一题:
本题按照这个顺序去实现上述操作方法。再按照下述顺序操作一遍。
得到的结果是什么————自己操作，不会看视频。
得到结果如下：
你会发现同一个表达式，按照不同的顺序排序，得到的结果是不唯一的。
所以得出结论：
同一个表达式，可以用不同的图去表示
6.4.4 拓扑排序（有向无环图的第二个应用）
AOV网
AOV网使用DAG图表示一个工程。注意A是表示一个活动。也就是顶点表示活动，有向边<Vi,Vj>表示活动Vi进行必须先于Vj进行。如果出现了环路就一定不是AOV网。看如下不是一个AOV网，去掉红色箭头就属于一个AOV网；
拓扑排序实现
定义：在图中，有一个有向无环图的顶点组成的序列。当且仅当满足下列条件时候称之为该图的一个拓扑排序。
1.每个顶点出现且出现一次。
2.若顶点A在排序中排在顶点B的前面，则在图中不存在从顶点B到顶点A的路径。
或者定义为：拓扑排序是对有向无环图的顶点的一种排序，它使得若存在一条从顶点A到顶点B的路径，则在排序中顶点B出现在顶点A的后面。每个AOV图都有一个或者多个拓扑排序序列。
以上是官方定义：也就是说拓扑排序就是排序而已。而且他是只能有向无环图，从前指向后的排序。排序结果可能有多种。
实现：
1.从AOV网中选择一个没有前驱（入度为0）的顶点输出。
2.从网中删除该顶点和所有以他为顶点的有向边。
重复1，2直到AOV为空为止，或者网中不存在无前驱的顶点（说明没有回路）。
那咱们看看对上述工程进行排序：下图是按照顺序从前往后的一种顺序（过程不会看视频图13）
如果图中存在回路怎么办，那么就拓扑排序不下去了，如下图
代码实现:
对于如下一个图，左边是图的结构，右边是图的储存结构。如何用代码实现如下的排序呢？
首先你需定义一个数组indegree[]表示当前各个顶点的度。定义一个输出后的排序数组print[]来记录拓扑排序。再用一个栈或者队列来按一定顺序保存和弹出相关活动获得顺序。
如下：
代码实现
bool topologicalsort(Graph G){//定义了一个bool型号的函数，看返回值返回1就是排序成功 initstack(S); for(int i=0;i<G.vexnum;i++) if(indegree[i]==0) push(S,i); push(S,i); int count=0;//其实count表示print[]的数组序号 while(！IsEmpty(S)){ Pop(S,i); print[count++]=i; for(p=G.vertices[i].firstarc;p=p->nextarc){//复杂在他是一个邻接表的储存结构没有弄懂。作用是i指向的顶点入度减一，并且将入读为01的顶点压入栈。 v=p->adjvex; if(!(--indegree[v])) push(S,v); } } if(count<G.vexnum) return false; else return ture; }
关于时间复杂度：上述使用了邻接表，几乎每一个点和边都需要遍历一遍。故邻接表的时间复杂度如下，而矩阵存储不一样。每个点都要遍历。
逆拓扑排序
选一个出度为0的顶点输出。其他和上述三步法一模一样，我就不重复了。
对于上面的工程用，逆排序结果也不是唯一的。有回路也不能排序成功。下面是其中一种顺序排法。
关于代码：
题目：用逆拓扑排序解决下图：左边是图，右边是储存结构
代码如下：
思考：
如果使用逆邻接表（每个顶点后面链接的是入边，如上图的逆邻接表如下）邻接矩阵对时间复杂度的影响如何？
用DFS算法实现（逆）拓扑排序
思考：
1.如果存在环路…
2.用DFS实现拓扑排序
6.4.5关键路径
１、ＡＯＶ：有向图中，用顶点表示事件，用有向边表示活动之间开始的先后顺序，则称这种有向图为AOV（Activity On Vertex）网络；AOV网络可以反应任务完成的先后顺序（拓扑排序）。
２、AOE:在实际应用中，活动除了先后关系外，还需考虑时间上的约束
在一个表示工程的带权有向图中，用顶点表示事件，用有向边表示活动，边上的权值表示活动的持续时间，称这样的有向图叫做边表示活动的网，简称AOE网
如图：
３、AOE网中只有一个入读为零的顶点称为始点（或源点），只有一个出度为零的顶点称为终点（或汇点）。
４、性质：
⑴ 只有在某顶点所代表的事件发生后，从该顶点出发的各活动才能开始；
⑵ 只有在进入某顶点的各活动都结束，该顶点所代表的事件才能发生。
５、完成一个工程所需要的最短时间是从源点到汇点的最长路径长度
关键路径：具有最长长度的路径，这里的路径长度是路径上的各权值之和
注意：关键路径不一定只有一条。
关键活动：关键路径上的活动称为关键活动。（需要满足 ee [i]=el [i] ）
！！ 关键路径的长度是整个工程所需要的最短工期，要缩短整个工期，必须要加快关键活动的进度
二、求关键活动所需要的参量
⑴ 事件的最早发生时间ve[k] － 从前往后，前驱结点到当前结点所需时间，取最大值。
ve[k]是指从始点开始到顶点vk的最大路径长度。这个长度决定了 所有从顶点vk发出的活动能够开工的最早时间。
⑵ 事件的最迟发生时间 vl[k] － 从后往前，后继结点的最迟发生时间-边权值，取最小值。
vl[k]是指在不推迟整个工期的前提下, 事件vk允许的最晚发生时间。
⑶ 活动的最早开始时间e [i]
若活动ai是由弧<vk , vj> 表示，则活动 ai的最早开始时间应等于事件vk的最早发生时间。
因此，有：e[i]=ve[k]
⑷ 活动的最晚开始时间 l [i]
活动ai的 最晚开始时间是指，在不推迟整个工期的前提下， ai 必须开始的最晚时间。若ai由弧<vk，vj>表示，则ai的最晚开始时间要保证事件 vj 的最迟发生时间不拖后。
一般等于l(i)=vl(j)-weight(vk,vj)
时间余量：当时间余量为0时候，说明这是一个关键活动。
求解路径的步骤：
举个例子：
上面是求解路径的的方法：那咱们看一道题目来操作一哈，如下
第一步：
第二步：
第三步：
第四步：
第五步：
==》找到关键路径
1 若关键活动的耗时增加，则整个工程的工期将加长；
2 缩短 关键活动的时间，可以缩短整个工程的工期
3.当缩短到一定程度时候，关键活动可能变成非关键活动
4 可能有多条关键路径，只提高一条关键路径的关键活动速度并不能缩短整个工程的工期，只有加快那些在所有关键路径上的关键活动才能达到缩短工期的目的
