1
$\begingroup$

This is a rather strange question, but I have used Washall's algorithm in Graph Theory quite a bit on various matrices (representing graphs) to find least cost paths and matrices that reflect these weights.

However, I was wondering if there is any standard solution/notation for recording a path for the relevant weight as well while using Washall's algorithm?

For example I thought of modifying Washall's algorithm as seen below:

Let W be the matrice I am using Washall's algorithm on. Let M be a matrix of dimension n,n such that it can store the relevant paths. These paths will be stored as lists of integers in the matrix, such that each index stores the least cost path between nodes.

For k = 1 to n
   For i = 1 to n
      For j = 1 to n

         If (W[i,j] > W[i,k] + W[k,j]) Then
            # update with new least cost weight
            W[i,j] = W[i,k] + W[k,j]

            # and update the matrice M to store the least cost path
            M[i,j] = M[i,k] + M[k,j]

This then would output an additional matrix M with least cost paths. This, however, seems very crude and unconventional.

However, surely mathematicians running this algorithm want to know the paths to the least cost weights? What do they normally do?

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.