相关代码地址:
一、什么是AOE网
AOE( on edge ) :在一个表示工程的带权有向图中,用顶点表示事件 , 用有向边表示活动,边上的权值表示活动的持续时间,称这样的有向图叫做边表示活动的网,简称AOE网
【07.AOE网和图的关键路径】AOE网中没有入边的顶点称为始点(或源点);没有出边的点称为终点(或汇点)
二、AOE网的性质 只有再某顶点所代表的事件发生后,从该顶点出发的活动才能开始;只有再进入某顶点的各活动都结束,该顶点所代表的事件才能发生 。三、AOE网可以解决下列问题 完成整个工程至少需要多少时间为缩短完成工程所需要的时间 , 应当加快哪些活动 四、关键活动 1.关键路径
从开始到结束最长的一条路径,可能不只一条,那么如何找到这样条路径呢?这就需要,找本节的重要概念关键活动 (全部由关键活动组成的路径 , 就是关键路径)
2.关键活动
(1)如果缩短某一条活动的时间,不能改变总体结束时间 , 活动就不是关键活动 。
(2)如果缩短某条活动的时间,能减少总体结束时间,活动就是关键活动 。
(3)活动的最早发生时间,和最迟发生时间一样,活动,就是关键活动 。
五、求关键活动
上文说到,活动的最早发生时间,和最迟发生时间一样 , 活动 , 就是关键活动 。
这两个时间怎么求呢?下面将给出答案 。
1.关键活动的4个前导量
(1)事件A的最早发生时间[B] :[B] = max{[]+len}
(2)事件A的最迟发生时间[B]:[B] = min{[]-len}
![07.AOE网和图的关键路径](http://img.gansulong.com/231230/03413IF8-0.jpg)
文章插图
(3)活动AB 的最早发生时间:[BC] = [B]
(4)活动AB 的最迟发生时间: [CD] = [D] - len[CD]
注:len表示 弧AB的长度
(1) 分析
event : A B C D E F G H I
: 0 6 4 5 7 7 16 14 18
从起点开始算,起点时间一定是0之后的事件用前一个事件的时间推算如: [B] = max{[A]+len}[E] = max{[B]+len ,[C]+len}(2)分析,依赖
event : A B C D E F G H I
: 0 6 4 5 7 7 16 14 18
: 0 6 6 8 7 10 16 14 18
从后往前计算,结束事件直接取用前一个事件的时间推算如:[B] = min{[C]-len}开始时间,必定是0 (3) 分析
活动BC 的最早开始时间应该等于 时间B的最早开始时间因此有:[BC] = [B]
event: A BC DEFGHIevent_early : 0 64 57716 14 18event_latest: 0 668 7 10 16 14 18activity: ABACADBECEDFEGEHFHGIHIactivity_early : 0006457771614
(4) 分析
要从前往后算
例如活动CD 的最晚开始时间要保证时间D的最迟时间不能拖后所有:[CD] = [D] - len[CD]
event: A B C D EFGHIevent_early : 0 64 57716 14 18event_latest: 0 668 7 10 16 14 18activity: ABACADBECEDFEGEHFHGIHIactivity_early : 0006457771614activity_latest: 023668711101614
2.关键活动:
最早开始时间和最晚开始时间是一样的称为关键活动 。
activity: (AB)ACAD(BE)CEDF (EG) (EH)FH(GI)(HI)activity_early : 0006457771614activity_latest: 02366877101614
注意:
关键活动组成的路径叫关键路径虽然会产生多条关键路径 , 但是多条关键路径的执行时间是一样的 。工程的总执行时间就是任意选其中一条关键路径的总执行时间 。六、动画演示
七、代码实现
aoe.go
package aoeimport ("fmt""gitee.com/gudongkun/datestruct/dataStructures/graph""gitee.com/gudongkun/datestruct/dataStructures/linear")func GetGraph() graph.DMGraph {g := graph.NewDMGraph()g.AddNode("A")g.AddNode("B")g.AddNode("C")g.AddNode("D")g.AddNode("E")g.AddNode("F")g.AddNode("G")g.AddNode("H")g.AddNode("I")g.AddEdge("A", "B", 6)g.AddEdge("A", "C", 4)g.AddEdge("A", "D", 5)g.AddEdge("B", "E", 1)g.AddEdge("C", "E", 1)g.AddEdge("E", "G", 9)g.AddEdge("E", "H", 7)g.AddEdge("G", "I", 2)g.AddEdge("H", "I", 4)g.AddEdge("D", "F", 2)g.AddEdge("F", "H", 4)return g}func AOEKeyEvents() []string {g := GetGraph()eventEarly := make(map[string]int)eventLatest := make(map[string]int)activeEarly := make(map[string]int)activeLatest := make(map[string]int)// 1. 求eventEarlyindegrees := make(map[string]int)stack := linear.NewStack()for _, v := range g.Nodes {indegrees[v] = g.GetIndegree(v)if indegrees[v] == 0 {stack.Push(v)indegrees[v] = -1eventEarly[v] = 0}}for !stack.IsEmpty() {v, _ := stack.Pop()for _, edge := range g.GetEdgesByHead(v) {indegrees[edge.Tail]--if indegrees[edge.Tail] == 0 {stack.Push(edge.Tail)indegrees[edge.Tail] = -1for _, endEdge := range g.GetEdgesByTail(edge.Tail) {val, ok := eventEarly[edge.Tail]if !ok {eventEarly[edge.Tail] = eventEarly[endEdge.Head] + endEdge.Val} else {if val < eventEarly[endEdge.Head]+endEdge.Val {eventEarly[edge.Tail] = val}}}}}}// 2. 求eventLatestoutdegrees := make(map[string]int)outstack := linear.NewStack()for _, v := range g.Nodes {outdegrees[v] = g.GetOutdegree(v)if outdegrees[v] == 0 {outstack.Push(v)outdegrees[v] = -1eventLatest[v] = eventEarly[v]}}for !outstack.IsEmpty() {v, _ := outstack.Pop()for _, edge := range g.GetEdgesByTail(v) {outdegrees[edge.Head]--if outdegrees[edge.Head] == 0 {outstack.Push(edge.Head)outdegrees[edge.Head] = -1for _, endEdge := range g.GetEdgesByHead(edge.Head) {val, ok := eventLatest[edge.Head]if !ok {eventLatest[edge.Head] = eventLatest[endEdge.Tail] - endEdge.Val} else {if val < eventLatest[endEdge.Tail]-endEdge.Val {eventLatest[edge.Head] = val}}}}}}// 3.求 activityEarlyfor _, v := range g.GetEdgeList() {activeEarly[v.Head+"-"+v.Tail] = eventEarly[v.Head]}// 4. 求activeLatestfor _, v := range g.GetEdgeList() {activeLatest[v.Head+"-"+v.Tail] = eventLatest[v.Tail] - v.Val}// 5.关键活动var keyActivity []stringfor k,v := range activeEarly {if activeLatest[k] == v {keyActivity = append(keyActivity,k)}}fmt.Println(keyActivity)return keyActivity}
.go
package aoeimport "testing"func TestAOEKeyEvents(t *testing.T) {list := AOEKeyEvents()if len(list) != 6 {t.Fail()}}
添加了新方法的 有向图 .go
package graphimport ("errors")const DMaxSize = 20const DMaxNum = 99999type DMGraph struct {Edges[DMaxSize][DMaxSize]intEdgeNum intNodes[]stringIndexsmap[string]int}type DEdge struct {Head, Tail stringValint}func NewDMGraph() DMGraph {var g DMGraphfor k, v := range g.Edges {for kk, _ := range v {if k == kk {g.Edges[k][kk] = 0} else {g.Edges[k][kk] = DMaxNum}}}g.Indexs = make(map[string]int)return g}func (g *DMGraph) AddNode(nodeName string) error {if g.Indexs == nil {return errors.New("不是有效的图")}if _, ok := g.Indexs[nodeName]; ok {return errors.New("已经添加过此结点")}g.Indexs[nodeName] = len(g.Nodes)g.Nodes = append(g.Nodes, nodeName)return nil}func (g *DMGraph) AddEdge(Head, Tail string, val int) error {if _, ok := g.Indexs[Head]; !ok {return errors.New("结点不存在:" + Head)}if _, ok := g.Indexs[Tail]; !ok {return errors.New("结点不存在:" + Tail)}if g.Edges[g.Indexs[Head]][g.Indexs[Tail]] != DMaxNum {return errors.New("边已经存在")}g.Edges[g.Indexs[Head]][g.Indexs[Tail]] = valg.EdgeNum++return nil}func (g *DMGraph) GetEdgeList() []DEdge {var edgeList []DEdgefor i := 0; i < len(g.Nodes); i++ {for j := 0; j < len(g.Nodes); j++ {if g.Edges[i][j] != DMaxNum && i != j {edgeList = append(edgeList,DEdge{Head: g.Nodes[i], Tail: g.Nodes[j], Val: g.Edges[i][j]},)}}}return edgeList}func (g *DMGraph) GetIndegree(ele string) int {tail, ok := g.Indexs[ele]if !ok {return -1 //点不存在}indegree := 0for i := 0; i < len(g.Nodes); i++ {if g.Edges[i][tail] != 0 && g.Edges[i][tail] != DMaxNum {indegree++}}return indegree}func (g *DMGraph) GetOutdegree(ele string) int {head, ok := g.Indexs[ele]if !ok {return -1 //点不存在}outdegree := 0for i := 0; i < len(g.Nodes); i++ {if g.Edges[head][i] != 0 && g.Edges[head][i] != DMaxNum {outdegree++}}return outdegree}func (g *DMGraph) GetEdgesByTail(ele string) []DEdge {var edgeList []DEdgetail, ok := g.Indexs[ele]if !ok {return nil}for i := 0; i < len(g.Nodes); i++ {if g.Edges[i][tail] != 0 && g.Edges[i][tail] != DMaxNum {edgeList = append(edgeList,DEdge{Head: g.Nodes[i], Tail: g.Nodes[tail], Val: g.Edges[i][tail]},)}}return edgeList}func (g *DMGraph) GetEdgesByHead(ele string) []DEdge {var edgeList []DEdgehead, ok := g.Indexs[ele]if !ok {return nil}for i := 0; i < len(g.Nodes); i++ {if g.Edges[head][i] != 0 && g.Edges[head][i] != DMaxNum {edgeList = append(edgeList,DEdge{Head: g.Nodes[head], Tail: g.Nodes[i], Val: g.Edges[head][i]},)}}return edgeList}
- 上海健康证查询官网入口 上海健康证查询官方
- 桂林七星区居住证办理时间和地点查询 桂林七星区居住证办理时间和地点
- 上海健康证官方网站 上海健康证查询网址
- 手机怎么测试无线网络稳定性 怎样用手机测试无线网的稳定性
- 顺丰单号怎么区分陆运和空运 顺丰快递单号如何区分空运还是陆运
- 动车与高铁区别在哪儿 高铁和动车区别在哪里?
- 牛网刺根的功效与作用 牛网刺的功效与作用
- 黄牛刺的功效与作用 黄牛刺的功效和用处
- 马桑根功效和作用 马桑根的药用价值与功效作用
- 羊肉粉的功效与作用 羊肉粉的功效和作用