qq_31571775
qq_31571775
采纳率66.7%
2015-12-11 08:09 阅读 1.8k
已采纳

重金悬赏:数据结构,关键路径求法,帮我看看写的对不对!!

20

请帮我检查一下!!!指正错误,或者认为我写的对不对,手机拍的比较小,见谅!!图片图片

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 复制链接分享

6条回答 默认 最新

  • 已采纳
    cuiwei1026522829 另一花生 2015-12-11 12:11

    图片说明

    点赞 2 评论 复制链接分享
  • gzy252050968 RapdoZoro 2015-12-11 10:51

    你图里这是要求最短路径而不是求关键路径,你先弄明白最短路径和关键路径的概念:
    最短路径:如果从某顶点出发,这个顶点称为源点,经图的边到达另一顶点,这个顶点称为终点,所经过的路径不止一条,找出一条路径使的沿此路径上各边的权值之和为最小。(从源点到终点走得最短的路线权值之和)
    关键路径:采用边表示活动(Activity On Edge)网络,简称AOE网络。每个顶点代表一个事件,事件说明某些活动或某一项活动的完成,边表示活动,权表示活动持续的时间(关键路径法,也称为统筹方法)。(从源点到汇点完成时间最长路径之和)即从源点到汇点的最长路径的长度,此长度最大的路径叫做关键路径,也称临界路径。
    好了,明白概念后就该知道怎么求了,一般求最短路径的算法是迪杰斯塔拉算法和弗洛伊德算法,看你的图的答案应该是用的迪杰斯塔拉算法,但你的答案是错误的,明白该算法的思想就知道你错哪了,其实步骤很简单,
    1.初使时令 S={V0},T={其余顶点},T中顶点对应的距离值, 若存在,为弧上的权值(和SPFA初始化方式不同),若不存在,为Inf;
    2.从T中选取一个其距离值为最小的顶点W(贪心体现在此处),加入S(注意不是直接从S集合中选取,理解这个对于理解vis数组的作用至关重要),对T中顶点的距离值进行修改:若加进W作中间顶点,从V0到Vi的距离值比不加W的路径要短,则修改此距离值(上面两个并列for循环,使用最小点更新);
    3.重复上述步骤,直到S中包含所有顶点,即S=V为止(说明最外层是除起点外的遍历)。
    你图里的数看不太清,给你看个例子你就明白怎么做了,妈蛋码了这么多字题主怎么谢我?
    图片说明

    点赞 2 评论 复制链接分享
  • qq_31571775 qq_31571775 2015-12-11 08:13

    这个还比较清楚…………………………图片

    点赞 评论 复制链接分享
  • wr10980170 王倔驴 2015-12-11 08:26

    public static void main(String[] args) {
    String [] str = {"abb","aba","acf","bdq"};
    for (int i = 0; i < str.length; i++) {
    if(str[i].startsWith("ab")){
    System.out.println("Strat With ab:"+str[i]);
    }
    }
    }

    点赞 评论 复制链接分享
  • cuiwei1026522829 另一花生 2015-12-11 12:07

    图片说明

    点赞 评论 复制链接分享
  • cuiwei1026522829 另一花生 2015-12-11 12:13

    有图有真相~~~~~~~~

    点赞 评论 复制链接分享

相关推荐