Wyszukiwanie "najbardziej wartościowej" krawędzi grafu

Cześć,
poszukuję sposobu by w grafie nieskierowanym znaleźć krawędź, której usunięcie spowoduje maksymalne wydłużenie najkrótszej ścieżki pomiędzy dwoma wierzchołkami tego grafu. Jedyne co na szybko przychodzi mi do głowy to znalezienie najkrótszej ścieżki i następnie po kolei obliczanie ścieżek z usuniętą jedną z krawędzi najkrótszej ścieżki. Jakaś część odległości w grafie się nie zmienia, więc troche obliczeń odpada, ale zapewne jest jakaś szybsza metoda.

Ja bym pewnie szukał minimalnego drzewa rozpinającego.
https://pl.wikipedia.org/wiki​/Minimalne_drzewo_rozpinaj%C4%85ce

Cały trick polega na tym, aby z dodatnich wartości w grafie zrobić ujemne (czyli ).

/edit:
A jak nie chcesz mieć wartości ujemnych to wyszukujesz dodatkowo największą wartość (przed zmianą znaku) i po zmianie znaku dodajesz ją do wszystkich węzłów. Wówczas najmniejsza krawędź będzie miała wagę 0.