Der Min-Plus-Matrixmultiplikations-Algorithmus ist ein Algorithmus der Graphentheorie , der die Distanzmatrix eines Graphen berechnet. Er läuft mit einer speziellen Matrizenoperation und hat zudem den Vorteil, dass bei jedem Berechnungsschritt automatisch alle Informationen über erreichbare Wege innerhalb der bisher angegebenen Anzahl der Berechnungsschritte verfügbar sind. Er ist allerdings sehr rechenintensiv und daher langsam.
Definitionen
Gegeben seien ein gerichteter Graph
G
=
(
V
,
E
)
{\displaystyle G=(V,E)}
c
i
,
j
{\displaystyle c_{i,j}}
i
{\displaystyle i}
j
{\displaystyle j}
V
{\displaystyle V}
Bewertungsmatrix
Die Kostenmatrix oder Bewertungsmatrix
K
{\displaystyle K}
k
i
,
j
=
{
0
f
a
l
l
s
i
=
j
c
i
,
j
f
a
l
l
s
(
i
,
j
)
∈
E
∞
s
o
n
s
t
{\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}}}
Entfernungsmatrix
Die Entfernungsmatrix
D
{\displaystyle D}
d
i
,
j
=
{
0
,
f
a
l
l
s
i
=
j
L
a
¨
n
g
e
d
e
s
k
u
¨
r
z
e
s
t
e
n
W
e
g
e
s
v
o
n
i
n
a
c
h
j
∞
,
f
a
l
l
s
e
s
k
e
i
n
e
n
W
e
g
g
i
b
t
{\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}}}
F
,
G
{\displaystyle F,G}
n
×
n
{\displaystyle n\times n}
H
=
F
⊕
G
{\displaystyle H=F\oplus G}
h
i
,
j
=
min
{
f
i
,
l
+
g
l
,
j
∣
l
∈
{
1
,
…
,
n
}
}
{\displaystyle h_{i,j}=\min\{f_{i,l}+g_{l,j}\mid l\in \{1,\dots ,n\}\}}
wobei gelten soll
a
+
∞
=
∞
+
a
=
∞
{\displaystyle a+\infty =\infty +a=\infty }
⊕
{\displaystyle \oplus }
Halbring mit
(
0
,
1
,
+
,
⋅
)
:=
(
∞
,
0
,
min
,
+
)
{\displaystyle (0,1,+,\cdot ):=(\infty ,0,\operatorname {min} ,+)}
Statt
K
⊕
K
{\displaystyle K\oplus K}
K
[
2
]
{\displaystyle K^{[2]}}
K
[
n
+
1
]
=
K
[
n
]
⊕
K
{\displaystyle K^{[n+1]}=K^{[n]}\oplus K}
Algorithmus
1.
K
{\displaystyle K}
2. Berechne
K
[
2
]
,
K
[
3
]
,
K
[
4
]
,
.
.
.
{\displaystyle K^{[2]},K^{[3]},K^{[4]},...}
K
[
p
+
1
]
=
K
[
p
]
{\displaystyle K^{[p+1]}=K^{[p]}}
K
[
p
]
=
D
{\displaystyle K^{[p]}=D}
oder
2. Berechne
K
[
2
]
,
K
[
4
]
,
K
[
8
]
,
.
.
.
{\displaystyle K^{[2]},K^{[4]},K^{[8]},...}
K
[
2
∗
p
]
=
K
[
p
]
{\displaystyle K^{[2*p]}=K^{[p]}}
K
[
p
]
=
D
{\displaystyle K^{[p]}=D}
Siehe auch
Quellen 
![{\displaystyle K^{[2]}}](/media/api/rest_v1/media/math/render/svg/d3ec0de8f987c1398aa3c9b2f8045f436cb94432)
![{\displaystyle K^{[n+1]}=K^{[n]}\oplus K}](/media/api/rest_v1/media/math/render/svg/ad1df2d32afd632e0868129347354e66460f0152)
![{\displaystyle K^{[2]},K^{[3]},K^{[4]},...}](/media/api/rest_v1/media/math/render/svg/6c49ef4c58d4a520394bd66fbf10affcd96a2103)
![{\displaystyle K^{[p+1]}=K^{[p]}}](/media/api/rest_v1/media/math/render/svg/8e97e59982cce4d44209ad4658923d2cf876beeb)
![{\displaystyle K^{[p]}=D}](/media/api/rest_v1/media/math/render/svg/784770e129804e9e807fc06674a463fc2aa5bd79)
![{\displaystyle K^{[2]},K^{[4]},K^{[8]},...}](/media/api/rest_v1/media/math/render/svg/ca13e7eb9fe9dc84184ad711ccb3c9fd68a2476b)
![{\displaystyle K^{[2*p]}=K^{[p]}}](/media/api/rest_v1/media/math/render/svg/acec2517f69ec5642a3e55c6aceb027d5e3800fb)