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.
Przecież to jest Dijkstra[0].
[0] https://www.geeksforgeeks.org/dijkstras-shortest-path-algorithm-using-priority_queue-stl/
EDIT: To nie Dijkstra.
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.