?
#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
豪 閱讀(1143)
評論(1) 編輯 收藏 引用 所屬分類:
數據結構與算法