Najkrótsza ścieżka w grafie - dane są krawędzie grafu

0

Pytanie jaki algorytm zastosować aby wyznaczyć koszt najkrótszej ścieżki w grafie niezorientowanym. Program zaimplementowany ma być Javie.

Podane mam jedynie dane krawędzi w bazie danych - tabela składa się z wierszy. Każdy wiersz tabeli interpretowany jest jako opis krawędzi łączącej wierzchołki x oraz y oraz posiada atrybut p krawędzi oznaczjący maksymalną przepustowość na odcinku pomiędzy x a y.
Czyli każdy wiersz zawiera x, y, p i id takiej krawędzi.

Koszt transportu dla każdego z węzłów ścieżki jest to bezwzględna wartość różnicy przepustowości krawędzi ścieżki o końcach w tym
wierzchołku, czyli np. w przypadku węzła y przez który przechodzi ścieżka z wykorzystaniem krawędzi (x,y) oraz (y,z) o przepustowości odpowiednio Pxy i Pyz koszt transportu wyniesie | Pxy - Pyz |.

Nie za bardzo rozumiem jak mam obliczyć koszt danego węzła.

Poproszę o jakieś podpowiedzi/sugestie.

0

Oj coś późno sie zabrałeś, bo kolega @jacke http://4programmers.net/Forum/Java/239911-graf_niezorientowany już dawno prosił o tego samego gotowca ;]
Poza tym przysiągłbym że widziałem to zadanie jeszcze raz, z tydzień temu.
Wzór na liczenie kosztu węzła jest podany, nie ma tu nic do "rozumienia". Cel jest taki żeby ktoś nie ściągnął sobie gotowca z dijkstrą z internetu, tylko pomyślał chwilę nad implementacją. W rzeczywistości wielkiej różnicy nie ma, ale konieczne jest pamiętanie "skąd" przyszliśmy do danego węzła bo inaczej nie możemy obliczyć kosztu.

0

No właśnie nie rozumiem skąd wziąć koszt danego węzła.
user image

Mając dane w bazie jak na zdjęciu - 2 rekordy w bd.
koszt węzła X jest 0.
Jak obliczyć koszt dojścia do węzła Y(p-max przepustowość)?

0

o_O? Przecież od razu widać ze koszt jest zdefiniowany tylko dla węzła pośredniego! Nie ma czegoś takiego jak koszt przejścia z X do Y. Jest tylko koszt przejścia z X do Z przez Y.
Możesz to sobie transponować w taki sposób że każdą parę krawędzi zamieniasz na jedną krawędź a jej waga to właśnie ta podana wartść bezwzględna, wtedy to możesz juz puścic dowolny standardowy algorytm.

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