Witam,
Mam następujący problem, dla którego nie mogę znaleźć szybko działającego rozwiązania, a mianowicie:
Wczytuję sobie graf w postaci listy incydencji.
Wszystkie krawędzie w grafie mają takie same wagi.
Następnie muszę dodać do tego grafu krawędzie w następujący sposób:
Tworzę krawędź pomiędzy dwoma wierzchołkami, nazwijmy je A i B jeżeli:
NIE ISTNIEJE taka krawędź oraz NAJKRÓTSZE przejście pomiędzy tymi dwoma wierzchołkami wymaga DOKŁADNIE JEDNEGO przejścia przez inny wierzchołek to znaczy, że tworzę krawędź pomiędzy wierzchołkami A i B jeżeli aktualnie najkrótsza ścieżka je łącząca wymaga przejścia tylko przez jeden inny wierzchołek czyli np. C.
Inaczej:
Istnieje ścieżka: A - C - B
To tworzę krawędź pomiędzy A i B, ponieważ najkrótsza ścieżka pomiędzy tymi dwoma wierzchołkami wymaga przejścia przez tylko jeden inny wierzchołek.
We wczytywanym grafie krawędzie nigdy nie krzyżują się oraz wczytywany graf jest spójny.
Tak się zastanawiam w jaki szybki sposób mógłbym sprawdzać, w których miejscach powinienem dodawać brakujące krawędzie. Aktualnie robię to tak, że sprawdzam po prostu każdy wierzchołek po kolei i jeżeli natrafię na kombinację, że np.: Wierzchołek_Sprawdzany, Wierzchołek_Sąsiad, Wierzchołek_Sąsiad_Sąsiada i nie ma krawędzi pomiędzy: Wierzchołek_Sprawdzany, a Wierzchołek_Sąsiad_Sąsiada to ją tworzę, bo aktualnie najkrótsza ścieżka łącząca te wierzchołki wymaga przejścia dokładnie przez jeden inny wierzchołek, a mianowicie: Wierzchołek_Sąsiad. Takie sprawdzanie po kolei tych możliwości daje bardzo dużą złożoność obliczeniową ;/. Ma ktoś jakiś inny pomysł na szybkie tworzenie brakujących krawędzi?
- przyklad.png (8 KB) - ściągnięć: 248