Min-plus matrix multiplication

The minimum plus matrix multiplication algorithm is an algorithm of the graph theory, which calculates the shortest paths of a graph. He runs with a special matrix multiplication and also has the advantage that automatically complete information about accessible routes within the specified date number of calculation steps are available at each calculation step. However, he is very computationally intensive and therefore slow.

• 3.1 Running time

Definitions

Given a directed graph and a matrix of weights, where the indices and run over the crowd.

Evaluation matrix

The cost matrix or evaluation matrix is then defined as follows:

Distance matrix

The distance matrix is defined as follows

Matrix operation ⊕

Be two matrices. The matrix is calculated as follows:

Is being considered.

So with the multiplication of matrices over a semiring.

Instead, we briefly review.

Related to shortest paths

For a directed graph with positive edge weights (or with a conservative weight function ) applies:

• The matrix indicates the length of the shortest paths with maximum edge. The entry thus indicates the Länges of the shortest path ( with a maximum of edges) from node to node.
• If the number of nodes is then valid for all.
• If then also.

Algorithm

The min -plus matrix multiplication algorithm computes now starting so from the cost matrix of the graph.

Option 1: Calculated to. In this case, in each step the result of the last step is multiplied by the matrix.

Option 2: Calculated to. In this case, in each step the result of the last step is squared.

Term

In the following, we use the Landau notation to specify the asymptotic behavior of the term. In the worst case variant requires 1 matrix multiplications while variant 2 only requires matrix multiplications. The term with the naive Implementiertung the min -plus matrix multiplication is then for variant 1 and variant 2 for which enables the algorithm has a worse running time than the comparable algorithm of Floyd and Warshall whose running time is.

The running time can be improved by more complicated Implementiertungen the min -plus matrix multiplication.