Algoritma Djikstra
Algoritma
Dijkstra dikstra ditemukan oleh Edsger.Wybe Dijkstra pada tahun 1959. Algoritma
ini merupakan algoritma yang dapat memecahkan masalah pencarian jalur terpendek
dari suatu graf pada setiap simpul yang bernilai tidak negatif. dijkstra
merupakan algoritma yang termasuk dalam algoritma greedy, yaitu algoritma yang
sering digunakan untuk memecahkan masalah yang berhubungan dengan suatu
optimasi. Dalam pencarian jalur terpendeknya algoritma dijkstra bekerja dengan
mencari bobot yang paling minimal dari suatu graf berbobot, jarak terpendek
akan diperoleh dari dua atau lebih titik dari suatu graf dan nilai total yang
didapat adalah yang bernilai paling kecil.
Source
code Algoritma Dijkstra
Berikut
merupakan source code untuk algoritma
Dijkstra, yaitu:
include <stdio.h>
#include <stdlib.h>
#include <iostream>
#define INF 999
using namespace std;
int main()
{
int n,i,j,start;
printf("Masukan Jumlah Vertex : ");
scanf("%d",&n);
int
G[n][n],tempGraf[n][n],jarak[n],visit[n],temp[n],count;
printf("Masukan Matrix Graf : \n");
for(i = 0;i <
n ;i++)
{
for
(j=0;j<n;j++)
{
cout<<"Matriks
["<<i<<"]["<<j<<"]: ";
scanf("%d",&G[i][j]);
}
}
printf("Masukan Vertex Asal : ");
scanf
("%d",&start);
for(i=0;i<n;i++)
{
for
(j=0;j<n;j++)
{
if
(G[i][j] == 0)
{
tempGraf[i][j] = INF;
}
else{
tempGraf[i][j] = G[i][j];
}
}
}
for (i =
0;i<n;i++)
{
jarak[i] =
tempGraf[start][i];
temp[i] =
start;
visit[i] = 0;
}
jarak[start] = 0;
visit[start] = 1;
count =1;
//dimulai dari 1 karena kita tidak akan menghitung vertex asal lagi
//proses untuk
menghitung vertex yang dikunjungi
int
jarakmin,nextvertex;
while (count <
n-1)
{
jarakmin =
INF;
for
(i=0;i<n;i++)
{
//jika
jarak lebih kecil dari jarak minimum dan vertex belum dikunjungi
// maka
jarak minimum adalah jarak yang sudah dibandingkan sebelumnya dengan jarakmin
if(jarak[i] < jarakmin && visit[i]!=1)
{
jarakmin = jarak[i];
nextvertex = i; //untuk memberikan vertex pada jarak minimum
}
}
// untuk
mengecek vertex selanjutnya yang terhubung dengan vertex lain yang memiliki
jarak minimum
visit[nextvertex] = 1;
for(i =
0;i<n;i++)
{
if(visit[i]!=1)
{
if(jarakmin+tempGraf[nextvertex][i]<jarak[i])
{
jarak[i] = jarakmin+tempGraf[nextvertex][i];
temp[i] = nextvertex;
}
}
}
count++;
}
//nenampilkan
jalur dan jarak untuk setiap vertex
int a[n+1],k;
for (i = 0; i
< n ;i++)
{
if(i!=start)
{
printf
("\nHasil jarak untuk vertex ke-%d adalah %d\n",i,jarak[i]);
j=i;
printf
("%d<-",i);
while(j!=start)
{
j=temp[j];
printf ("%d",j);
if(j!=start)
{
printf ("<-");
}
}
}
}
printf
("\nTotal Jaraknya adalah %d\n",jarak[n-1]);
return 0;
}
|
Algoritma Kruskal
Algoritma
Kruskal merupakan salah satu algoritma dalam teori graf untuk menyelesaikan
persoalan pohon merentang minimum. Pada Algoritma Kruskal, sisi-sisi didalam
graf diurutkan terlebih dahulu berdasarkan bobotnya dari kecil ke besar.
Algoritma
Kruskal ditemukan pada tahun 1956 oleh seorang ilmuwan matematika, statistika,
komputer dan psikometrika Joseph yaitu Bernard Kruskal, Jr yang berasal dari
Amerika. 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 persatu sisi dari graf G dan
memasukkannya dalam pohon yang telah terbentuk sebelumnya. Seiring dengan
berjalannya iterasi pada setiap sisi maka forest akan memiliki pohon yang
semakin sedikit. Oleh sebab itu analogi ini disebut growing forest. Algoritma
Kruskal akan terus menambahkan sisi-sisi ke dalam hutan sesuai hingga akhirnya
tidak akan ada lagi forest, melainkan hanyalah sebuah pohon merentang minimum.
Adapun
langkah kerja algoritma Kruskal sebagai berikut (Wattimena dan Lawatama, 2013):
1)
Lakukan pengurutan
terhadap setiap sisi di graf G mulai dari sisi dengan bobot terkecil.
2)
Pilih sisi (u,v) yang
mempunyai bobot minimum yang tidak membentuk sirkuit di T. Tambahkan (u,v) ke
dalam T.
3)
Ulangi langkah 2
sampai pohon merentang minimum terbentuk, yaitu ketika sisi di dalam pohon
merentang T berjumlah 𝑛
− 1 (𝑛
adalah jumlah simpul pada graf).
Source code Algoritma Kruskal
Berikut
merupakan source code untuk algoritma
Dijkstra, yaitu:
include <cstdlib>
#include <iostream>
#include <fstream>
using namespace std;
class kruskal
{
private:
int n ;//no of
nodes
int noe; //no
edges in the graph
int
graph_edge[100][4];
int tree[10][10];
int
sets[100][10];
int top[100];
public:
int read_graph();
void
initialize_span_t();
void
sort_edges();
void algorithm();
int find_node(int
);
void
print_min_span_t();
};
int kruskal::read_graph()
{
///cout<<"Program ini Mengimplementasikan
Algoritma Kruskal\n";
cout<<"Banyak titik graph : ";
cin>>n;
noe=0;
cout<<"\nJarak antar tiap titik:\n";
for(int i=1;i<=n;i++)
{
for(int
j=i+1;j<=n;j++)
{
cout<<"("<<i<<" ,
"<<j<<") = ";
int w;
cin>>w;
if(w!=0)
{
noe++;
graph_edge[noe][1]=i;
graph_edge[noe][2]=j;
graph_edge[noe][3]=w;
}
}
}
}
void kruskal::sort_edges()
{
/** Sort the edges using bubble sort in increasing
order******/
for(int i=1;i<=noe-1;i++)
{
for(int
j=1;j<=noe-i;j++)
{
if(graph_edge[j][3]>graph_edge[j+1][3])
{
int
t=graph_edge[j][1];
graph_edge[j][1]=graph_edge[j+1][1];
graph_edge[j+1][1]=t;
t=graph_edge[j][2];
graph_edge[j][2]=graph_edge[j+1][2];
graph_edge[j+1][2]=t;
t=graph_edge[j][3];
graph_edge[j][3]=graph_edge[j+1][3];
graph_edge[j+1][3]=t;
}
}
}
cout<<"\n\nSetelah Jarak diurutkan adalah
::\n";
for(int i=1;i<=noe;i++)
cout<<"("<< graph_edge[i][1]
<<" , "<<graph_edge[i][2]
<<" ) =
"<<graph_edge[i][3]<<endl;
}
void kruskal::algorithm()
{
for(int
i=1;i<=n;i++)
{
sets[i][1]=i;
top[i]=1;
}
cout<<"\nRentang Yang di Pakai\n\n";
for(int
i=1;i<=noe;i++)
{
int
p1=find_node(graph_edge[i][1]);
int
p2=find_node(graph_edge[i][2]);
if(p1!=p2)
{
cout<<"Rentang yg masuk ke pohon ::"
<<" < "<<graph_edge[i][1]<<" ,
"
<<graph_edge[i][2]<<" >
"<<endl<<endl;
tree[graph_edge[i][1]][graph_edge[i][2]]=graph_edge[i][3];
tree[graph_edge[i][2]][graph_edge[i][1]]=graph_edge[i][3];
// Mix
the two sets
for(int
j=1;j<=top[p2];j++)
{
top[p1]++;
sets[p1][top[p1]]=sets[p2][j];
}
top[p2]=0;
}
else
{
cout<<"Jika "
<<"
< "<<graph_edge[i][1]<<" , "
<<graph_edge[i][2]<<" > "<<"di
masukkan, maka terbentuk siklus. jadi di hapus\n\n";
}
}
}
int kruskal::find_node(int n)
{
for(int
i=1;i<=noe;i++)
{
for(int
j=1;j<=top[i];j++)
{
if(n==sets[i][j])
return i;
}
}
return -1;
}
int main(int argc, char *argv[])
{
kruskal obj;
obj.read_graph();
obj.sort_edges();
obj.algorithm();
system("PAUSE");
return
EXIT_SUCCESS;
}
|
Kasus
Pendistribusian Obat ke Apotek-Apotek yang Ada di Kota Pelaihari
Di
kota Pelaihari terdapat beberapa apotek yang memiliki jarak beragam antara satu
dengan yang lainnya. Dalam pendistribusian obat-obatan, diperlukan jarak yang
paling minimum untuk membantu proses pengiriman obat agar cepat dan menghemat
waktu serta bahan bakar, sehingga pendistribusian obat menjadi lebih efisien.
Pencarian
jarak terpendek untuk melakukan pendistribusian obat ke masing-masing apotik
dapat dilakukan dengan menerapkan algoritma Dijkstra dan algoritma Kruskal.
Maps
Berikut
merupakan maps yang diijadikan dasar oleh penulis untuk dibuat graf pada kasus
pendistribusian obat ke apotek-apotek yang ada di Kota Pelaihari, yaitu:
Graph
Berikut
merupakan graph pada algoritma Dijkstra mengenai kasus pendistribusian obat ke
apotek-apotek yang ada di Kota Pelaihari, yaitu:
2.3.2
Matriks
1.
Matriks pada Algoritma
Dijkstra
Berikut merupakan matriks yang terdapat
pada algoritma Dijkstra, yaitu:
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
|
0
|
0
|
255
|
0
|
0
|
0
|
0
|
0
|
0
|
1600
|
0
|
0
|
0
|
1
|
255
|
0
|
441
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
2
|
0
|
441
|
0
|
2760
|
0
|
0
|
0
|
0
|
1800
|
0
|
0
|
26
|
3
|
0
|
0
|
2760
|
0
|
7070
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
4
|
0
|
0
|
0
|
7070
|
0
|
5590
|
0
|
0
|
0
|
0
|
0
|
0
|
5
|
0
|
0
|
0
|
0
|
5590
|
0
|
1310
|
0
|
0
|
0
|
0
|
0
|
6
|
0
|
0
|
0
|
0
|
0
|
1310
|
0
|
656
|
0
|
1690
|
0
|
0
|
7
|
0
|
0
|
0
|
0
|
0
|
0
|
656
|
0
|
435
|
0
|
0
|
0
|
8
|
1600
|
0
|
1800
|
0
|
0
|
0
|
0
|
435
|
0
|
0
|
0
|
0
|
9
|
0
|
0
|
0
|
0
|
0
|
0
|
1690
|
0
|
0
|
0
|
20
|
0
|
10
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
20
|
0
|
30
|
11
|
0
|
0
|
26
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
30
|
0
|
2. Matriks pada Algortima
Kruskal
Berikut merupakan matriks yang terdapat
pada algoritma Kruskal, yaitu:
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
12
|
|
1
|
0
|
255
|
0
|
0
|
0
|
0
|
0
|
0
|
1600
|
0
|
0
|
0
|
2
|
255
|
0
|
441
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
3
|
0
|
441
|
0
|
2760
|
0
|
0
|
0
|
0
|
1800
|
0
|
0
|
26
|
4
|
0
|
0
|
2760
|
0
|
7070
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
5
|
0
|
0
|
0
|
7070
|
0
|
5590
|
0
|
0
|
0
|
0
|
0
|
0
|
6
|
0
|
0
|
0
|
0
|
5590
|
0
|
1310
|
0
|
0
|
0
|
0
|
0
|
7
|
0
|
0
|
0
|
0
|
0
|
1310
|
0
|
656
|
0
|
1690
|
0
|
0
|
8
|
0
|
0
|
0
|
0
|
0
|
0
|
656
|
0
|
435
|
0
|
0
|
0
|
9
|
1600
|
0
|
1800
|
0
|
0
|
0
|
0
|
435
|
0
|
0
|
0
|
0
|
10
|
0
|
0
|
0
|
0
|
0
|
0
|
1690
|
0
|
0
|
0
|
20
|
0
|
11
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
20
|
0
|
30
|
12
|
0
|
0
|
26
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
30
|
0
|
Running
1.
Hasil running pada Algoritma Kruscal
