0
$\begingroup$

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.

$\endgroup$
1
  • 2
    $\begingroup$ You might want to consider using Inner with the times operation replaced by Plus and the plus operation replaced by Min. $\endgroup$ – Daniel Lichtblau May 15 '18 at 15:06
2
$\begingroup$

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], "->"]]

enter image description here

$\endgroup$
4
  • $\begingroup$ 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 $\endgroup$ – Voyteck May 16 '18 at 21:17
  • $\begingroup$ 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 $\endgroup$ – Voyteck May 16 '18 at 21:18
  • $\begingroup$ 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] $\endgroup$ – halmir May 17 '18 at 13:38
  • $\begingroup$ Thanks, everything works fine. $\endgroup$ – Voyteck May 18 '18 at 21:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.