Da die einzelnen Funktionen, die bei der Berechnung auftreten, auch konkav sind, liegt das gesuchte Minimum auch hier in einem Rand einer Kante, also in einem Knoten selbst.
Der Algorithmus zur Berechnung des absoluten Medians sieht also so aus:
Berechne mit dem Algorithmus von Floyd alle d (i,j) -Werte. |
Bilde für alle Knoten i aus G sum[i] = d (i,j) |
Finde das i mit minimalem sum[i] . Dieser Knoten i ist dann der absolute Median. |
Der Algorithmus ist also erstaunlich einfach, relativ zur Komplexität des Problems gesehen.