#include
<
iostream
>
using
namespace
std;
const
int
MAXN
=
100
;
const
int
MAXV
=
MAXN
*
MAXN;
const
int
INF
=
2000000000
;
struct
EDGE
{
int
u, v;
}
;
int
g[MAXN][MAXN];
EDGE e[MAXV];
int
BellmanFord(
int
beg,
int
end,
int
nNum,
int
eNum)
{
//
nNum为顶点数, eNum为边数, 复杂度O(VE)
int
d[MAXN];
int
i, k;
for
(i
=
0
; i
<
nNum; i
++
)
d[i]
=
INF;
d[beg]
=
0
;
bool
ex
=
true
;
for
(k
=
1
; k
<
nNum
&&
ex; k
++
)
{
ex
=
false
;
for
(i
=
0
; i
<
eNum; i
++
)
if
(d[e[i].u]
<
INF
&&
d[e[i].v]
>
d[e[i].u]
+
g[e[i].u][e[i].v])
{
d[e[i].v]
=
d[e[i].u]
+
g[e[i].u][e[i].v];
ex
=
true
;
}
}
return
d[end];
}
int
main()
{
int
i, j;
int
t
=
0
;
int
eNum
=
0
;
int
nNum
=
9
;
for
(i
=
0
; i
<
4
; i
++
)
for
(j
=
0
; j
<
4
; j
++
)
{
if
(i
==
j)
{
g[i][j]
=
INF;
}
else
{
g[i][j]
=
++
t;
e[eNum].u
=
i;
e[eNum].v
=
j;
eNum
++
;
}
}
cout
<<
BellmanFord(
2
,
3
, nNum, eNum)
<<
endl;
return
0
;
}
posted on 2006-09-22 22:04
豪 阅读(1138)
评论(1) 编辑 收藏 引用 所属分类:
数据结构与算法