The min-plus matrix multiplication algorithm is a graph theory algorithm that calculates the shortest paths of a graph . It runs with a special matrix multiplication and also has the advantage that for each calculation step, all information about achievable paths within the previously specified number of calculation steps is automatically available. However, it is very computationally intensive and therefore slow.
The matrix gives the length of the shortest paths with a maximum of edges. The entry indicates the length of the shortest path (with a maximum of edges) from node to node .
If the number of nodes is then it applies to all .
If so then .
algorithm
The min-plus matrix multiplication algorithm now calculates based on the cost matrix of the graph so .
Variant 1 : Calculated until . The result of the last step is multiplied by the matrix in each step .
Variant 2 : Calculated until . The result of the last step is squared in each step.
running time
In the following we use Landau notation to indicate the asymptotic behavior of the runtime. In the worst case , variant 1 requires matrix multiplications while variant 2 only requires matrix multiplications. The running time with the naive implementation of the min-plus matrix multiplication is then in for variant 1 and in for variant 2. This means that the algorithm has a worse running time than the comparable algorithm by Floyd and Warshall whose running time is in.
However, run time can be improved by more complicated implementations of min-plus matrix multiplication.