Click here to load reader

Bellman ford

  • View
    1.294

  • Download
    5

Embed Size (px)

Text of Bellman ford

  • 1. bn
    bn
    A
    B
    C
    4
    1
    bn
    2
    -2
    2
    S
    1
    1
    3
    3
    3
    0
    F
    E
    D
    2
    2
    bn
    bn
    bn
    Step 1
    SA
    SF
    AB
    AF
    BC
    BF
    DB
    DC
    EB
    ED
    FA
    FE
    SA

2. bn
bn
2
A
B
C
4
1
bn
2
-2
2
S
1
1
3
3
3
0
F
E
D
2
2
bn
bn
bn
3
Step 1
SA
SF
AB
AF
BC
BF
DB
DC
EB
ED
FA
FE
SA
SF
3. bn
bn
2
3
A
B
C
4
1
bn
2
-2
2
S
1
1
3
3
3
0
F
E
D
2
2
bn
bn
bn
3
Step 1
SA
SF
AB
AF
BC
BF
DB
DC
EB
ED
FA
FE
SF
AB
4. bn
bn
2
3
A
B
C
4
1
bn
2
-2
2
S
1
1
3
3
3
0
F
E
D
2
2
bn
bn
bn
3
Step 1
SA
SF
AB
AF
BC
BF
DB
DC
EB
ED
FA
FE
AB
AF
5. bn
bn
2
3
A
B
C
4
1
bn
7
2
-2
2
S
1
1
3
3
3
0
F
E
D
2
2
bn
bn
bn
3
Step 1
SA
SF
AB
AF
BC
BF
DB
DC
EB
ED
FA
FE
AF
BC
6. bn
bn
2
3
A
B
C
4
1
bn
7
2
-2
2
S
1
1
3
3
3
0
F
E
D
2
2
bn
bn
bn
3
Step 1
SA
SF
AB
AF
BC
BF
DB
DC
EB
ED
FA
FE
BC
BF
7. bn
bn
2
3
A
B
C
4
1
bn
7
2
-2
2
S
1
1
3
3
3
0
F
E
D
2
2
bn
bn
bn
3
Step 1
SA
SF
AB
AF
BC
BF
DB
DC
EB
ED
FA
FE
BF
DB
8. bn
bn
2
3
A
B
C
4
1
bn
7
2
-2
2
S
1
1
3
3
3
0
F
E
D
2
2
bn
bn
bn
3
Step 1
SA
SF
AB
AF
BC
BF
DB
DC
EB
ED
FA
FE
DB
DC
9. bn
bn
2
3
A
B
C
4
1
bn
7
2
-2
2
S
1
1
3
3
3
0
F
E
D
2
2
bn
bn
bn
3
Step 1
SA
SF
AB
AF
BC
BF
DB
DC
EB
ED
FA
FE
DC
EB
10. bn
bn
2
3
A
B
C
4
1
bn
7
2
-2
2
S
1
1
3
3
3
0
F
E
D
2
2
bn
bn
bn
3
Step 1
SA
SF
AB
AF
BC
BF
DB
DC
EB
ED
FA
FE
EB
ED
11. 2
bn
1
3
A
B
C
4
1
bn
7
2
-2
2
S
1
1
3
3
3
0
F
E
D
2
2
bn
bn
bn
3
Step 1
SA
SF
AB
AF
BC
BF
DB
DC
EB
ED
FA
FE
ED
FA
12. 2
bn
1
3
A
B
C
4
1
bn
7
2
-2
2
S
1
1
3
3
3
0
F
E
D
2
2
bn
bn
bn
3
5
Step 1
SA
SF
AB
AF
BC
BF
DB
DC
EB
ED
FA
FE
FA
FE
13. 2
bn
1
3
A
B
C
4
1
bn
7
2
-2
2
S
1
1
3
3
3
0
F
E
D
2
2
bn
bn
bn
3
5
Step 2
SA
SF
AB
AF
BC
BF
DB
DC
EB
ED
FA
FE
SA
14. 2
bn
1
3
A
B
C
4
1
bn
7
2
-2
2
S
1
1
3
3
3
0
F
E
D
2
2
bn
bn
bn
3
5
Step 2
SA
SF
AB
AF
BC
BF
DB
DC
EB
ED
FA
FE
SA
SF
15. 2
3
1
2
A
B
C
4
1
bn
7
2
-2
2
S
1
1
3
3
3
0
F
E
D
2
2
bn
bn
bn
3
5
Step 2
SA
SF
AB
AF
BC
BF
DB
DC
EB
ED
FA
FE
SF
AB
16. 2
3
1
2
A
B
C
4
1
bn
7
2
-2
2
S
1
1
3
3
3
0
F
E
D
2
2
bn
bn
bn
3
5
Step 2
SA
SF
AB
AF
BC
BF
DB
DC
EB
ED
FA
FE
AB
AF
17. 2
3
1
2
A
B
C
4
1
7
6
2
-2
2
S
1
1
3
3
3
0
F
E
D
2
2
bn
bn
bn
3
5
Step 2
SA
SF
AB
AF
BC
BF
DB
DC
EB
ED
FA
FE
AF
BC
18. 2
3
1
2
A
B
C
4
1
7
6
2
-2
2
S
1
1
3
3
3
0
F
E
D
2
2
bn
bn
bn
3
5
Step 2
SA
SF
AB
AF
BC
BF
DB
DC
EB
ED
FA
FE
BC
BF
19. 2
3
1
2
A
B
C
4
1
7
6
2
-2
2
S
1
1
3
3
3
0
F
E
D
2
2
bn
bn
bn
3
5
Step 2
SA
SF
AB
AF
BC
BF
DB
DC
EB
ED
FA
FE
BF
DB
20. 2
3
1
2
A
B
C
4
1
7
6
2
-2
2
S
1
1
3
3
3
0
F
E
D
2
2
bn
bn
bn
3
5
Step 2
SA
SF
AB
AF
BC
BF
DB
DC
EB
ED
FA
FE
DB
DC
21. 2
3
1
2
A
B
C
4
1
7
6
2
-2
2
S
1
1
3
3
3
0
F
E
D
2
2
bn
bn
bn
3
5
Step 2
SA
SF
AB
AF
BC
BF
DB
DC
EB
ED
FA
FE
DC
EB
22. 2
3
1
2
A
B
C
4
1
7
6
2
-2
2
S
1
1
3
3
3
0
F
E
D
2
2
bn
7
bn
bn
3
5
Step 2
SA
SF
AB
AF
BC
BF
DB
DC
EB
ED
FA
FE
EB
ED
23. 2
3
1
2
A
B
C
4
1
7
6
2
-2
2
S
1
1
3
3
3
0
F
E
D
2
2
bn
7
bn
bn
3
5
Step 2
SA
SF
AB
AF
BC
BF
DB
DC
EB
ED
FA
FE
ED
FA
24. 2
3
1
2
A
B
C
4
1
7
6
2
-2
2
S
1
1
3
3
3
0
F
E
D
2
2
bn
7
bn
bn
3
5
Step 2
SA
SF
AB
AF
BC
BF
DB
DC
EB
ED
FA
FE
FA
FE
25. 2
3
1
2
A
B
C
4
1
7
6
2
-2
2
S
1
1
3
3
3
0
F
E
D
2
2
bn
7
bn
bn
3
5
Step 3
SA
SF
AB
AF
BC
BF
DB
DC
EB
ED
FA
FE
SA
26. 2
3
1
2
A
B
C
4
1
7
6
2
-2
2
S
1
1
3
3
3
0
F
E
D
2
2
bn
7
bn
bn
3
5
Step 3
SA
SF
AB
AF
BC
BF
DB
DC
EB
ED
FA
FE
SA
SF
27. 2
3
1
2
A
B
C
4
1
7
6
2
-2
2
S
1
1
3
3
3
0
F
E
D
2
2
bn
7
bn
bn
3
5
Step 3
SA
SF
AB
AF
BC
BF
DB
DC
EB
ED
FA
FE
SF
AB
28. 2
3
1
2
A
B
C
4
1
7
6
2
-2
2
S
1
1
3
3
3
0
F
E
D
2
2
bn
7
bn
bn
3
5
Step 3
SA
SF
AB
AF
BC
BF
DB
DC
EB
ED
FA
FE
AB
AF
29. 2
3
1
2
A
B
C
4
1
7
6
2
-2
2
S
1
1
3
3
3
0
F
E
D
2
2
bn
7
bn
bn
3
5
Step 3
SA
SF
AB
AF
BC
BF
DB
DC
EB
ED
FA
FE
AF
BC
30. 2
3
1
2
A
B
C
4
1
7
6
2
-2
2
S
1
1
3
3
3
0
F
E
D
2
2
bn
7
bn
bn
3
5
Step 3
SA
SF
AB
AF
BC
BF
DB
DC
EB
ED
FA
FE
BC
BF
31. 2
3
1
2
A
B
C
4
1
7
6
2
-2
2
S
1
1
3
3
3
0
F
E
D
2
2
bn
7
bn
bn
3
5
Step 3
SA
SF
AB
AF
BC
BF
DB
DC
EB
ED
FA
FE
BF
DB
32. 2
3
1
2
A
B
C
4
1
7
6
2
-2
2
S
1
1
3
3
3
0
F
E
D
2
2
bn
7
bn
bn
3
5
Step 3
SA
SF
AB
AF
BC
BF
DB
DC
EB
ED
FA
FE
DB
DC
33. 2
3
1
2
A
B
C
4
1
7
6
2
-2
2
S
1
1
3
3
3
0
F
E
D
2
2
bn
7
bn
bn
3
5
Step 3
SA
SF
AB
AF
BC
BF
DB
DC
EB
ED
FA
FE
DC
EB
34. 2
3
1
2
A
B
C
4
1
7
6
2
-2
2
S
1
1
3
3
3
0
F
E
D
2
2
bn
7
bn
bn
3
5
Step 3
SA
SF
AB
AF
BC
BF
DB
DC
EB
ED
FA
FE
EB
ED
35. 2
3
1
2
A
B
C
4
1
7
6
2
-2
2
S
1
1
3
3
3
0
F
E
D
2
2
bn
7
bn
bn
3
5
Step 3
SA
SF
AB
AF
BC
BF
DB
DC
EB
ED
FA
FE
ED
FA
36. 2
3
1
2
A
B
C
4
1
7
6
2
-2
2
S
1
1
3
3
3
0
F
E
D
2
2
bn
7
bn
bn
3
5
Step 3
SA
SF
AB
AF
BC
BF
DB
DC
EB
ED
FA
FE
FA
FE
37. 2
3
1
2
A
B
C
4
1
7
6
2
-2
2
S
1
1
3
3
3
0
F
E
D
2
2
bn
7
bn
bn
3
5
Step 3
dist step 3?
!
!!
SA
SF
AB
AF
BC
BF
DB
DC
EB
ED
FA
FE