MemoryGarden's Blog
努力 -----------大能猫
C++博客
首页
新随笔
联系
聚合
管理
118 Posts :: 11 Stories :: 20 Comments :: 0 Trackbacks
公告
嵩哥,我想你了。
随笔分类
(102)
AS3(2)
coco2d-x(1)
Hadoop Streaming(2)
ICE(12)
JAVA
JS
LAMP
Linux(14)
OC
pugixml
Python(4)
sth(1)
STL(7)
string.h
XMPP(4)
报告(27)
网络编程(28)
随笔档案
(118)
2012年11月 (1)
2012年9月 (2)
2011年7月 (3)
2011年6月 (25)
2011年3月 (1)
2010年11月 (6)
2010年9月 (1)
2010年1月 (4)
2009年12月 (25)
2009年10月 (4)
2009年9月 (22)
2009年4月 (5)
2008年12月 (1)
2008年11月 (1)
2008年10月 (1)
2008年9月 (16)
文章分类
(10)
acm
计算几何
搜索
图论(10)
文章档案
(11)
2009年10月 (9)
2009年7月 (1)
2008年9月 (1)
相册
acm
hoho
友情链接
15天便利店
15天便利店
analytics
aowarmen's Blog
pku 分类
poj
搜索
最新评论
1. re: 树的直径[未登录]
评论内容较长,点击标题查看
--王
阅读排行榜
1. c++ && python 实现 Hadoop Streaming 的 partitioner 和 模块化 (11239)
2. xmpp muc 群聊协议 4(7953)
3. xmpp muc 群聊协议 1(7951)
4. xmpp muc 群聊协议 3(6945)
5. xmpp muc 群聊协议 2(6005)
bellman
对图进行点 - 1 次松弛
即对最短路径估计值的一个松弛
代码 : 有错请指出
#include
<
stdio.h
>
#include
<
string
.h
>
const
int
_
=
0x7fffffff
;
struct
e{
int
u, v, w;
e(
int
a,
int
b,
int
c){u
=
a; v
=
b; w
=
c;}
e(){}
};
int
n, m, el, d[
100
];e edge[
10000
];
int
path[
100
];
bool
relax(
int
u,
int
v,
int
w){
//
松弛操作
if
(d[u]
!=
_
&&
d[v]
>
d[u]
+
w){
path[v]
=
u;
d[v]
=
d[u]
+
w;
return
true
;
}
return
false
;
}
bool
bellman(){
int
i, j, u, v, w;
bool
ok;
for
(i
=
0
; i
<
n
-
1
; i
++
){
//
点 - 1此松弛操作
ok
=
true
;
for
(j
=
0
; j
<
el; j
++
){
u
=
edge[j].u;v
=
edge[j].v;w
=
edge[j].w;
if
(relax(u, v, w))ok
=
false
;
}
if
(ok)
break
;
//
若此次更新没有对边的松弛,则可以跳出了
}
for
(i
=
0
; i
<
el; i
++
){
u
=
edge[i].u; v
=
edge[i].v;w
=
edge[i].w;
if
(d[u]
!=
_
&&
d[v]
>
d[u]
+
w)
return
false
;
//
验证是否有负环
}
return
true
;
}
void
init(){
int
i;
for
(i
=
0
; i
<
n; i
++
)d[i]
=
_;
//
初始化最短路径估计值,以及路径
memset(path,
-
1
,
sizeof
(path));
d[
0
]
=
0
;el
=
0
;
//
源点的估计值为0
}
int
main(){
freopen(
"
bellman.in
"
,
"
r
"
, stdin);
freopen(
"
bellman.out
"
,
"
w
"
, stdout);
int
i, j, u, v, w;
while
(scanf(
"
%d%d
"
,
&
n,
&
m)
!=
-
1
){
init();
for
(i
=
0
; i
<
m; i
++
){
scanf(
"
%d%d%d
"
,
&
u,
&
v,
&
w);
edge[el].u
=
u;edge[el].v
=
v;edge[el
++
].w
=
w;
}i
=
bellman();
if
(i){
for
(i
=
0
; i
<
n; i
++
){
printf(
"
shortest value from 0 to point %d = %d\n
"
, i, d[i]);
}
}
else
{
puts(
"
..
"
);
}
}
return
0
;
}
posted on 2009-10-06 23:49
memorygarden
阅读(201)
评论(0)
编辑
收藏
引用
所属分类:
图论
只有注册用户
登录
后才能发表评论。
【推荐】100%开源!大型工业跨平台软件C++源码提供,建模,组态!
相关文章:
树的直径
bellman
图的割点
prime + pq
kruskal
有向图的强连通分量 实现
拓扑排序
图的遍历
图的存储
有向图的强连通分量
网站导航:
博客园
IT新闻
BlogJava
知识库
博问
管理
Powered by:
C++博客
Copyright © memorygarden