37
2 4 1 -2 3 1 2 3 2 2 1 0 bn bn bn bn bn bn 3 Step 1 SF AB AF BC BF DB DC EB ED FA FE SA

Bellman ford

  • Upload
    bidil

  • View
    1.313

  • Download
    5

Embed Size (px)

Citation preview

Page 1: Bellman ford

2

41

-2

3

1

2

32

2

1

0

bn bn

bn bn

bn

bn

3

Step 1

SA SF AB AF BC BF DB DC EB ED FA FESA

Page 2: Bellman ford

2

41

-2

3

1

2

32

2

1

0

bn bn

bn bn

bn

bn

3

SA SF AB AF BC BF DB DC EB ED FA FESA

2

SF

3

Step 1

Page 3: Bellman ford

2

41

-2

3

1

2

32

2

1

0

bn bn

bn bn

bn

bn

3

SA SF AB AF BC BF DB DC EB ED FA FE

2

SF

3

AB

3

Step 1

Page 4: Bellman ford

2

41

-2

3

1

2

32

2

1

0

bn bn

bn bn

bn

bn

3

SA SF AB AF BC BF DB DC EB ED FA FE

2

3

AB

3

AF

Step 1

Page 5: Bellman ford

2

41

-2

3

1

2

32

2

1

0

bn bn

bn bn

bn

bn

3

SA SF AB AF BC BF DB DC EB ED FA FE

2

3

3

AF BC

7

Step 1

Page 6: Bellman ford

2

41

-2

3

1

2

32

2

1

0

bn bn

bn bn

bn

bn

3

SA SF AB AF BC BF DB DC EB ED FA FE

2

3

3

BC

7

BF

Step 1

Page 7: Bellman ford

2

41

-2

3

1

2

32

2

1

0

bn bn

bn bn

bn

bn

3

SA SF AB AF BC BF DB DC EB ED FA FE

2

3

3

7

BF DB

Step 1

Page 8: Bellman ford

2

41

-2

3

1

2

32

2

1

0

bn bn

bn bn

bn

bn

3

SA SF AB AF BC BF DB DC EB ED FA FE

2

3

3

7

DB DC

Step 1

Page 9: Bellman ford

2

41

-2

3

1

2

32

2

1

0

bn bn

bn bn

bn

bn

3

SA SF AB AF BC BF DB DC EB ED FA FE

2

3

3

7

DC EB

Step 1

Page 10: Bellman ford

2

41

-2

3

1

2

32

2

1

0

bn bn

bn bn

bn

bn

3

SA SF AB AF BC BF DB DC EB ED FA FE

2

3

3

7

EB ED

Step 1

Page 11: Bellman ford

2

41

-2

3

1

2

32

2

1

0

2 bn

bn bn

bn

bn

3

SA SF AB AF BC BF DB DC EB ED FA FE

1

3

3

7

ED FA

Step 1

Page 12: Bellman ford

2

41

-2

3

1

2

32

2

1

0

2 bn

bn bn

bn

bn

3

Step 1

SA SF AB AF BC BF DB DC EB ED FA FE

1

3

3

7

FA FE

5

Page 13: Bellman ford

2

41

-2

3

1

2

32

2

1

0

2 bn

bn bn

bn

bn

3

Step 2

SA SF AB AF BC BF DB DC EB ED FA FE

1

3

3

7

5

SA

Page 14: Bellman ford

2

41

-2

3

1

2

32

2

1

0

2 bn

bn bn

bn

bn

3

SA SF AB AF BC BF DB DC EB ED FA FE

1

3

3

7

5

SA SF

Step 2

Page 15: Bellman ford

2

41

-2

3

1

2

32

2

1

0

2 3

bn bn

bn

bn

3

SA SF AB AF BC BF DB DC EB ED FA FE

1

3

2

7

5

SF AB

Step 2

Page 16: Bellman ford

2

41

-2

3

1

2

32

2

1

0

2 3

bn bn

bn

bn

3

SA SF AB AF BC BF DB DC EB ED FA FE

1

3

2

7

5

AB AF

Step 2

Page 17: Bellman ford

2

41

-2

3

1

2

32

2

1

0

2 3

bn bn

7

bn

3

SA SF AB AF BC BF DB DC EB ED FA FE

1

3

2

6

5

AF BC

Step 2

Page 18: Bellman ford

2

41

-2

3

1

2

32

2

1

0

2 3

bn bn

7

bn

3

SA SF AB AF BC BF DB DC EB ED FA FE

1

3

2

6

5

BC BF

Step 2

Page 19: Bellman ford

2

41

-2

3

1

2

32

2

1

0

2 3

bn bn

7

bn

3

SA SF AB AF BC BF DB DC EB ED FA FE

1

3

2

6

5

BF DB

Step 2

Page 20: Bellman ford

2

41

-2

3

1

2

32

2

1

0

2 3

bn bn

7

bn

3

SA SF AB AF BC BF DB DC EB ED FA FE

1

3

2

6

5

DB DC

Step 2

Page 21: Bellman ford

2

41

-2

3

1

2

32

2

1

0

2 3

bn bn

7

bn

3

SA SF AB AF BC BF DB DC EB ED FA FE

1

3

2

6

5

DC EB

Step 2

Page 22: Bellman ford

2

41

-2

3

1

2

32

2

1

0

2 3

bn bn

7

bn

3

SA SF AB AF BC BF DB DC EB ED FA FE

1

3

2

6

5

EB ED

7

Step 2

Page 23: Bellman ford

2

41

-2

3

1

2

32

2

1

0

2 3

bn bn

7

bn

3

SA SF AB AF BC BF DB DC EB ED FA FE

1

3

2

6

5

ED

7

FA

Step 2

Page 24: Bellman ford

2

41

-2

3

1

2

32

2

1

0

2 3

bn bn

7

bn

3

Step 2

SA SF AB AF BC BF DB DC EB ED FA FE

1

3

2

6

5

7

FA FE

Page 25: Bellman ford

2

41

-2

3

1

2

32

2

1

0

2 3

bn bn

7

bn

3

Step 3

SA SF AB AF BC BF DB DC EB ED FA FE

1

3

2

6

5

7

SA

Page 26: Bellman ford

2

41

-2

3

1

2

32

2

1

0

2 3

bn bn

7

bn

3

Step 3

SA SF AB AF BC BF DB DC EB ED FA FE

1

3

2

6

5

7

SA SF

Page 27: Bellman ford

2

41

-2

3

1

2

32

2

1

0

2 3

bn bn

7

bn

3

Step 3

SA SF AB AF BC BF DB DC EB ED FA FE

1

3

2

6

5

7

SF AB

Page 28: Bellman ford

2

41

-2

3

1

2

32

2

1

0

2 3

bn bn

7

bn

3

Step 3

SA SF AB AF BC BF DB DC EB ED FA FE

1

3

2

6

5

7

AB AF

Page 29: Bellman ford

2

41

-2

3

1

2

32

2

1

0

2 3

bn bn

7

bn

3

Step 3

SA SF AB AF BC BF DB DC EB ED FA FE

1

3

2

6

5

7

AF BC

Page 30: Bellman ford

2

41

-2

3

1

2

32

2

1

0

2 3

bn bn

7

bn

3

Step 3

SA SF AB AF BC BF DB DC EB ED FA FE

1

3

2

6

5

7

BC BF

Page 31: Bellman ford

2

41

-2

3

1

2

32

2

1

0

2 3

bn bn

7

bn

3

Step 3

SA SF AB AF BC BF DB DC EB ED FA FE

1

3

2

6

5

7

BF DB

Page 32: Bellman ford

2

41

-2

3

1

2

32

2

1

0

2 3

bn bn

7

bn

3

Step 3

SA SF AB AF BC BF DB DC EB ED FA FE

1

3

2

6

5

7

DB DC

Page 33: Bellman ford

2

41

-2

3

1

2

32

2

1

0

2 3

bn bn

7

bn

3

Step 3

SA SF AB AF BC BF DB DC EB ED FA FE

1

3

2

6

5

7

DC EB

Page 34: Bellman ford

2

41

-2

3

1

2

32

2

1

0

2 3

bn bn

7

bn

3

Step 3

SA SF AB AF BC BF DB DC EB ED FA FE

1

3

2

6

5

7

EB ED

Page 35: Bellman ford

2

41

-2

3

1

2

32

2

1

0

2 3

bn bn

7

bn

3

Step 3

SA SF AB AF BC BF DB DC EB ED FA FE

1

3

2

6

5

7

ED FA

Page 36: Bellman ford

2

41

-2

3

1

2

32

2

1

0

2 3

bn bn

7

bn

3

Step 3

SA SF AB AF BC BF DB DC EB ED FA FE

1

3

2

6

5

7

FA FE

Page 37: Bellman ford

2

41

-2

3

1

2

32

2

1

0

2 3

bn bn

7

bn

3

Step 3

SA SF AB AF BC BF DB DC EB ED FA FE

1

3

2

6

5

7

Άλλαξε κάποιο dist στο step 3?

Όχι! Άπα τελειώσαμε!!