Dijkstra dan Kruskal
1. Algoritma Dijkstra
Dijkstra adalah
mengambil sisi yang memiliki bobot minimum untuk setiap langkahnya. Sisi yang
diambil menghubungkan sebuah simpul yang sudah terpilih dengan simpul lain yang
belum terpilih. Lintasan yang dipilih haruslah lintasan terpendek diantara
semua lintasan ke simpul-simpul yang belum terpilih.
Algoritma
Dijkstra adalah salah satu metode untuk memecahkan masalah pencarian rute
terpendek. Algoritma ini biasanya diterapkan pada sebuah aplikasi pencari rute
jalan yang terdekat dari suatu daerah ke daerah lainnya.
Untuk bisa menerapkan algoritma ini dibutuhkan beberapa data yang harus disiapkan, yaitu :
Untuk bisa menerapkan algoritma ini dibutuhkan beberapa data yang harus disiapkan, yaitu :
1.
Beberapa
Titik/simpul/daerah, titik/simpul/daerah yang bisa dijangkau secara langsung,
dan juga jarak antara mereka.
2. Titik/simpul/daerah awal.
3. Titik/simpul/daerah tujuan.
Contoh Program :
|
Algortima
|
|
#include<stdio.h>
#include<conio.h>
#include<process.h>
#include<string.h>
#include<math.h>
#define
IN 99
#define
N 6
int
dijkstra(int cost[][N], int source, int target);
int
dijsktra(int cost[][N],int source,int target)
{
int
dist[N],prev[N],selected[N]={0},i,m,min,start,d,j;
char
path[N];
for(i=1;i<
N;i++)
{
dist[i] = IN;
prev[i] = -1;
}
start
= source;
selected[start]=1;
dist[start]
= 0;
while(selected[target]
==0)
{
min = IN;
m = 0;
for(i=1;i< N;i++)
{
d = dist[start]
+cost[start][i];
if(d<
dist[i]&&selected[i]==0)
{
dist[i] = d;
prev[i] = start;
}
if(min>dist[i] &&
selected[i]==0)
{
min = dist[i];
m = i;
}
}
start = m;
selected[start] = 1;
}
start
= target;
j
= 0;
while(start
!= -1)
{
path[j++] = start+65;
start = prev[start];
}
path[j]='\0';
strrev(path);
printf("%s",
path);
return
dist[target];
}
int
main()
{
int cost[N][N],i,j,w,ch,co;
int source, target,x,y;
printf("\t****Lintaan
Algoritma Terpendek (DIJKSRTRA's ALGORITHM)****\n\n");
for(i=1;i< N;i++)
for(j=1;j< N;j++)
cost[i][j] = IN;
for(x=1;x< N;x++)
{
for(y=x+1;y<
N;y++)
{
printf(" Masukkan nilai dari jalur antara simpul %d dan %d:
",x,y);
scanf("%d",&w);
cost
[x][y] = cost[y][x] = w;
}
printf("\n");
}
printf("\n Masukkan asal
simpul: ");
scanf("%d",
&source);
printf("\n Masukkan target
simpul: ");
scanf("%d",
&target);
co =
dijsktra(cost,source,target);
printf("\n Jalur Terpendek:
%d",co);
getch();
return(0);
}
|
2. Algoritma Kruskal
Algoritma ini adalah
algoritma yang akan mencari sebuah pohon merentang minimum (minimum spanning
tree) pada seabuah graf berbobot yang terhubung. Secara umum, algoritma Kruskal adalah memilih sisi yang
memiliki bobot minimum yang tidak membentuk sirkuit pada pohon, kemudian
menambahkan sisi tersebut sebagai solusi. Langkah tersebut diulangi sampai
sebanyak jumlah simpul dikurangi satu.
Contoh Program :
|
Algoritma
|
|
#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][100];
int tree[100][100];
int sets[100][100];
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;
}
}
cout << endl;
}
}
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;
}
|
Hasil Running
0 komentar:
Posting Komentar