由买买提看人间百态
登录
首页
论坛
未名存档
话题女王
小圈子
马甲追踪
版面排名
流量曲线
水枪排名
发帖量曲线
发帖版面饼图
发帖时间柱图
关于本站
帮助
boards
本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字
访问原贴
Programming版
- [合集] 问个图的问题
相关主题
●
请问一个算法
●
wdong和赵老师请进
●
C++大家都怎么做dependency management?
●
[合集] 问个多线程的问题
●
请教一个算法题关于shortest path的
●
[合集] 问个C++题目
●
[合集] 有人用过gasdev()产生随即数吗?求救!
●
再问个最短路径问题,
●
这个图问题的复杂度是多少呢
●
问个红黑树高度的问题
●
[合集] 给定一个最小堆,如何查找某数是否存在此堆中?
●
问个图的问题
●
请问图形搜索所有路径问题
●
[合集] 问个python问题
●
请教系统架构的实现(给最靠谱的设计10个包子)
●
问个编程算法题
相关话题的讨论汇总
话题: 分布
话题: 节点
话题: 路径
话题: may
话题: fri
进入Programming版参与讨论
1
(共1页)
b***y
发帖数: 2799
1
☆─────────────────────────────────────☆
kukutf (五脚蟹★酷酷豆腐) 于 (Fri May 9 14:08:06 2008) 提到:
无圈的有向图,如何估计比较长的路径(从source到sink)的分布?
每个边就算距离1
比如最长的路径个数,第二长的路径个数,第三长的路径个数?
只要大概的就可以了。因为增长的速度很可能是个指数。
有没有什么好办法估计一下?
☆─────────────────────────────────────☆
wdong (cybra) 于 (Fri May 9 16:30:29 2008) 提到:
严格计算可能更容易。大致思路是给每个节点维护一个分布。source的分布是什么都没
有。
然后从source开始遍历整个图。每次找前驱节点都已经被访问的节点。该节点的分布就
是所有前驱节点分布在加上这些分布的距离都加1得到的分布之和。访问完所有节点后
,总得路径分布就是所有sink的分布之和。算法复杂度应该是O(节点数x最大出/入度x
最大路径长度)。
☆──────────────────
1
(共1页)
进入Programming版参与讨论
相关主题
●
问个编程算法题
●
这个图问题的复杂度是多少呢
●
问个数据库服务器配置的问题 (转载)
●
[合集] 给定一个最小堆,如何查找某数是否存在此堆中?
●
问个C#的问题
●
请问图形搜索所有路径问题
●
问个c++删除链表(linked list)节点的问题
●
请教系统架构的实现(给最靠谱的设计10个包子)
●
请问一个算法
●
wdong和赵老师请进
●
C++大家都怎么做dependency management?
●
[合集] 问个多线程的问题
●
请教一个算法题关于shortest path的
●
[合集] 问个C++题目
●
[合集] 有人用过gasdev()产生随即数吗?求救!
●
再问个最短路径问题,
相关话题的讨论汇总
话题: 分布
话题: 节点
话题: 路径
话题: may
话题: fri
未名新帖统计
// 7月16日
#
版面
帖数(主题数)
-
全站
4871 (796)
1
Military
3777 (569)
2
Stock
341 (51)
3
Joke
117 (17)
4
History
116 (3)
5
Automobile
100 (9)
6
USANews
55 (9)
7
Midlife
45 (1)
8
Headline
41 (41)
9
Dreamer
33 (13)
10
FleaMarket
32 (20)
11
Living
30 (7)
* 这里只显示发帖超过25的版面,努力灌水吧:-)
历史上的今天
faintcat妹妹看进来~~
发表于12年前.
NSC, PD 1/7/2007, EB2, ...
发表于11年前.
[FBA求购]MJVE2 758 MJVM2 ...
发表于6年前.
老生常谈,归与不归
发表于10年前.
【申请】Seattle西雅图 版版主——申请人...
发表于9年前.
宝宝出生,头骨骨折,求祝福
发表于9年前.
求推荐舒缓优美的古典音乐
发表于11年前.
百分之一的北京人上北大 中国网友愤怒(转载)
发表于10年前.
新人带狗狗Bailey来报道
发表于12年前.
全世界最有价值的运动队
发表于10年前.
请问大切诺基的质量如何
发表于6年前.
TNND,军版全是BKC
发表于15年前.
Inception
发表于12年前.
微软的有些家属可真恶心,为了卖保险脸都不要了
发表于10年前.
每周坐高铁的苦逼来说说感受吧!!
发表于9年前.