Czas najszybszego przejścia

Rysunek przedstawia układ szlaków w centralnej Polsce. Każdy z odcinków opisany jest dwoma liczbami: górna jest czasem w minutach pokonywania danego odcinka zgodnie ze strzałką, a dolna w kierunku przeciwnym. Strzałki nie oznaczają, że graf jest skierowany, ale tylko pomaga rozróżnić wagi krawędzi.

Proszę wskazać algorytm, który pozwoli na zejście do Kuźnic. Proszę określić czas najszybszego przejścia pokazując przebieg algorytmu.

Pytanie 1: z jednej strony jest napisane, że strzałki nie oznaczają, że graf jest skierowany więc Dijkstry odpada, a z drugiej że oznaczają czas pokonania w danym kierunku co sugeruje, że jest skierowany - to jakiego algorytmu tu użyć?

Pytanie 1: z jednej strony jest napisane, że strzałki nie oznaczają, że graf jest skierowany więc Dijkstry odpada, a z drugiej że oznaczają czas pokonania w danym kierunku co sugeruje, że jest skierowany - to jakiego algorytmu tu użyć?

Czemu to czy jest skierowany czy nie miałoby wykluczać Dijkstrę?

Ja bym powiedział, że to jest graf skierowany w którym między wierzchołkami masz zawsze 2 strzałki w dwie strony. Czy to sprawia, że podpada to pod definicję grafu nieskierowanego - powiedziałbym, że tutaj nie, bo różne kierunki mają różne wagi. Ale to już semantyka.

Zamodeluj to po prostu tak, że masz dwie strzałki w dwie strony.

Zawrat -> Świnica w rzeczywistości jest szlakiem jednokierunkowym ;-) Dijkstrę by wykluczyło przy ujemnych wagach, a tu takich nie ma.

Możliwe, że chodzi o znalezienie najkrótszych ścieżek z Kużnic do pozostałych węzłów, ale że chodzi o zejście, to trzeba by odwrócić krawędzie w oryginalnym grafie.
Inaczej znajdziesz najkrótsze wejścia na szczyty. Jeśli wagi byłyby ujemne to algorytm Bellmana-Forda.

@tkowal Zapoznaj się z : https://visualgo.net/en/sssp Wierzchołkiem początkowym byłyby Kuźnice, bo chcesz mieć czasy zejścia do Kuźnic, więc szukasz najkrótszej drogi z Kuźnic do pozostałych wierzchołków. A że chodzi o zejście, to odwracasz strzałki w grafie. Na podanej stronie masz przegląd algorytmów do tego problemu.

tkowal napisał(a):

"Rysunek przedstawia układ szlaków w centralnej Polsce"

W tej kwestii bym mocno polemizował :-)
Może być to prawda ale dopiero jak podbijemy Czechy, Słowację, Austrię i Węgry.
No chyba, że Kuźnica - to ta wiocha na Półwyspie Helskim zaraz za Chałupami :-)