Jump to content

help with warshall formula

- - - - -

This topic has been archived. This means that you cannot reply to this topic.
4 replies to this topic

#1
gammaman

gammaman

    Learning Programmer

  • Members
  • PipPipPip
  • 71 posts
Using this formula

W[i,j,k+1]=W[i,j,k]+W[i,k+1,k]*W[K+1,j,k]

How would I solve

W[i][j][3].

Note: I am not programming this. I just need to solve by hand.

#2
WingedPanther

WingedPanther

    A spammer's worst nightmare

  • Moderators
  • 16,831 posts
Well, applying the formula once gives:
W[i,j,3] implies k=2
W[i,j,3] = W[i,j,2] + W[i,3,2]*W[3,j,2]

Now we need to solve W[i,j,2] which implies k=1; W[i,3,2] which implies k=1; and W[3,j,2] which implies k=1.
I wasn't able to find that exact formula, which raises the issue that there must be certain values of k where a different formula applies.
Programming is a branch of mathematics.
My CodeCall Blog | My Personal Blog

#3
gammaman

gammaman

    Learning Programmer

  • Members
  • PipPipPip
  • 71 posts
Looking at this example
W[1,2,1]=W[1,2,0]+W[1,1,0]*W[1,2,0]
then, 1 + 0*1 =1

were does 1 + 0* 1 come from. I mean obviously it comes from the above formula, but it does not seem obvious to me as to how we know the choose the 1,0 and 1.

#4
WingedPanther

WingedPanther

    A spammer's worst nightmare

  • Moderators
  • 16,831 posts
As I said: you HAVE TO have boundary conditions. The formula you provided is not the complete formula.
Programming is a branch of mathematics.
My CodeCall Blog | My Personal Blog

#5
gammaman

gammaman

    Learning Programmer

  • Members
  • PipPipPip
  • 71 posts
Well this is the formula our professor gave us. I appreciate your help. All I really need to know is where the 1+0*1 came from. Because based on what I had in the previous post it looks like for some reason we are choosing i then k then k+1.