Floyd Algorithm, need help with path Matrix..

Hi i'm new here.. Got a little coding problem..
I'm creating an excel macro to determine shortest route between a number of nodes using Floyd's algorithm..
I had no problem calculating and displaying the distance,
but I can't get the path Matrix to give correct result..

From the network pic below, the correct path for T1 to T2 is supposed to be :
T7-T8-T3-T4
But my program gives me T8 - T4..

So i need help fixing the path algorithm in Xls file here :

http://ifile.it/j8dc1a9/floyd_no_cycle.xls

I hope anyone familiar with this algorithm could help me, I'm stuck at this problem for weeks.. :(

Thanks in advance.

Code:

---

Sub Button1_Click()
    Dim i, j, k, n, x
    ActiveWorkbook.Sheets("Input").Activate
    n = ActiveWorkbook.Sheets("Input").Cells(1, 8).Value
   
   
    'Clear output sheet
    For i = 1 To 50
        For j = 1 To 50
            Sheets("Output").Cells(3 + i, 1 + j).Value = Null
            Sheets("Routes").Cells(3 + i, 1 + j).Value = Null
        Next j
    Next i
   
    'Copy weights to output sheet
    For i = 1 To n
        For j = 1 To n
        y = y + 1
            Sheets("Output").Cells(3 + i, 1 + j).Value = Sheets("Input").Cells(3 + i, 1 + j)
            If Sheets("Input").Cells(3 + i, 1 + j).Value = "" Then
                Sheets("Output").Cells(3 + i, 1 + j).Value = 10 ^ 15
            Else
                Sheets("Routes").Cells(3 + i, 1 + j).Value = Sheets("Routes").Cells(3 + i, 1)
            End If
        Next j
        Sheets("Output").Cells(3 + i, 1 + i).Value = 0
    Next i

    'Run algorithm
    Sheets("Output").Activate

    For k = 1 To n
      For i = 1 To n
          For j = 1 To n
              If Sheets("Output").Cells(3 + i, 1 + j) > (Sheets("Output").Cells(3 + i, 1 + k) + Sheets("Output").Cells(3 + k, 1 + j)) Then
                    Sheets("Output").Cells(3 + i, 1 + j) = Sheets("Output").Cells(3 + i, 1 + k) + Sheets("Output").Cells(3 + k, 1 + j)
                  Sheets("Routes").Cells(3 + i, 1 + j) = Sheets("Routes").Cells(3 + k, 1 + j)
                End If
            Next j
        Next i
       
                    'If x = 8 Then
                    'k = n
                  ' End If
    Next k
End Sub

---

I marked the lines where I changed things in red.
You initialized the path matrix wrongly and you updated it with the wrong nodes.

Can you understand your errors ?

Regards,
Zachm