Considere a seguinte matriz de distâncias, gerada para o grafo mostrado no enunciado:

0 7 15 5 14 11 22
7 0 8 9 7 15 16
15 8 0 17 5 13 14
5 9 17 0 14 6 17
14 7 5 14 0 8 9
11 15 13 6 8 0 11
22 16 14 17 9 11 0

O 'hospital' deverá ser construído no vértice 5 porque o maior valor na linha 5 é 14, enquanto que nas demais linhas temos: 22 (linha 1), 16 (linha 2), 17 (linha 3), 17 (linha 4). 15 (linha 6) e 22 (linha 7). Agora, supondo que o maior na linha 5 fosse, por exemplo, 15 então haveria dois nós escolhidos: o 5 e o 7.
Portanto, não deve ser levada em consideração a SOMA dos valores das linhas, mas sim o MAIOR valor da linha.