ALGORITMA
DIJKSTRA
SEJARAH
ALGORITMA DIJKSTRA
Algoritma Dijkstra, dinamai menurut penemunya, Edsger Dijkstra, adalah sebuah algoritma rakus (greedy algorithm) dalam memecahkan permasalahan jarak terpendek (shortest path problem) untuk sebuah graf berarah (directed graph) dengan bobot-bobot sisi (edge weights) yang bernilai tak-negatif.
Algoritma dijkstra termasuk algoritma pencarian graf yang digunakan untuk menyelesaikan masalah lintasan terpendek dengan satu sumber pada sebuah graf yang tidak memiliki cost sisi negatif dan menghasilkan sebuah pohon lintasan terpendek. Algoritma ini sering digunakan pada routing. Algoritma dijkstra mencari lintasan terpendek dalam sejumlah langkah.
Algoritma ini menggunakan strategi greedy sebagai berikut : Untuk setiap simpul pada sumber (source) dalam graf, algoritma ini akan mencari jalur dengan cost minnimum antara simpul tersebut dengan simpul lainnya.
Misalnya, bila vertices dari sebuah graf melambangkan kota-kota dan bobot sisi (edge weights) melambangkan jarak antara kota-kota tersebut, maka algoritma Dijkstra dapat digunakan untuk menemukan jarak terpendek antara dua kota.
Input algoritma ini adalah sebuah graf berarah dan berbobot, G dan sebuah source vertex s
dalam G. V adalah himpunan semua simpul dalam graph G. Setiap sisi dari graph ini adalah
pasangan vertices (u,v) yang melambangkan hubungan dari vertex u ke vertex v. Himpunan
semua edge disebut E. Weights dari edges dihitung dengan fungsi w: E → [0, ∞); jadi
w(u,v) adalah jarak non-negatif dari vertex u ke vertex v. Cost dari sebuah edge dapat dianggap
sebagai jarak antara dua vertex, yaitu jumlah jarak semua edge dalam path tersebut. Untuk
sepasang vertex s dan t dalam V, algoritma ini menghitung jarak terpendek dari s ke t.
Algorima dijkstra adalah sebuah algoritma rakus (greedy algorithm) dalam memecahkan permasalahan jarak terpendek (shortest path problem). Di bawah ini merupakan penerapan algoritma dijkstra pada graf yang mempunyai 11 vertices dengan bobot masing-masing yang mewakili jarak antar verteks. Vertices pada graf dapat mewakili suatu tempat atau ring road pada suatu wilayah geografis.
Dalam penentuan jalur terpendek pada graf di atas di butuhkan titik awal dan titik tujuan. Misalkan titik awal D dengan titik tujuan F dengan diagram pohon kita dapat mengetahui jalur mana yang dapat dilalui, dengan ketentuan jalur jalan yang telah dilalui dengan rute yang sama tidak boleh dilalui lagi dan jika telah sampai pada titik tujuan maka pencarian pada rute tersebut berhenti dan melanjutkan dengan rute lain, jika semua rute telah dilalui kita dapat mengambil kesimpulan rute mana yang akan dilalui dengan jarak yang optimum atau terpendek.
Cara Kerja :
Cara kerja Algoritma dijkstra memakai strategi greedy, dimana pada setiap langkah di pilih sisi dengan bobot terkecil yang menghubungkan sebuah simpul yang sudah terpilih dengan simpul yang sudah terpilih dengan simpul lain yang belum terpilih.
Algoritma
Dijkstra membutuhkan parameter tempat asal dan tempat tujuan. Hasil akhir dari
algoritma ini adalah jarak terpendek dari tempat asal ke tempat ujuan
beserta rutenya.
Pencarian rute terpendek merupakan salah satu persoalan dalam teori graf.
Persoalan ini bisa diselesaikan dengan algoritma dijkstra karena lebih mudah
dan menarik, adapun beberapa keuntungan yang kita peroleh dari Algoritma
Dijkstra yaitu :
1.
Algoritma Dijkstra dapat menentukan jalur tercepat dengan waktu yang lebih
cepat dibandingkan algoritma lainnya.
2. Menggunakan Algoritma Dijkstra mempermudah kita
dalam mengetahui jarak atau lintasan terpendek dari suatu titik tertentu ke
semua titik yang lain.
3. Menggunakan Algoritma Dijkstra dalam penerapan di
dalam sistem geografis akan menampilakan visualisasi data dalam
bentuk peta
4. Pada penampilan
rute atau peta Algoritma Dijkstra lebih mudah di baca dan di pahami.
5. Pada
rute atau peta dan lintasannya dapat diberikan warna, sehingga penampilan
Algoritma Dijkstra lebih menarik dan lebih mudah untuk membedakan dari suatu
titik tertentu ke titik yang lain.
contoh:
Dari diagram pohon tersebut dapat ditentukan rute yang berhasil mencapai tujuan dari vertices D ke vertices F yaitu :
D ⇨A ⇨ B ⇨F dengan total jarak = 10
D ⇨A ⇨ G ⇨ B⇨ F dengan total jarak = 18
D ⇨C ⇨ B ⇨F dengan total jarak = 13
D ⇨E ⇨F dengan total jarak = 9
Dari hasil tersebut jarak terpendek adalah D ⇨E ⇨F dengan total jarak 9. Dalam penerapan algoritma dijkstra pada graf di atas merupakan graf tidak berarah, tetapi algoritma Dijkstra dapat juga diterapkan pada graf berarah
Contoh Program Algoritma Dijkstra:
#include
#include
#include
using namespace std;
const Vertices=100; //The Max Number Of Vertices Can User Inter ,You Can Change It
const Value=100; //The Max Number Of Value Can User Inter ,You Can Change It
int NumbetOfVertices; //The Number Of Vertices
int Data_Vertices[Vertices][Vertices],InformationOfPath[Vertices][2];
int CalculateTheVertices[Vertices][Vertices],Calc_Ver_Positions[Vertices][Vertices];
int Search(int); // The function To Search
void CalcuatePath(); // Use This function To Calcuate Path
void VerticesInformation();
void Print(); //Use This function To Print Path
int main()
{
cout<<"Please Enter The Number of Vertice :"<>NumbetOfVertices; //Here user Inter The Number Of Vertice
int i,j;
for(i=0;i<<="i)" continue;="" cout<<endl<<"if="" conection="" between="" vertice="" "<<i<<"="" and="" "<<j<<"="" please="" prss="" y="" not="" press="" n:="" "="" ;="" ch="getche();" (ch="='Y'" ||="" cout<<endl<<"enter="" distance="" :="" ";="" cin="">>Data_Vertices[i][j];
}
else
Data_Vertices[i][j]=Value;
Data_Vertices[j][i]=Data_Vertices[i][j];
}
}
void Print()
{
int i,p,j;
cout<<endl<<"the short="" path="" is="" :="" "<<<endl<<<"(v"<<p<<")="" ";="" if(informationofpath[j][1]="=Value)" cout<<"("<<"inf"<<")";="" else="" cout<<<"="="> ";
p=Calc_Ver_Positions[j][p];
}
cout<<" (V"<<p<<")";
}
cout<<"\n";
}
void CalcuatePath()
{
bool Temp;
int i,j,k,L,Current,Min_Vertice,Min_Value;
for (i=1;i<=NumbetOfVertices;i++)
{
CalculateTheVertices[1][i]=Data_Vertices[1][i];
if ( Data_Vertices[1][i]<value)
Calc_Ver_Positions[1][i]=1;
else
Calc_Ver_Positions[1][i]=Value;
}
Current=1;
InformationOfPath[1][0]=1;
InformationOfPath[1][1]=0;
for (k=2;k<=NumbetOfVertices;k++)
{
Min_Value=Value;
for (j=1;j<=NumbetOfVertices;j++)
{
if(CalculateTheVertices[k-1][j]<min_value)
{
Temp=false;
for (i=0;i
if (InformationOfPath[i][0]==j)
{
Temp=true;
break;
}
if (Temp==false)
{
Min_Value=CalculateTheVertices[k-1][j];
Min_Vertice=j;
}
}
}
if (Min_Value==Value)
{
cout <<"\nNo Graph\n";
exit (1);
}a
Current=Min_Vertice;
InformationOfPath[k][0]=Min_Vertice;
InformationOfPath[k][1]=Min_Value;
for (j=1;j<=NumbetOfVertices;j++)
{
L=Data_Vertices[InformationOfPath[k][0]][j] + InformationOfPath[k][1];
if ( L<calculatethevertices[k-1][j])
{
CalculateTheVertices[k][j]=L;
Calc_Ver_Positions[k][j]=InformationOfPath[k][0];
}
else
{
CalculateTheVertices[k][j]=CalculateTheVertices[k-1][j];
Calc_Ver_Positions[k][j]=Calc_Ver_Positions[k-1][j];
}
}
}
}</calculatethevertices[k-1][j])
</min_value)
</value)
</p<<")";
</endl<<"the>
Dari diagram pohon tersebut dapat ditentukan rute yang berhasil mencapai tujuan dari vertices D ke vertices F yaitu :
D ⇨A ⇨ B ⇨F dengan total jarak = 10
D ⇨A ⇨ G ⇨ B⇨ F dengan total jarak = 18
D ⇨C ⇨ B ⇨F dengan total jarak = 13
D ⇨E ⇨F dengan total jarak = 9
Dari hasil tersebut jarak terpendek adalah D ⇨E ⇨F dengan total jarak 9. Dalam penerapan algoritma dijkstra pada graf di atas merupakan graf tidak berarah, tetapi algoritma Dijkstra dapat juga diterapkan pada graf berarah
Contoh Program Algoritma Dijkstra:
#include
#include
#include
using namespace std;
const Vertices=100; //The Max Number Of Vertices Can User Inter ,You Can Change It
const Value=100; //The Max Number Of Value Can User Inter ,You Can Change It
int NumbetOfVertices; //The Number Of Vertices
int Data_Vertices[Vertices][Vertices],InformationOfPath[Vertices][2];
int CalculateTheVertices[Vertices][Vertices],Calc_Ver_Positions[Vertices][Vertices];
int Search(int); // The function To Search
void CalcuatePath(); // Use This function To Calcuate Path
void VerticesInformation();
void Print(); //Use This function To Print Path
int main()
{
cout<<"Please Enter The Number of Vertice :"<>NumbetOfVertices; //Here user Inter The Number Of Vertice
int i,j;
for(i=0;i<<="i)" continue;="" cout<<endl<<"if="" conection="" between="" vertice="" "<<i<<"="" and="" "<<j<<"="" please="" prss="" y="" not="" press="" n:="" "="" ;="" ch="getche();" (ch="='Y'" ||="" cout<<endl<<"enter="" distance="" :="" ";="" cin="">>Data_Vertices[i][j];
}
else
Data_Vertices[i][j]=Value;
Data_Vertices[j][i]=Data_Vertices[i][j];
}
}
void Print()
{
int i,p,j;
cout<<endl<<"the short="" path="" is="" :="" "<<<endl<<<"(v"<<p<<")="" ";="" if(informationofpath[j][1]="=Value)" cout<<"("<<"inf"<<")";="" else="" cout<<<"="="> ";
p=Calc_Ver_Positions[j][p];
}
cout<<" (V"<<p<<")";
}
cout<<"\n";
}
void CalcuatePath()
{
bool Temp;
int i,j,k,L,Current,Min_Vertice,Min_Value;
for (i=1;i<=NumbetOfVertices;i++)
{
CalculateTheVertices[1][i]=Data_Vertices[1][i];
if ( Data_Vertices[1][i]<value)
Calc_Ver_Positions[1][i]=1;
else
Calc_Ver_Positions[1][i]=Value;
}
Current=1;
InformationOfPath[1][0]=1;
InformationOfPath[1][1]=0;
for (k=2;k<=NumbetOfVertices;k++)
{
Min_Value=Value;
for (j=1;j<=NumbetOfVertices;j++)
{
if(CalculateTheVertices[k-1][j]<min_value)
{
Temp=false;
for (i=0;i
if (InformationOfPath[i][0]==j)
{
Temp=true;
break;
}
if (Temp==false)
{
Min_Value=CalculateTheVertices[k-1][j];
Min_Vertice=j;
}
}
}
if (Min_Value==Value)
{
cout <<"\nNo Graph\n";
exit (1);
}a
Current=Min_Vertice;
InformationOfPath[k][0]=Min_Vertice;
InformationOfPath[k][1]=Min_Value;
for (j=1;j<=NumbetOfVertices;j++)
{
L=Data_Vertices[InformationOfPath[k][0]][j] + InformationOfPath[k][1];
if ( L<calculatethevertices[k-1][j])
{
CalculateTheVertices[k][j]=L;
Calc_Ver_Positions[k][j]=InformationOfPath[k][0];
}
else
{
CalculateTheVertices[k][j]=CalculateTheVertices[k-1][j];
Calc_Ver_Positions[k][j]=Calc_Ver_Positions[k-1][j];
}
}
}
}</calculatethevertices[k-1][j])
</min_value)
</value)
</p<<")";
</endl<<"the>
