Wpis z mikrobloga

#algorytmy #programowanie #studbaza #grafy #kiciochpyta #pytanie #pytaniedoeksperta #tagujetogowno

Za pomocą algorytmu Dijkstry da się wyznaczyć najkrótszą ścieżkę między dwoma wierzchołkami grafu. Pytanie czy jest jakiś mądry sposób na znalezienie kolejnej najkrótszej ścieżki między tymi dwoma wierzchołkami - mamy skończoną ilość ścieżek między dwoma wierzchołkami posortowaną malejąco wg kosztu przejścia i ostatnia jest najkrótsza, to ja potrzebuję przedostatniej. Mam nadzieję, że mnie rozumiecie, bo trochę I cannot into polski ( ͡° ͜ʖ ͡°)
  • 5
  • Odpowiedz
  • Otrzymuj powiadomienia
    o nowych komentarzach

@franczi: Rozwiązanie mam troszkę toporne, ale może Ci pomoże:

Druga najkrótsza ścieżka musi różnić się od najkrótszej ścieżki co najmniej jednym odcinkiem (między dwoma wierzchołkami grafu). Skoro tak, to po wyznaczeniu najkrótszej ścieżki weź tyle grafów ile najkrótsza ma odcinków, z każdego grafu usuń jeden, inny, należący do najkrótszej ścieżki odcinek, dla każdego znajdź najkrótszą ścieżkę za pomocą algorytmu Dijkstry i wybierz najkrótszą z nich. I to będzie ta druga
  • Odpowiedz