Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?

Wyszukiwanie "najbardziej wartościowej" krawędzi grafu

Ostatnio zmodyfikowano 2016-01-28 10:21
Autor Wiadomość
OSA_PL
Temat założony przez niniejszego użytkownika
Wyszukiwanie "najbardziej wartościowej" krawędzi grafu
» 2016-01-27 22:47:31
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.
P-144089
DejaVu
» 2016-01-28 10:21:20
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
waga = - waga;
).

/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.
P-144100
« 1 »
  Strona 1 z 1