Tablica 2D - najkrótsza ścieżka o najmniejszym koszcie

Witam, na zajęcia mam przygotować program w języku PASCAL o następującej treśći:

Na podstawie podanej przez użytkownika planszy zawierającej pola o określonych
kosztach program powinien znaleźć ścieżkę pozwalającą na przejście całej planszy (od ustalonego „wejścia” do „wyjścia”) w taki sposób, aby łączny koszt mijanych pól był jak najniższy.

Po rozmowie z prowadzącym zajęcia dostałem konkretne wytyczne:
-program działa dla tablicy 2D o ustalonym i niezmiennym rozmiarze 5x5
-Ustalone wejście to lewy górny róg tablicy (indeksy [0][0]) a wyjście to prawy dolny róg (indeksy [4][4])
-użytkownik przy starcie programu podaje osobno dla każdego pola tej tablicy jakąś wartość liczbową (np. zakres wyboru to 0-9)
-w tablicy nie ma żadnych ścian, przeszkód
-poruszamy się kierunkami: DÓŁ, GÓRA, LEWO, PRAWO

Proszę Was o pomoc w algorytmie. Prowadzącym zasugerował, aby nie korzystać z Dijkstry. Ja znalazłem coś takiego:

http://warsztat.gd/wiki/Algorytm+wyszukiwania+najkr%C3%B3tszej+drogi+w+%C5%9Bwiecie+2D

Próbowałem zrobić ten algorytm w języku PASCAL, ale coś nie za bardzo mi wychodzi. Może znacie lepsze rozwiązanie tego problemu? Czy ten algorytm podany w linku wyżej mógłby być dobry dla tego zadania?

Z góry dziękuję za odpowiedzi. Pozdrawiam

A* jest stosunkowo prosty w implementacji (+istnieje wiele opisów, jak i gotowych kodów).

Proszę Was o pomoc w algorytmie.

Zadaj konkretne pytanie.

DFS

@Patryk27 A* wcale nie jest taka trywialna, bo trzeba o heurystyce myśleć :P
BFS jeśli chcesz zaklepać to "prosto" -> będzie miał może z 10 linijek.
Dijsktra jeśli chcesz mieć optymalną trasę.

Moją konkretną myślą była prośba o pomoc w wyborze jak najprostszego algorytmu do zrealizowania treści tego zadania. Z odpowiedzi rozumiem, że DFS się sprawdzi (znajdzie najkrótszą trasę od wejścia do wyjścia jak najmniejszym kosztem przejścia?)

Tak, ale dużo wygodniej będzie to zrobić jednak BFSem. Oba są zasadniczo równie proste w implementacji.

Czy jest gdzieś dostępny przykład BFS, który mogę przerobić na swoją wersję programu w PASCALu?

Na A=B+C też potrzebowałeś przykładu do przerobienia.

Co do przerobienia to chce tylko wiedzieć jak zaprezentować tablicę 2D jako graf. Mój obecny kod bez algorytmu wygląda następująco:

program project1;

uses crt;

type

    TPoint = record
        x : integer;
        y : integer;
     end;

    TCell = record
        flag : boolean;
        value : byte;
    end;

    TArr = array [0..4, 0..4] of TCell;


var
    i, j, c: integer;
    start, finish: TPoint;
    field : TArr;


procedure ShowField;
var
    i, j: integer;
begin
    for i := 0 to 4 do
    begin
        for j := 0 to 4 do
        begin
             write(field[i, j].value, ' ');
             field[i, j].flag:=FALSE;
        end;
        writeln;
    end;
end;


begin
    randomize;
    start.x:=0;
    start.y:=0;
    finish.x:=0;
    finish.y:=0;
    Writeln('Witaj w programie Zadanie nr 10!');
    Readln;
    for i := 0 to 4 do
        for j := 0 to 4 do
        begin
            ClrScr;
            Write('Podaj wartosc pola [',i,'][',j,']:= ');
            ReadLn(field[i, j].value);
        end;
end.

dodanie znacznika <code class="delphi"> - fp