Najkrótsza o najmniejszej sumie wag po krawędizach malejacych

Odpowiedz Nowy wątek
2019-06-02 13:11
0

Mam zadany graf G (V, E) gdzie krawędzie są parami różne. Mam napisać algorytm który dla zadanych wierzchołków x i y wyznaczy ścieżkę o najmniejszej sumie wag, która prowadzi z x do y po krawędziach o malejących wagach.

Pozostało 580 znaków

2019-06-02 15:59
0

Przecież to jest Dijkstra[0].
[0] https://www.geeksforgeeks.org[...]thm-using-priority_queue-stl/

EDIT: To nie Dijkstra.


edytowany 1x, ostatnio: lion137, 2019-06-02 16:21
Nie, nie jest. Nigdzie nie masz warunku na malejące wagi krawędzi a to nie jest takie trywialne do dodania. - Shalom 2019-06-02 16:20
Rzeczywiście, nie doczytałem. - lion137 2019-06-02 16:21

Pozostało 580 znaków

2019-06-03 09:09
1

Da się to zrobić Dijkstra, na odwróconym grafie gdzie idziemy od węzła końcowego do początkowego, tak będzie wygodniej.
Zamiast pojedynczej wartości oznaczającej odległość w każdym węźle trzymamy listę par (odległość, minimalna waga krawędzi użyta do osiągnięcia danej odległości),
na listę/do kolejki dodajemy tylko wtedy kiedy osiągnęliśmy mniejszą odległość, lub większa odległość ale przy użyciu krawędzi o mniejszej wadze.
Jak przetwarzamy daną parę pobraną z kolejki to bierzemy pod uwagę tylko krawędzie o większej wadze niż to co mamy w danej parze.

Złożoność tego jest straszna, ale zdarzyło mi się coś podobnego popełnić na hackerranku i przechodziło.


#Dżunior React Devloper wanna be#

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0