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

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.

0

Przecież to jest Dijkstra[0].
[0] https://www.geeksforgeeks.org/dijkstras-shortest-path-algorithm-using-priority_queue-stl/

EDIT: To nie Dijkstra.

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.

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