Min-plus matrix multiplication algorithm

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.

Definitions

Let a directed graph and a matrix with weights be given , with the indices and running over the set . ${\displaystyle G=(V,E)}$ ${\displaystyle c_{i,j}}$ ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle V}$

Evaluation matrix

The cost matrix or evaluation matrix is then defined as follows: ${\displaystyle K}$

${\displaystyle k_{i,j}={\begin{cases}0~\mathrm {falls} ~i=j\\c_{i,j}~\mathrm {falls} ~(i,j)\in E\\\infty ~\mathrm {sonst} \end{cases}}}$

Distance matrix

The distance matrix is defined as follows ${\displaystyle D}$

${\displaystyle d_{i,j}={\begin{cases}0,~\mathrm {falls} ~i=j\\\mathrm {L{\ddot {a}}nge~des~k{\ddot {u}}rzesten~Weges~von~} i\mathrm {~nach~} j\\\infty ,~\mathrm {falls~es~keinen~Weg~gibt} ~\end{cases}}}$

Matrix operation ⊕

${\displaystyle F,G}$let two matrices. The matrix is calculated as follows: ${\displaystyle n\times n}$ ${\displaystyle H=F\oplus G}$

${\displaystyle h_{i,j}=\min\{f_{i,l}+g_{l,j}\mid l\in \{1,\dots ,n\}\}}$

where should apply . ${\displaystyle a+\infty =\infty +a=\infty }$

${\displaystyle \oplus }$is the multiplication of matrices over a half ring with . ${\displaystyle (0,1,+,\cdot ):=(\infty ,0,\operatorname {min} ,+)}$

Instead of writing briefly . ${\displaystyle K\oplus K}$ ${\displaystyle K^{[2]}}$

${\displaystyle K^{[i+1]}=K^{[i]}\oplus K}$

Relation to Shortest Paths

For a directed graph with positive edge weights (or with a conservative weight function ): ${\displaystyle G=(V,E)}$ ${\displaystyle c_{i,j}}$

• 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 . ${\displaystyle K^{[p]}=(k_{i,j}^{[p]})}$ ${\displaystyle p}$ ${\displaystyle k_{i,j}^{[p]}}$ ${\displaystyle p}$ ${\displaystyle i}$ ${\displaystyle j}$
• If the number of nodes is then it applies to all . ${\displaystyle n}$ ${\displaystyle K^{[p]}=D}$ ${\displaystyle p\geq n-1}$
• If so then . ${\displaystyle K^{[p+1]}=K^{[p]}}$ ${\displaystyle K^{[p]}=D}$

algorithm

The min-plus matrix multiplication algorithm now calculates based on the cost matrix of the graph so . ${\displaystyle K}$ ${\displaystyle K^{[p]}}$ ${\displaystyle K^{[p+1]}=K^{[p]}=D}$

Variant 1 : Calculated until . The result of the last step is multiplied by the matrix in each step . ${\displaystyle K^{[2]},K^{[3]},K^{[4]},...}$ ${\displaystyle K^{[p+1]}=K^{[p]}}$ ${\displaystyle K}$

Variant 2 : Calculated until . The result of the last step is squared in each step. ${\displaystyle K^{[2]},K^{[4]},K^{[8]},...}$ ${\displaystyle K^{[2*p]}=K^{[p]}}$

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. ${\displaystyle \Theta \left(n\right)}$ ${\displaystyle \Theta \left(\log n\right)}$ ${\displaystyle \Theta \left(n^{4}\right)}$ ${\displaystyle \Theta \left(n^{3}\cdot \log n\right)}$ ${\displaystyle {\mathcal {O}}(n^{3})}$

However, run time can be improved by more complicated implementations of min-plus matrix multiplication.

See also

• Pathfinding

swell

• Thomas H. Cormen, Charles Leiserson , Ronald L. Rivest , Clifford Stein: Introduction to Algorithms. 2nd Edition. MIT Press, 2001, ISBN 0-262-53196-8 , pp. 622-627