Algoritma Dijkstra dan Kruskal

1. Algoritma Dijkstra 

Algoritma dijkstra (pencarian jalur terpendek), merupakan suatu algoritma yang disebut juga sebagai single-source shortest path yang digunakan dalam menentukan jalur terpendek dari simpul sumber menuju simpul tujuan berdasarkan bobot pada sisi. Bobot pada sisi dapat berupa jarak, waktu, biaya, ataupun bobot yang lainnya. Algoritma dijkstra bekerja dengan cara mengujungi semua semua simpul-simpul yang terdapat pada graf yang dimulai pada simpul sumber. Secara berulang, algoritma ini akan memilih simpul-simpul terdekat dan menghitung total bobot semua sisi yang dilewati untuk mencapai simpul tujuan.

Algoritma ini bertujuan untuk menemukan jalur terpendek berdasarkan bobot terkecil dari satu titik ke titik lainnya. Misalkan titik mengambarkan gedung dan garis menggambarkan jalan, maka algoritma Dijkstra melakukan kalkulasi terhadap semua kemungkinan bobot terkecil dari setiap titik.

Pertama-tama, tentukan titik mana yang akan menjadi node awal, lalu beri bobot jarak pada node pertama ke node terdekat satu per satu, Dijkstra akan melakukan pengembangan pencarian dari satu titik ke titik lain dan ke titik selanjutnya tahap demi tahap. Berikut adalah urutan logika dari algoritma Dijkstra.

a.       Beri nilai bobot atau nilai jarak untuk setiap satu titik ke titik lainnya, lalu set nilai 0 pada node awal dan nilai tak hingga terhadap node lain yang belum terisi.

b.      Set semua node sebagai “Belum terjamah” dan set node awal sebagai “Node keberangkatan”.

c.       Dari node keberangkatan, pertimbangkan node tetangga yang belum terjamah dan hitung jaraknya dari titik keberangkatan. Sebagai contoh, jika titik keberangkatan A ke B memiliki bobot jarak 6 dan dari B ke node C berjarak 2, maka jarak ke C melewati B menjadi 6+2=8. Jika jarak ini lebih kecil dari jarak sebelumnya, yang telah terekam sebelumnya. Maka hapus data lama, simpan ulang data jarak dengan jarak yang baru.

d.      Saat kita selesai mempertimbangkan setiap jarak terhadap node tetangga, tandai node yang telah terjamah sebagai “Node terjamah”. Node terjamah tidak akan pernah di cek kembali, jarak yang disimpan adalah jarak terakhir dan yang paling minimal bobotnya.

e.       Set “Node belum terjamah” dengan jarak terkecil dari node keberangkatan  sebagai “Node Keberangkatan” selanjutnya, dan ulangi kembali step c.

                       Dibawah ini penjelasan langkah per langkah pencarian jalur terpendek secara rinci                               dimulai dari node awal sampai node tujuan dengan nilai jarak terkecil.

a.   Node awal 1, Node tujuan 5. Setiap edge yang terhubung antar node telah diberi nilai.

b.   Dijkstra melakukan kalkulasi terhadap node tetangga yang terhubung langsung dengan node keberangkatan yaitu node 1, dan hasil yang didapat adalah node 2, karena bobot nilai node 2 paling kecil dibandingkan nilai pada node lain, nilai = 7 (0+7).

c.       Node 2 diset menjadi node keberangkatan dan ditandai sebagai node yang telah terjamah. Dijkstra melakukan kalkulasi kembali terhadap node-node tetangga yang terhubung langsung dengan node yang telah terjamah. Dan kalkulasi dijkstra menunjukan bahwa node 3 yang menjadi node keberangkatan selanjutnya karena bobotnya yang paling kecil dari hasil kalkulasi terakhir, nilai 9 (0+9).

d.       Perhitungan berlanjut dengan node 3 ditandai menjadi node yang telah terjamah. Dari semua node tetangga belum terjamah yang terhubung langsung dengan node terjamah, node selanjutnya yang ditandai menjadi node terjamah adalah node 6 karena nilai bobot yang terkecil, nilai 11 (9+2).

e. Node 6 menjadi node terjamah, dijkstra melakukan kalkulasi kembali, dan menemukan bahwa node 5 atau node tujuan telah tercapai lewat node 6. Jalur terpendeknya adalah 1-3, 6-5, dan niilai bobot yang didapat adalah 20 (11+9). Bila node tujuan telah tercapai maka kalkulasi dijkstra dinyatakan selesai.

Contoh Program 

#include <cstdlib>
#include <iostream>
#define max 20
#define infinity 9999

using namespace std;
class dijkstra
{
private:
int n,graph[max][max],colour[max],start,distance[max],predecessor[max];
         enum {green,yellow,red};
      public:
             void read_graph();
             void initialize();
             int select_min_distance_lable();
             void update(int);
             void output();
             void function();
      };
void dijkstra::read_graph(){
     cout<<"masukkan jumlah node = ";
     cin>>n;
     cout<<"masukkan nilai matrik untuk graf ::\n";
     int i,j;
     for(i=1;i<=n;i++){
                       for(j=1;j<=n;j++){
                                         cout<<"["<<i<<"],["<<j<<"]=";
                                         cin>>graph[i][j];}}
     for(i=1;i<=n;i++){
    colour[i]=green;}
     cout<<"masukkan vertex mulai :: ";
     cin>>start;
     }
void dijkstra::initialize(){
     for(int i=1;i<=n;i++){
             if(i==start){
                          distance[i]=0;}
             else{distance[i]=infinity;}
     }
     for(int j=1;j<=n;j++){
             if(graph[start][j]!=0){
                                    predecessor[j]=start;}
             else{predecessor[j]=0;}
     }
}
int dijkstra::select_min_distance_lable(){
    int min=infinity;
    int p=0;
    for(int i=1;i<=n;i++){
            if(colour[i]==green){
                                 if(min>=distance[i]){
                                                   min=distance[i];
                                                   p=i;
                                                   }
                                 }
            }
    return p;
    }
void dijkstra::update(int p){
     cout<<"\nupdate jarak = \n";
     for(int i=1;i<=n;i++){
            if(colour[i]==green){
                     if(graph[p][i]!=0){
                                   if(distance[i]>graph[p][i]+distance[p]){
                                              distance[i]=graph[p][i]+distance[p];
                                                        predecessor[i]=p;
                                                                                             }
                                                     }
                                  }
             cout<<distance[i]<<'\t';
             }
     }
void dijkstra::output()
{
 cout<<"****** The final paths and the distances are ******\n\n";

 for(int i=1;i<=n;i++)
 {
  if(predecessor[i]==0 && i!=start)
  {
   cout<<"path does not exists between "<<i<<" and the start vertex "
    <<start<<endl;
   exit(1);
  }
  cout<<"path for node "<<i<<" is ::\n";
  int j=i;
  int array[max];
  int l=0;
  while(predecessor[j]!=0)
  {
   array[++l]=predecessor[j];
   j=predecessor[j];
  }
 for(int k=l;k>=1;k--)
  cout<<array[k]<<"->";
  cout<<i<<endl;
  cout<<"distance is "<<distance[i]<<endl<<endl<<endl;
 }
}
void dijkstra::function()
{
cout<<"\n**********************************************************************\n";
 cout<<"*This program is to implement dijkstra’s algorithm using colour codes* \n";
cout<<"**********************************************************************\n\n";
 read_graph();
 initialize();  //repeate until all nodes become red
 int flag=0;
 int i;
 cout<<"\n\n******** The working of the algorithm is **********\n\n";
 for(i=1;i<=n;i++)
  if(colour[i]!=red)
   flag=1;
 cout<<"The initial distances are ::\n";
 for(i=1;i<=n;i++)
  cout<<distance[i]<<'\t';
 cout<<endl;
 while(flag)
 {
  int p=select_min_distance_lable();
  cout<<"\nThe min distance lable that is coloured yellow is "<<p;
  colour[p]=yellow;
  update(p);
   cout<<"\nnode ="<<p<<" is coloured red "<<endl;
  colour[p]=red;

  flag=0;
  for(i=1;i<=n;i++)
   if(colour[i]!=red)
    flag=1;
  cout<<endl<<endl<<endl;
 }
 output();
}
int main(int argc, char *argv[])
{
    dijkstra d;
 d.function();
    system("PAUSE");
    return EXIT_SUCCESS;
}

1. Algoritma Kruskal

 Algoritma kruskal adalah sebuah algoritma dalam teori graf yang mencari sebuah minimum spanning tree untuk sebuah graf berbobot yang terhubung. Ini berarti menemukan subset dari tepi yang membentuk sebuah pohon yang mencakup setiap titik , di mana berat total dari semua tepi di atas pohon diminimalkan.. Jika grafik tidak terhubung, maka harus menemukan hutan rentang minimum atau pohon rentang minimum untuk setiap komponen terhubung. Algoritma Kruskal juga tergolong algoritma Greedy dalam teori graf yang digunakan untuk mencari minimum spanning tree. Algoritma ini pertama kali muncul pada tahun 1956 dalam sebuah tulisan yang ditulis oleh Joseph Kruskal. Algoritma Kruskal adalah contoh dari algoritma rakus . Algoritma ini pertama kali muncul dalam Prosiding American Mathematical Society , hal 1956.

Dasar pembentukan algoritma Kruskal berasal dari analogi growing forest. Growing forest maksudnya adalah untuk membentuk pohon merentang minimum T dari graf G adalah dengan cara mengambil satu per satu sisi dari graf G dan memasukkannya ke dalam pohon yang telah terbentuk sebelumnya. Seiring dengan berjalannya iterasi untuk setiap sisi, maka forest akan memiliki pohon yang semakin sedikit. Oleh sebab itu, maka analogi ini disebut dengan growing forest. Algoritma Kruskal akan terus menambahkan sisi-sisi ke dalam hutan yang sesuai, hingga akhirnya tidak ada lagi forest melainkan hanya sebuah pohon yang merentang minimum.

Graph adalah kumpulan dua himpunan, yaitu himpunan titik ( vertex/simpul/node ) dan kumpulan dari garis ( edge ). Tree merupakan graph tak berarah yang terhubung dan tidak mengandung sirkuit. Sirkuit sendiri ialah simpul awal = simpul akhir.

Secara Umum  Algoritma Kruskal ditulis :

1.      T masih kosong.

2.      Pilih sisi (i,j) dengan bobot minimum.

3.      Pilih sisi (i,j) dengan bobot minimum, berikutnya yang tidak membentuk cycle di T, tambahkan (i,j) ke T.

4.      Ulangi langkah 3 sebanyak (n-2) kali.

5.      Total langkah (n-1) kali.

Sifat Algoritma Kruskal adalah sebagai berikut.

1.      Ia bekerja tidak hanya dengan grafik yang terarah.

2.      Ia bekerja dengan bobot dan dengan grafik tidak tertimbang.

3.      Kruskal adalah jenis algoritma rakus yang menghasilkan solusi optimal MST.

Terdapat dua macam algoritma tipe greedy yang dapat memenuhi pemecahan masalah pohon merentang ini. Yaitu algoritma Prim dan algoritma kruskal, namun dalam laporan ini lebih menjelaskan tentang algoritma kruskal disbanding algoritma prim. Berikut adalah kelebihan dan kekurangan algoritma Kruskal dibanding algoritma prim.

a.       Kelebihan Algoritma Kruskal

Kelebihan algoritma Kruskal dibanding algoritma prim adalah sebagai berikut :

Sangat cocok diterapkan saat graf memiliki sisi berjumlah sedikit namun memiliki sangat banyak simpul, karena orientasi kerja algoritma ini adalah berdasarkan pada urutan bobot sisi, tidak berdasarkan simpul.

b.      Kekurangan Algoritma Kruskal

Beberapa hal yang menjadi kekurangan algoritma kruskal dibanding algoritma prim yaitu :

Kurang cocok digunakan saat graf lengkap atau graf mendekati lengkap, dimana setiap simpul terhubungkan dengan semua simpul yang lain. Karena algoritma Kruskal menitikberatkan pada pencarian sisi, dimana sisi-sisi tersebut harus diurutkan dan ini memakan waktu yang tidak sedikit.

Berikut adalah contoh penyelesaian kasus minimun spanning tree dengan algoritma kruskal, diketahui sebuah graf berbobot seperti gambar dibawah ini.

Bobot  Ruas               

15        D,E                 

9          B,D     E,F     

8          B,C      B,E      F,G

7          A,D     C,E     

6          A,B     E,G     

5          D,F                 

Peyelesaian :

      1.      Mula-mula, buat sekumpulan titik G hanya terdiri dari simpul-simpul saja.

      2.  Urutkan Ruas dari bobot kecil ke besar (DF, AB, EG, AD, CE, BC, BE, FG, BD, EF, DE),                  kemudian berdasarkan urutan tersebut, kita menambahkan ruas dengan mencegah terbentuknya           sirkuit.

Contoh Program

#include<stdio.h>
#define MAX 30

typedef struct edge
{
 int u,v,w;
}edge;

typedef struct edgelist
{
 edge data[MAX];
 int n;
}edgelist;

edgelist elist;

int G[MAX][MAX],n;
edgelist spanlist;

void kruskal();
int find(int belongs[],int vertexno);
void union1(int belongs[],int c1,int c2);
void sort();
void print();

 main()
{
 int i,j,total_cost;

 printf("\nMasukkan jumlah simpul:");

 scanf("%d",&n);

 printf("\nMasukkan matrix:\n");

 for(i=0;i<n;i++)
  for(j=0;j<n;j++)
   scanf("%d",&G[i][j]);

 kruskal();
 print();
}
void kruskal()
{
 int belongs[MAX],i,j,cno1,cno2;
 elist.n=0;

 for(i=1;i<n;i++)
  for(j=0;j<i;j++)
  {
   if(G[i][j]!=0)
   {
    elist.data[elist.n].u=i;
    elist.data[elist.n].v=j;
    elist.data[elist.n].w=G[i][j];
    elist.n++;
   }
  }

 sort();

 for(i=0;i<n;i++)
  belongs[i]=i;

 spanlist.n=0;

 for(i=0;i<elist.n;i++)
 {
  cno1=find(belongs,elist.data[i].u);
  cno2=find(belongs,elist.data[i].v);

  if(cno1!=cno2)
  {
   spanlist.data[spanlist.n]=elist.data[i];
   spanlist.n=spanlist.n+1;
   union1(belongs,cno1,cno2);
  }
 }
}

int find(int belongs[],int vertexno)
{
 return(belongs[vertexno]);
}

void union1(int belongs[],int c1,int c2)
{
 int i;

 for(i=0;i<n;i++)
  if(belongs[i]==c2)
   belongs[i]=c1;
}

void sort()
{
 int i,j;
 edge temp;

 for(i=1;i<elist.n;i++)
  for(j=0;j<elist.n-1;j++)
   if(elist.data[j].w>elist.data[j+1].w)
   {
    temp=elist.data[j];
    elist.data[j]=elist.data[j+1];
    elist.data[j+1]=temp;
   }
}

void print()
{
 int i,cost=0;

 for(i=0;i<spanlist.n;i++)
 {
  printf("\n%d\t%d\t%d",spanlist.data[i].u,spanlist.data[i].v,spanlist.data[i].w);
  cost=cost+spanlist.data[i].w;
 }

 printf("\n\nBiaya pohon merentang=%d",cost);
}

Buble Sort dan Quick Sort C++

kali ini kita akan membahas metode pengurutan mengenai Algoritma Buble Sort dan Quick Sort :

1.  Buble Sort

Pengurutan merupakan proses dasar yang ada dalam algoritma dan stuktur data. Terdapat banyak algoritma pengurutan yang sering digunakan, namun pada tulisan kali ini akan dibahas mengenai dasar algoritma Bubble Sort. Algortima ini merupakan algortima pengurutan sederhana dan biasanya dipelajari sebagai pokok bahasan seputar pengurutan.

Algoritma Bubble Sort ini merupakan proses pengurutan yang secara berangsur-angsur berpindah ke posisi yang tepat karena itulah dinamakan Bubble yang artinya gelembung. Algoritma ini akan mengurutkan data dari yang terbesar ke yang terkecil (ascending) atau sebaliknya (descending).

Secara sederhana, bisa didefenisikan algoritma Bubble Sort adalah pengurutan dengan cara pertukaran data dengan data disebelahnya secara terus menerus sampai dalam satu iterasi tertentu tidak ada lagi perubahan.

Untuk belajar algoritma Bubble Sort ini kita hanya perlu memahami cara yang digunakan untuk mengurutkan data, sederhananya algoritma ini menggunakan perbandingan dalam operasi antar elemennya. Di bawah ini merupakan gambaran dari algoritma Bubble Sort dengan array “3 1 4 2 8”.

Proses pertama

(3 1 4 2 8) menjadi (1 3 4 2 8)

(1 3 4 2 8) menjadi (1 3 4 2 8)

(1 3 4 2 8) menjadi (1 3 2 4 8)

(1 3 2 4 8) menjadi (1 3 2 4 8)

Proses kedua

(1 3 2 4 8) menjadi (1 3 2 4 8)

(1 3 2 4 8) menjadi (1 2 3 4 8)

(1 2 3 4 8) menjadi (1 2 3 4 8)

(1 2 3 4 8) menjadi (1 2 3 4 8)

Proses ketiga

(1 2 3 4 8) menjadi (1 2 3 4 8)

(1 2 3 4 8) menjadi (1 2 3 4 8)

(1 2 3 4 8) menjadi (1 2 3 4 8)

(1 2 3 4 8) menjadi (1 2 3 4 8)

Jika kita perhatikan proses diatas, para proses kedua data sudah terurut dengan benar. Tetapi algoritma Bubble Sort tetap berjalan hingga proses kedua berakhir. Proses ketiga masih terus berjalan karena pada algoritma Bubble Sort maksud terurut itu adalah tidak ada satupun penukaran pada suatu proses. Proses ketiga ini dilakukan untuk verifikasi data.

Algoritma Bubble Sort ini mempunyai kelebihan dan kekurangan, untuk kelebihannya metode ini merupakan metode paling sederhana untuk mengurutkan data. Selain sederhana, algoritma Bubble Sort mudah dipahami. Sementara itu, kekurangannya terletak pada efisiensi.

             Bubble Sort ini merupakan metode pengurutan yang tidak efisien karena ketika mengurutkan               data yang sangat besar akan sangat lambat prosesnya. Selain itu, jumlah pengulangan akan                   tetap sama jumlahnya meskipun data sudah cukup terurut.

 Listing program

#include <iostream>
using namespace std;
int main()
{
    char pil,sl;
    int i,n,j,Buble;
    int data[10];
    up:
    cout<<"Masukkan Jumlah Data : ";cin>>n;
    for(i=0; i<n; i++)
    {
        cout<<"Data ke - "<<i+1<<" : " ; cin >>data[i];
    }
    up1:
    cout <<"Pilih Urutan Data "<<endl;
    cout <<"1. Ascending "<<endl;
    cout <<"2. Descending"<<endl;
    cout <<"Pilihan Pencarian(1/2) : "; cin >>pil;
    if(pil =='1')
    {
        cout<<"Anda Memilih Urutan Data Ascending "<<endl;
        for(i=0; i<=n-2; i++)
        {
            for(j=n-1; j>=i+1; j--)
            {
                if (data[j]<data[j-1])
                {
                    Buble = data [j];
                    data[j] = data[j-1];
                    data[j-1]=Buble;
                }
            }
        }
    }
    else if(pil =='2')
    {
        cout<<"Anda Memilih Urutan Data Descending "<<endl;
        for(i=0; i<=n-2; i++)
        {
            for(j=n-1; j>=i+1; j--)
            {
                if (data[j]>data[j-1])
                {
                    Buble = data [j];
                    data[j] = data[j-1];
                    data[j-1]=Buble;
                }
            }
        }
    }
    else
    {
        cout<<"Anda Salah Menginputkan Pilihan!!!"<<endl;
        goto up1;
    }
    for(i=0; i<n; i++)
        {
            cout<<data[i]<<"   ";
        }
    cout<<endl;
    cout<<"apakah anda ingin memasukkan data lagi ?[Y/T] : ";cin>>sl;
    if(sl=='Y' || sl=='y')
    {
        goto up;
    }
    else if (sl == 'T' || sl == 't')
    {
        return 0;
    }

}

2. Quick Sort

metode quick sort c++ mengurutkan dengan sangat cepat, namun algoritma ini sangat komplex dan diproses secara rekursif. Dapat memungkinkan untuk menulis algoritma yang lebih cepat untuk beberapa kasus khusus. Tapi untuk kasus umum, sampai saat ini tidak ada yang lebih cepat dibandingkan algoritma metode quick sort c++.

Pada algoritma quick sort, pemilihan pivot ialah hal yang menentukan apakah algoritma quick sort tersebut akan memberikan performa terbaik atau terburuk. Berikut beberapa cara pemilihan pivot :

1. Pivot merupakan elemen pertama, elemen terakhir, atau elemen tengah dalam array. Cara ini bagus jika elemen tabel tersusun secara acak, tetapi sebaliknya atau tidak bagus jika elemen tabel semula sudah terurut.
2. Pivot dipilih dengan cara acak dari salah satu elemen array. Cara ini baik tapi belum tentu maksimal, sebab diperlukan prosedur khusus untuk menentukan pivot secara acak.
3. Pivot adalah elemen median tabel. Cara ini yaitu cara paling bagus, sebab pada hasil partisi menghasilkan dua bagian tabel yang berukuran seimbang. Juga cara ini memberikan kompleksitas waktu yang minimum. Masalahnya, mencari median dari elemen tabel yang belum terurut adalah persoalan tersendiri

 Listing Program

#include <iostream>
#include <conio.h>
using namespace std;
void quick_sort(int arr[], int left, int right)
{
      int i = left, j = right;int tmp;
      int pivot = arr[(left+right)/2];/* partition */
  while (i<j){
   while (arr[i] < pivot)
   i++;
   while (arr[j] > pivot)
   j--;
   if (i<=j){
    tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
    i++;j--;
                                                    };
         }; /* recursion */
      if (left < j)
            quick_sort(arr, left, j);
      if (i < right)
            quick_sort(arr, i, right);
}
int main()
{
int i,n,data[50];
cout<<"Masukan banyak data: ";cin>>n;
for(i=0;i<n;i++)
{cout<<"Masukan data ["<<i<<"] : ";cin>>data[i];}
cout<<"\nData sebelum diurutkan: "<<endl;
for(i=0;i<n;i++)
{
cout<<data[i]<<" ";
}cout<<"\n";
quick_sort(data,0,n-1);//hasil pengurutan
cout<<"\nHasil pengurutan:\n";
{
int i;
for (i=0;i<n;i++)
cout<<data[i]<<" ";
cout<<"\n";
}getch();
}