Szukanie najtańszej trasy

Witajcie :)

Mam do rozgryzienia pewien problem.
Dysponuję kwadratową siatką i znam punkt startowy. Chcę dostać się do punktu X, który leży na prostej, która przecina w dowolnym miejscu siatkę. Koszty "jazdy" w każdej kratce są inne. Czy istnieje algorytm, który wyznaczyłby "najtańszą" drogę z punktu X do punktu na prostej? Warunkiem nie jest najkrótsza trasa ale właśnie najtańsza.
Czytałem o algorytmie A*, jednak tam konieczna jest znajomość punktu końcowego. W moim przypadku tych punktów jest wiele. Podobno działa w takich przypadkach algorytm Dijkstr'y, jednak nie wiem, czy odnajduje on najkrótszą czy najtańszą trasę.

W załączniku szkic opisujący problem :)

Proszę o Waszą pomoc, ja jestem laikiem jeżeli chodzi o sprawy związane z algorytmami.

Pozdrawiam :)

Do dowolnego punktu na tej prostej, czy do takiego gdzie będzie najtaniej? Ja bym puścił Dijkstrę dla każdego punktu na prostej i wybrał ten najtańszy. Dijkstra wyznacza minimalny koszt (w sensie wag krawędzi) dotarcia do każdego wierzchołka danego grafu (który nie ma ujemnych cykli) wychodząc z danego źródła.

Dokładnie tak. Algorytm powinien sam wybrać punkt, do którego trasa będzie najtańsza. Ważne, żeby ten punkt leżał na prostej.

Witam :)

Wracam do mojego zadania.
To, że Dijsktra podoła - rozumiem. Nie rozumiem jednak samej istoty działania tego algorytmu, nie mówiąc już o tym, że nie potrafię problemu w jakikolwiek sposób oprogramować. Czy zatem ktoś z Was mógłby podać dobry link (oczywiście najlepiej polski) lub napisać, od czego zacząć i jak mniej więcej przeprowadzać obliczenia, żeby dojść z punktu startowego do końcowego?

Będę bardzo wdzięczny.

Pozdrawiam :)

@Madm4n:
A czy ja mógłbym prosić, o taki kod do szukania najkrótszej drogi?
Mam tablicę dwuwymiarową array [1..25, 1..25] of Integer i jeżeli jest -1 to ściana, 0 to puste, i teraz jak znaleźć najkrótszą drogę z punktu np. 1, 13 do 25, 25. Próbowałem z dijkstrą ale jakoś nie wychodziło. Byłbym wdzięczny.