首页 新闻 论坛 群组 Blog 文档 下载 读书 Tag 网摘 搜索 .NET Java 游戏 视频 人才 外包 培训 数据库 书店 程序员
中国软件网
欢迎您:游客 | 登录 注册 帮助
    • 最长简单路径问题（help me大哥 大姐）
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于：2008-04-29 16:59:20 楼主
    «问题描述：
    试设计一个算法，对于给定的带权有向图，计算出该图中指定顶点为起点和终点的最长
    简单路，并分析算法的计算时间复杂性。
    «实验任务：
    对于给定的图G 和G 中的2 个顶点v和w，计算从v到w的最长简单路。
    «数据输入：
    由文件input.txt 给出输入数据。第1 行有2 个正整数n 和m，表示给定的图G 有n 个
    顶点和m条边，顶点编号为1，2，…，n。接下来的m行中，每行有3 个正整数u,v,w，表
    示图G 的一条边(u,v)及其边权w。第m+1 行是一个正整数k，表示要计算k 对顶点间的最
    长简单路。接下来的k 行中，每行有2 个正整数s 和t，表示要计算顶点对s 和t 间的最长
    简单路。
    «结果输出:
    将计算出的各顶点对间的最长简单路长依次输出到文件output.txt。如果不存在满足要
    求的简单路，则输出-1。
    输入文件示例 输出文件示例
    input.txt                                            output.txt
    7 10                                                102
    1 2 -5                                              103
    1 3 -6                                              -1
    1 6 1
    1 7 13
    2 3 100
    3 4 1
    3 5 1
    4 5 1
    5 6 1
    5 7 1
    3
    2 5
    2 6
    2 1
    120  修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于：2008-05-03 10:15:051楼 得分:0
    没看懂,帮顶.
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于：2008-05-03 11:35:072楼 得分:0
    顶
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于：2008-05-03 11:54:083楼 得分:0
    给自己顶，谁帮帮我啊
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于：2008-05-03 20:33:044楼 得分:0
    不懂
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于：2008-05-03 21:27:435楼 得分:0
    你把边的权重都取反，再用个Bellman-Ford算法不就得到最长路径了
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于：2008-05-04 19:40:536楼 得分:0
    dijkstra + heap
    intel比赛5月的题目 5月20日后我会公开并行版本的算法 :)
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于：2008-05-05 17:09:567楼 得分:0
    嘿嘿 我自己解决了 谢谢各位
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于：2008-05-07 16:36:298楼 得分:0
    请问你是怎样解决的啊？可以不可以说下哈？呵呵／．．．
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于：2008-05-08 14:15:069楼 得分:0
    任意取节点i,j，对节点k,如果有dis[i][k]+dis[k][j]>dis[i][j];
    则dis[i][j]=dis[i][k]+dis[k][j],
    不断更新节点之间的距离，最后就得到人以两个节点之间的最长路了
    用一个三重循环，直到节点不再更新为止

    时间复杂度是O(n^3)，用邻接矩阵表示图，dis也是
    二维矩阵，则空间复杂度为O(n^2)
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于：2008-05-08 15:57:0810楼 得分:0
    ls这样迭代可能解不一定正确哦

    如果是纯迭代的话5楼的floyd应该是可行的，

    求关键路径可以不用遍历所有的边，按照节点的最早开工时间和最晚开工时间去计算，具体算法严版数据结构上有
    修改 删除 举报 引用 回复
    网站简介－广告服务－网站地图－帮助－联系方式－诚聘英才－English－ 问题报告
    北京创新乐知广告有限公司 版权所有 京 ICP 证 070598 号
    世纪乐知(北京)网络技术有限公司 提供技术支持
    Copyright © 2000-2008, CSDN.NET, All Rights Reserved