鱼C论坛

 找回密码
 立即注册
查看: 2924|回复: 0

[学习笔记] 《数据结构与算法》——关键路径

[复制链接]
发表于 2017-8-21 20:44:23 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
关键路径:
1)AOE网是一个带有权值的有向图,在AOE网中用点表示事件,边表示时间,起始点称为源点,终点称为汇点,AOE网是从源点开始,结束于汇点。
2)我们需要在AOE网中找到一条从源点到汇点权值之和最大的路径,这就称之为关键路径。
3)etv:顶点Vk最早发生时间
  ltv:顶点Vk最晚发生时间
  ete:弧最ak早发生时间
  lte:弧最晚ak发生时间
4)我们通过比较ete和lte-相邻弧的权,我们可以知道,当且仅当二者相等的时候,该条弧为最大弧,可加入关键路径。重复至找到源点,我们即可找到完整的关键路径
  1. class EdgeNode
  2. {
  3. public:
  4.         int adjvex;
  5.         int weight;
  6.         EdgeNode *next;
  7. }edgeNode;

  8. class vertexNode
  9. {
  10. public:
  11.         int in;
  12.         int data;
  13.         EdgeNode *fedge;
  14. };

  15. class Gra
  16. {
  17. public:
  18.         vertexNode *adList;
  19.         int numVertex, numEdge;
  20. };

  21. int *ltv, *etv, *stack2;
  22. int top2;

  23. void CriticalPath(Gra GL)
  24. {
  25.         EdgeNode *e;
  26.         int getto;
  27.         int ete, lte;
  28.         // 调用改进后的拓扑排序,求出etv和stack2的值
  29.         TopologicalSort(GL);
  30.         ltv = new int[GL.numVertex];
  31.         for (int i = 0; i < GL.numVertex; i++)
  32.         {
  33.                 *(ltv + i) = etv[GL.numVertex-1];
  34.         }
  35.         while (top2 != 0)
  36.         {
  37.                 getto = stack2[top2--];
  38.                 for (e = GL.adList[getto].fedge; e; e = e->next)
  39.                 {
  40.                         k = e->adjvex;
  41.                         if ((ltv[k] - *e->weight) < ltv[getto])
  42.                         {
  43.                                 ltv[getto] = (ltv[k] - *e->weight);
  44.                         }
  45.                 }
  46.         }
  47.         for (int j = 0; j < GL.numVertex; j++)
  48.         {
  49.                 for (e = GL.adList[j].fedge; e; e = e->next)
  50.                 {
  51.                         k = e->adjvex;
  52.                         ete = etv[j];
  53.                         lte = ltv[j] - e->weight;
  54.                         if (ete == lte)
  55.                         {
  56.                                 printf("<v%d,v%d> length: %d , ", GL->adjList[j].data, GL->adjList[k].data, e->weight);
  57.                         }
  58.                 }
  59.         }
  60. }
复制代码

评分

参与人数 1鱼币 +4 收起 理由
小甲鱼 + 4 支持楼主!

查看全部评分

本帖被以下淘专辑推荐:

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 19:20

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表