d3f42291-798e-45af-bee4-8a4a6e86b856 13 4 5 false false false 0 3 decimal

Stagecoach Problem

C a b Stagecoach f C rows 1 matrix : P f : 12 mat m b 1 - (a range c ∞ : ν m : 12 mat n m 1 + (b range C m n el f n el + c < c C m n el f n el + : ν n : 12 mat if for f m el c : P m el ν c ∞ ≠ (* : 12 mat 31 line for R a 11 mat : k 1 : 12 mat R k el b ≠ ν R k el : R k k 1 + : el P ν el : 12 mat while f a el a P 1 C rows 1 - (range el stack R 13 mat 51 line :

Notation

C Cost_Matrix ≡

c Min_Cost ≡

P Path ≡

R Optimal_Path ≡

a start ≡

b end ≡

Example:

https://es.wikipedia.org/wiki/Anexo:Ejemplo_de_Algoritmo_de_Bellman_-_Ford

C 0 ∞ ∞ ∞ ∞ 102 ∞ ∞ 410 ∞ ∞ ∞ 8 ∞ 04 ∞ ∞ 22055 mat :

c P R 13 mat C transpose 15 Stagecoach : 41235551 mat 123541 mat 13 mat

Example:

https://www.math.kent.edu/~kowalcyk/modeling/freckaThe%20Stagecoach%20Problem.ppt

C 0243 ∞ ∞ ∞ ∞ ∞ ∞ ∞ 0 ∞ ∞ 746 ∞ ∞ ∞ ∞ ∞ 0 ∞ 324 ∞ ∞ ∞ ∞ ∞ ∞ 0415 ∞ ∞ ∞ ∞ ∞ ∞ ∞ 0 ∞ ∞ 14 ∞ ∞ ∞ ∞ ∞ ∞ 0 ∞ 63 ∞ ∞ ∞ ∞ ∞ ∞ ∞ 033 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 0 ∞ 3 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 04 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 01010 mat :

c P R 13 mat C 110 Stagecoach : 11135558981010101 mat 13581051 mat 13 mat

Alvaro

4 appVersion 1.75.9678.0