Самый дешевый путь. Графы.

[jocry]

Здравствуйте. Есть рисунок графа его необходимо переложить в понятный вид делфи и найти самый дешевый путь к примеру из точки 1 в точку 3 (1,2,4,3 = 1100). Цена А-Б, Б-А одинаковая , но путь может быть однонаправленным( из А можно попасть в Б, а наоборот нельзя).Я так понял необходимо найти все возможные пути из пункта 1 в пункт 3 и выбрать из них тот путь который будет являться самым дешёвым.

[KingOfNothing]

Вот посмотри, консольное приложение на Делфи, граф задаётся массивом, например
map[1,2]:=10 - стоимость пути из 1 в 2 = 10

program OptimalWay;

{$APPTYPE CONSOLE}

uses
  SysUtils;

const n=9;
var map:array [1..n,1..n] of integer; {Карта: map[i,j] не 0, якщо точки i та j з'єднані}
    road:array [1..n] of integer; {Маршрут}
    incl:array [1..n] of boolean; {incl[i]=true, якщо точка і належить до масиву road}
    length:array [1..n*n] of integer; {довжина маршруту}

start,finish:integer;
i,j,lenpointer:integer;

procedure step(s,f,p:integer);
var c,i:integer;
begin
if s=f then
    begin
    write('Way # ', lenpointer, ':');
        for i:=1 to p-1 do
        begin
            write(road[i],'');
            length[lenpointer]:=length[lenpointer]+map[road[i],road[i+1]];
        end;
    writeln;
    writeln('Length = ', length[lenpointer]);
    writeln;
    lenpointer:=lenpointer+1;
    end
else
    begin
    for c:=1 to n do
    begin
        if (map[s,c]<>0) and (not incl[c])
            then
            begin
                road[p]:=c;
                incl[c]:=True;
                step(c,f,p+1);
                incl[c]:=false;
                road[p]:=0;
            end;
      end;
      end;
end;

function min:integer;
var min1,min2,i:integer;
begin
min1:=length[1];
min2:=1;
for i:=2 to n*n do
  begin
    if length[i]=0 then break;
    if min1 > length[i] then
    begin
        min1:=length[i];
        min2:=i;
    end;
  end;
min:=min2;
end;

begin
lenpointer:=1;

{ініціалізація масивів}
for i:=1 to n do
begin
    road[i]:=0;
    incl[i]:=false;
end;

for i:=1 to n*n do
  length[i]:=0;

for i:=1 to n do for j:=1 to n do map[i,j]:=0;
{Введення значень карти}
map[1,2]:=12; map[2,1]:=12;
map[1,3]:=5; map[3,1]:=5;
map[1,4]:=8; map[4,1]:=8;
map[1,5]:=9; map[5,1]:=9;
map[2,6]:=3; map[6,2]:=3;
map[2,9]:=4; map[9,2]:=4;
map[3,6]:=5; map[6,3]:=5;
map[3,7]:=6; map[7,3]:=6;
map[4,6]:=8; map[6,4]:=8;
map[4,8]:=9; map[8,4]:=9;
map[4,9]:=8; map[9,4]:=8;
map[5,6]:=10; map[6,5]:=10;
map[5,9]:=6; map[9,5]:=6;
write('Enter Start and Finish dots ->');
readln(start,finish);
road[1]:=start;
incl[start]:=true;
step(start,finish,2);

writeln('Optimal Way is way # ', min);
writeln('Press <Enter> to exit');
readln;

end.