Kamis, 19 Juni 2014

Metode Djikstra pada Matematika Diskrit

Algoritma program Pascal untuk Metode Djikstra pada Matematika Diskrit


program djikstra;

uses wincrt;

var

   i, j, k, n, x, y, cek: integer;

   v                    : array [1..10,1..10] of integer;

   nilai, hasil         : array [1..10] of integer;

label 1, 2, 3;



Begin

1:

  {Input}

  writeln('Program Pencarian Lintasan Terpendek');

  write('Masukkan besar matriks adjacency (n x n): ');readln(n);

  for i:= 1 to n do

  begin

       for j:= 1 to n do

       begin

            if j <> i then

            begin

                 writeln('Masukkan 0 jika tidak hubungan antar vertex.');

                 write('V',i,'V',j,' = ');readln(v[i,j]);

                 clrscr;

            end;

       end;

  end;




2:

  {Cetak Matriks Adjacency}

  write('    ');

  for i:= 1 to n do

  begin

       write('  V',i);

  end;

  writeln;

  for i:= 1 to n do

  begin

       write('V',i,'|');

       for j:= 1 to n do

       begin

            if v[i,j-1] < 10 then write('   ',v[i,j]);

            if v[i,j-1] >= 10 then write('  ',v[i,j]);

       end;

       writeln('   |');

  end;



  if cek = 0 then

  begin

       writeln;

       writeln('Benarkan ini matriks adjacency yang anda inginkan?');

       writeln('1. Ya   2. Tidak');readln(k);

  end;



  if cek = 0 then

  begin

       {Jika dipilih ya, maka proses cetak matriks diulangi}

       if k = 1 then

       begin

            cek:= 1;

            clrscr;

            goto 2;

       end;



       {Jika dipilih tidak, maka proses input akan diulangi}

       if k = 2 then

       begin

            for i:= 1 to n do

            begin

                 for j:= 1 to n do

                 begin                                               

                      v[i,j]:= 0;

                 end;

            end;

            clrscr;

            goto 1;

       end;

  end;



  {Input vertex awal dan akhir}

  writeln;

  write('Masukkan vertex awal : V');readln(x);

  write('Masukkan vertex akhir: V');readln(y);



  writeln;

  write('    V1');

  for i:= 2 to n do

  begin

       write('      V',i);

  end;

  writeln;

  for i:= 1 to n do

  begin

       if i <> x then write('| -,0,0 ');

       if i = x then write('| 0,1,1 ');

  end;

  writeln('|');

  hasil[x]:= 1;

  nilai[x]:= 0;



  repeat

        {Pencarian pivot baru}

        k:= nilai[x];

        for i:= 1 to n do

        begin

             if hasil[i] <> 1 then

             begin

                  if v[x,i] <> 0 then

                  begin

                       if nilai[i] = 0 then nilai[i]:= v[x,i] + k;

                       if nilai[i] <> 0 then

                       begin

                            if v[x,i] + k < nilai[i] then nilai[i]:= v[x,i] + k;

                       end;

                  end;

             end;

        end;



        {Cetak nilai pivot}

        for i:= 1 to n do

        begin

             if hasil[i] <> 1 then

             begin

                  if nilai[i] <> 0 then

                  begin

                       if nilai[i] < 10 then write('| ',nilai[i],',0,0 ');

                       if nilai[i] >= 10 then write('|',nilai[i],',0,0 ');

                  end;

                  if nilai[i] = 0 then write('| -,0,0 ');

             end;



             if hasil[i] = 1 then

             begin

                  if nilai[i] <> 0 then

                  begin

                       if nilai[i] < 10 then write('| ',nilai[i],',1,0 ');

                       if nilai[i] >= 10 then write('|',nilai[i],',1,0 ');

                  end;

                  if nilai[i] = 0 then write('| ',nilai[i],',1,0 ');

             end;

        end;

        writeln('|');



        cek:= 10000;

        for i:= 1 to n do

        begin

             if hasil[i] <> 1 then

             begin

                  if nilai[i] <> 0 then

                  begin

                       if nilai[i] < cek then

                       begin

                            cek:= nilai[i];

                            x:= i;

                       end;

                  end;

             end;

        end;

        hasil[x]:= 1;

        nilai[x]:= cek;



        {Cetak pivot baru}

        for i:= 1 to n do

        begin

             if i = x then write('| ',nilai[i],',1,1 ');

             if i <> x then

             begin

                  if hasil[i] <> 1 then

                  begin

                       if nilai[i] <> 0 then

                       begin

                            if nilai[i] < 10 then write('| ',nilai[i],',0,0 ');

                            if nilai[i] >= 10 then write('|',nilai[i],',0,0 ');

                       end;

                       if nilai[i] = 0 then write('| -,0,0 ');

                  end;

                  if hasil[i] = 1 then

                  begin

                       if nilai[i] <> 0 then

                       begin

                            if nilai[i] < 10 then write('| ',nilai[i],',1,0 ');

                            if nilai[i] >= 10 then write('|',nilai[i],',1,0 ');

                       end;

                       if nilai[i] = 0 then write('| ',nilai[i],',1,0 ');

                  end;

             end;

        end;

        writeln('|');

  until x = y;

End.



Preview Program:

Tidak ada komentar:

Posting Komentar

Related Posts Plugin for WordPress, Blogger...