biorąc pod uwagę nieskierowany ważony wykres G i dwa wierzchołki: początek wierzchołka i koniec wierzchołka

jaki jest najbardziej efektywny algorytm, który znajduje najkrótszą ścieżkę od początku do końca, z możliwością zmiany wagi o jedną krawędź na zero?

EDYCJA: znam algorytm dijkstra, ale jak już powiedziałem, sytuacja jest inna w tym problemie: możemy obrócić jedną krawędź na zero,

chcę wiedzieć, jak skutecznie rozwiązać ten problem, w rzeczywistości jednym sposobem jest obracanie ciężarów krawędzi do zera iteracyjnie! i zastosuj algorytm dijkstra na każdym kroku, ale szukam bardziej efektywnego sposobu

dzięki