Badania Operacyjne- ujemne wartości łuków

Witam,
Proszę was serdecznie o pomoc w zadaniu z przedmiotu Badania Operacyjne.
Temat zadania to: Wyznaczanie drogi najkrótszej w acyklicznej sieci skierowanej. Przy konkretyzacji danych przyjąć ujemne wartości łuków.
I tu jest pies pogrzebany. Przegooglowałem prawie wszystko, ale nie znalazłem zbliżonych informacji na temat ujemnych wartości łuków. Z tego co rozumiem to jest to zadanie typu komiwojażera.

Czy jest ktoś w stanie udzielić mi cennych porad i wskazówek dotyczących tego zadania?
Niestety mam mało czasu na zaliczenie tego zadania, a utknąłem już na samym wymyśleniu zadania z powodu braku zrozumienia ujemnych łuków.

Z góry dziękuję za pomoc.

Pozdrawiam
Mateusz

Nie no gdzie tu jakis komiwojażer? To w ogóle nie ma nic wspólnego z żadnym Cyklem Hamiltona! Ja rozumiem że masz zadany skierowany ważony graf acykliczny i szukasz w nim ścieżki między dwoma zadanymi punktami i do tego służy algorytm Dijkstry (gdyby nie był ważony to i BFS by wystarczył). Nie radzi on sobie z grafami z ujemnymi cyklami (wtedy lepiej użyć Bellmana-Forda i stwierdzić czy w grafie taki cykl występuje) ale u ciebie graf w ogóle nie ma cykli więc ten problem nie występuje.

W ramach wyjaśnienia: ujemny cykl w grafie powoduje że mozesz w nieskończoność łazić tym cyklem i obniżać sumaryczny koszt ścieżki, więc zadanie nie ma rozwiązania.

Poza tym sam sobie tłumaczyłeś treść tego zadania? Bo nikt normalny nie mówi "łuki" tylko "krawędzie" i nie "sieć skierowana" a "graf skierowany".

tl;dr: algorytm Dijsktry lub algorytm Bellmana-Forda (wolniejszy ale dużo łatwiejszy w implementacji)

Dzieki za odpowiedź. Temat zadania był drukowany na kartce przez Profesora, wiec to on opisał krawedzie jako łuki etc.
Niestety z racji problemów zdrowotnych nie mogłem być na wykładach u tego Profesora i jestem kompletnie zielony.
O algorytmie Dijkstry itp. czytałem. Ale kompletnie nie wiem jak zaczepić sensowną treść zadania do tego.
Acykliczna sieć skierowana- tzn jednokierunkowa, bez cykli i do tego z ujemnymi wartościami krawedzi.
Dijkstra sie tu nie nada, ale nie jestem pewien czy powinienem to zrobić Bellmanem- Fordem czy też jakimś innym.
Nie mam pojecia co może oznaczać ujemna wartość w długości drogi.
Czy mógłby ktoś mi podsunąć treść zadania z takimi własnościami tematu pracy? Przeszukałem google i nie znalazłem przykładu grafu ze wszystkimi wartościami ujemnymi, a tak rozumiem temat pracy. Jak również nie znalazłem zadania lub grafu acyklicznego skierowanego z wartościami ujemnymi. :( Gdyby temat pracy był bez wartości ujemnych nie było by problemu :(

Nie no chłopie ty chyba w ogóle przespałeś cały semestr bo z tego co piszesz wynika że nie ogarniasz NIC :D Co wiecej przespałeś też chyba zajecia z matematyki dyskretnej...
No ale po kolei:

1. Zaręczam że Dijkstra sie nada.
2. Skierowanie grafu oznacza po prostu że każda krawędź w grafie ma kierunek, wiec krawędź (1,2) oznacza przejścia z wierzchołka 1 do 2, ale niekoniecznie musi istnieć krawędź powrotna.
3. O jejku, ujemna wartość drogi może oznaczać na przykład ile paliwa spalasz pokonując daną krawędź. Im więcej krawędzi miniesz tym więcej "odejmie" ci paliwa. Wyobraź sobie że graf określa połączenia drogowe między zbiorem miast. Ulice są jednokierunkowe i tak te ulice pobudowano że nie ma tam żadnego cyklu, tzn nie da sie jeździć w kółko. Masz przejechać z miasta A do B i chcesz zużyć jak najmniej paliwa. Ot całe zadanie.

I nie rozumiem co to znaczy "nie znalazłem grafu...". Grafy to ty sobie pewnie musisz generować losowo do tego zadania.