# Bellman-Kalaba algorithm optimization

I wrote a Bellman-Kalaba algorithm which finds the shortest paths between all vertices in graph (for now only distances). It works correctly but it is written iteration by iteration and I have a problem with putting all iterations into one. Number of iterations depends on size of matrix. When the starting distance matrix is D1 and the matrix size is 12x12 the final matrix should have number at least D12 but in each step number of matrix index is duplicating, so in this case there are 4 iterations needed to finish the algorithm (from the starting matrix D1 in sequence into: D2,D4,D8,D16). I'm not going to explain whole Bellman-Kalaba algorithm here because I think it isn't that important (of course I will explain some things if it is needed).

My question is: is it possible to optimize this code to one-iteration form instead of step by step iterations using example data below? The simplest solutions are welcome because i'm a beginner.

Code and compilation:

D1={
{0,1,8,∞,∞,∞,∞,∞,∞,∞,∞,∞},
{∞,0,3,7,∞,∞,∞,∞,∞,∞,∞,∞},
{∞,∞,0,5,∞,5,∞,∞,∞,∞,13,∞},
{∞,∞,∞,0,1,∞,2,6,∞,∞,∞,∞},
{∞,∞,∞,∞,0,4,∞,∞,∞,∞,∞,∞},
{∞,∞,∞,∞,∞,0,2,∞,4,∞,7,∞},
{∞,∞,∞,∞,∞,∞,0,3,∞,∞,∞,∞},
{∞,∞,∞,∞,∞,∞,∞,0,1,8,∞,∞},
{∞,∞,∞,∞,∞,∞,∞,∞,0,4,1,∞},
{∞,∞,∞,∞,∞,∞,∞,∞,∞,0,3,4},
{∞,∞,∞,∞,∞,∞,∞,∞,∞,∞,0,9},
{∞,∞,∞,∞,∞,∞,∞,∞,∞,∞,∞,0}};

Dp=Table[0,{i,12}];

(*1st iteration*)

D2=Table[0,{i,12},{j,12}];
For[i=1,i<=12,i++,
For[j=1,j<=12,j++,
For[h=1,h<=12,h++,Dp[[h]]=D1[[i,h]]+D1[[h,j]];];
D2[[i,j]]=Min[Dp];
]
]
Print["Matrix D2:",MatrixForm[D2]]
Print[" "]

Matrix D2: ({
{0, 1, 4, 8, ∞, 13, ∞, ∞, ∞, ∞, 21, ∞},
{∞, 0, 3, 7, 8, 8, 9, 13, ∞, ∞, 16, ∞},
{∞, ∞, 0, 5, 6, 5, 7, 11, 9, ∞, 12, 22},
{∞, ∞, ∞, 0, 1, 5, 2, 5, 7, 14, ∞, ∞},
{∞, ∞, ∞, ∞, 0, 4, 6, ∞, 8, ∞, 11, ∞},
{∞, ∞, ∞, ∞, ∞, 0, 2, 5, 4, 8, 5, 16},
{∞, ∞, ∞, ∞, ∞, ∞, 0, 3, 4, 11, ∞, ∞},
{∞, ∞, ∞, ∞, ∞, ∞, ∞, 0, 1, 5, 2, 12},
{∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, 0, 4, 1, 8},
{∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, 0, 3, 4},
{∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, 0, 9},
{∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, 0}
})

(*2nd iteration*)

D4=Table[0,{i,12},{j,12}];
For[i=1,i<=12,i++,
For[j=1,j<=12,j++,
For[h=1,h<=12,h++,Dp[[h]]=D2[[i,h]]+D2[[h,j]];];
D4[[i,j]]=Min[Dp];
]
]
Print["Matrix D4:",MatrixForm[D4]]
Print[" "]

Matrix D4: ({
{0, 1, 4, 8, 9, 9, 10, 13, 13, 21, 16, 26},
{∞, 0, 3, 7, 8, 8, 9, 12, 12, 16, 13, 24},
{∞, ∞, 0, 5, 6, 5, 7, 10, 9, 13, 10, 17},
{∞, ∞, ∞, 0, 1, 5, 2, 5, 6, 10, 7, 15},
{∞, ∞, ∞, ∞, 0, 4, 6, 9, 8, 12, 9, 16},
{∞, ∞, ∞, ∞, ∞, 0, 2, 5, 4, 8, 5, 12},
{∞, ∞, ∞, ∞, ∞, ∞, 0, 3, 4, 8, 5, 12},
{∞, ∞, ∞, ∞, ∞, ∞, ∞, 0, 1, 5, 2, 9},
{∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, 0, 4, 1, 8},
{∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, 0, 3, 4},
{∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, 0, 9},
{∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, 0}
})

(*3rd iteration*)

D8=Table[0,{i,12},{j,12}];
For[i=1,i<=12,i++,
For[j=1,j<=12,j++,
For[h=1,h<=12,h++,Dp[[h]]=D4[[i,h]]+D4[[h,j]];];
D8[[i,j]]=Min[Dp];
]
]
Print["Matrix D8:",MatrixForm[D8]]
Print[" "]

Matrix D8: ({
{0, 1, 4, 8, 9, 9, 10, 13, 13, 17, 14, 21},
{∞, 0, 3, 7, 8, 8, 9, 12, 12, 16, 13, 20},
{∞, ∞, 0, 5, 6, 5, 7, 10, 9, 13, 10, 17},
{∞, ∞, ∞, 0, 1, 5, 2, 5, 6, 10, 7, 14},
{∞, ∞, ∞, ∞, 0, 4, 6, 9, 8, 12, 9, 16},
{∞, ∞, ∞, ∞, ∞, 0, 2, 5, 4, 8, 5, 12},
{∞, ∞, ∞, ∞, ∞, ∞, 0, 3, 4, 8, 5, 12},
{∞, ∞, ∞, ∞, ∞, ∞, ∞, 0, 1, 5, 2, 9},
{∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, 0, 4, 1, 8},
{∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, 0, 3, 4},
{∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, 0, 9},
{∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, 0}
})

(*4th iteration*)

D16=Table[0,{i,12},{j,12}];
For[i=1,i<=12,i++,
For[j=1,j<=12,j++,
For[h=1,h<=12,h++,Dp[[h]]=D8[[i,h]]+D8[[h,j]];];
D16[[i,j]]=Min[Dp];
]
]
Print["Matrix D16:",MatrixForm[D16]]
Print[" "]

Matrix D16: ({
{0, 1, 4, 8, 9, 9, 10, 13, 13, 17, 14, 21},
{∞, 0, 3, 7, 8, 8, 9, 12, 12, 16, 13, 20},
{∞, ∞, 0, 5, 6, 5, 7, 10, 9, 13, 10, 17},
{∞, ∞, ∞, 0, 1, 5, 2, 5, 6, 10, 7, 14},
{∞, ∞, ∞, ∞, 0, 4, 6, 9, 8, 12, 9, 16},
{∞, ∞, ∞, ∞, ∞, 0, 2, 5, 4, 8, 5, 12},
{∞, ∞, ∞, ∞, ∞, ∞, 0, 3, 4, 8, 5, 12},
{∞, ∞, ∞, ∞, ∞, ∞, ∞, 0, 1, 5, 2, 9},
{∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, 0, 4, 1, 8},
{∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, 0, 3, 4},
{∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, 0, 9},
{∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, 0}
})

D8==D16
True


There is a rule when algorithm finish its job earlier (when the last matrix is the same as matrix before) but it isn't as much important right now.

• You might want to consider using Inner with the times operation replaced by Plus and the plus operation replaced by Min. Commented May 15, 2018 at 15:06

You could use FixedPoint:

FixedPoint[
Table[Min[#[[i, All]] + #[[All, j]]], {i, 1, 12}, {j, 1, 12}] &, D1]


If you want to see each step then use FixedPointList:

Row[Riffle[
Style[MatrixForm[#], 8] & /@
FixedPointList[
Table[Min[#[[i, All]] + #[[All, j]]], {i, 1, 12}, {j, 1, 12}] &,
D1], "->"]]


• It works great! @halmir @Daniel Lichtblau I would like to take this opportunity to ask another question about this solution. I am trying to implement Demoucron's algorithm which is very similar to this algorithm and have the same stopping rule. Instead of FixedPoint[Table[Min[#[[i, All]] + #[[All, j]]], {i, 1, 12}, {j, 1, 12}] &, D1] it looks like this: FixedPoint[Table[Min[#[[i, h]] + #[[h, j]], #[[i, j]]], {i, 1, 12}, {j, 1, 12}] &, D1] where h startig from h=2 should increase h++ to at most 12 (in case of 12x12 matrix) with each iteration of FixedPoint. part1 Commented May 16, 2018 at 21:17
• It would be great to be able to use FixedPoint again because of same stopping rule. Is it possible somehow to describe inside or outside of FixedPoint proper behavior of h? Or maybe another solution? I'm sorry for abusing comments section. part2 Commented May 16, 2018 at 21:18
• something like this? h = 1; l = Length[D1]; FixedPoint[(h++; Table[Min[#[[i, Min[h, l]]] + #[[Min[h, l], j]], #[[i, j]]], {i, 1, 12}, {j, 1, 12}] )&, D1] Commented May 17, 2018 at 13:38
• Thanks, everything works fine. Commented May 18, 2018 at 21:06