Algoritma Dijkstra untuk Jarak Terpendek

Graf sangat berguna untuk merepresentasikan banyak masalah dalam ilmu komputer dan dalam dunia nyata. Pengaplikasian representasi graf dari yang terlihat simple, kemudian cari tahu node yang dapat dicapai dari node lain, sampai yang paling kompleks seperti mencari rute yang mengunjungi tiap node dan meminimalkan total waktu ( Travelling Salesman Problem ). Umumnya, Tapi masalah tersebut adalah pencarian path sederhana. Secara umum, tugasnya adalah menentukan jarak terpendek dari node yang diberikan ke node lainnya pada graf.

Pencarian jalur ini mungkin berguna untuk masalah seperti mendisain mapQuest menjadi seperti program atau mengijinkan pemain komputer dalam game untuk mengarahkan dengan cepat dari tempat ke tempat. Tiap vertex dapat di letakkan dilokasi yang menarik, dan tiap sisi akan menjadi jalur antar tiap lokasi, kemungkinan besar sisi yang berarah. (Untuk tujuan memberikan panduan arah secara langsung, mungkin juga termasuk persimpangan antar vertex pada graf.

Satu dari algoritma paling dikenal untuk menyelesikan masalah tersebut adalah algoritma Dijkstra, yang mana penyelesian masalah dari pencarian jalur terpendek dari node sumber tertentu ke node manapun yang mana tidak ada node yang mempunyai bobot negatif (contoh, anda tidak dapat kembali ke masa lalu  ketika melintasi sisi tersebut). Walaupun memiliki bobot negatif mungkin lain kali akan diperlukan, untuk banyak aplikasi, mereka tidak mungkin dan kemungkinan sisi negatif dapat di hiraukan.

Algoritma Dijkstra

Algoritma Dijkstra prinsip kerjanya yaitu mencari jalur terpendek yang mungkin dari sumbernya yang akan menjadi node awal yang sudah ditemukan. Satu cara berfikir tentang ini adalah model eksplorasi yang dimulai dari sumber, kita dapat mengirim Pengeksplor tiap perjalanan pada kecepatan konstant dan menyebrangi tiap sisi pada waktu yang mungkin pada bobot tiap sisi sama. Kapan saja si pengeksplor mendapat vertex, Dia akan mengecek apakah vertex tersebut baru dikunjungi sekali, kalo iya, maka tandai kebawah jalur tersebut untuk mendapatkan vertex. Si Pengeksplor harus mendapatkan jalur terpendek yang mungkin untuk didapatkan vertex. Kemudian setelah itu mengirimkan si Pengeksplor sepanjang tiap sisi berhubungan dengan vertex tersebut sebagai tetangga,

Hal ini berguna untuk tiap vertex dari graf untuk disimpan pada "prev" sebgai penanda yang akan menyimpan vertex-vertex dari yang si pengeksplor datangi. Ini adalah vertex yang secara langsung menuju ke vertex sekarang pada jalur ke vertex sekarang.
Pseudocode untuk algoritma dijkstra cukup simple dan akan sedikit dibongkar bebrapa indormasi yang diperlukan untuk diolah. Vertex akan diberi nomor berawal dari 0 ada pseudocode yang simple.

Given a graph, G, with edges E of the form (v1, v2) and vertices V, and a
source vertex, s

dist : array of distances from the source to each vertex
prev : array of pointers to preceding vertices
i    : loop index
F    : list of finished vertices
U    : list or heap unfinished vertices

/* Initialization: set every distance to INFINITY until we discover a path */
for i = 0 to |V| - 1
    dist[i] = INFINITY
    prev[i] = NULL
end

/* The distance from the source to the source is defined to be zero */
dist[s] = 0

/* This loop corresponds to sending out the explorers walking the paths, where
 * the step of picking "the vertex, v, with the shortest path to s" corresponds
 * to an explorer arriving at an unexplored vertex */

while(F is missing a vertex)
   pick the vertex, v, in U with the shortest path to s
   add v to F
   for each edge of v, (v1, v2)
        /* The next step is sometimes given the confusing name "relaxation"
        if(dist[v1] + length(v1, v2) < dist[v2])
            dist[v2] = dist[v1] + length(v1, v2)
            prev[v2] = v1
            possibly update U, depending on implementation
        end if
    end for
end while

 Disini ada beberapa hal kecil untuk tetap dalam pengertian pada pseudocode tersebut. Pertama, tiap jarak di inisialisasikan ke INFINITY, kecuali jarak tersebut dari sumber. Masukan ini pada implementasi nyata nya perlu sebuah notasi untu invinity tersebut kebanyakan INT_MAX, didefinisikan limit h. Catatan juga bahwa konsep ini penunjuk pada vertex dan penggunaan nomor untuk mengacu pada vertex tidak benar-benar dikenal. Pada implementasi penggunaan NULL untuk penunjuk prev tidak akan sesuai (kalau vertex adalah bernomor, penggunaan -1 mungkin lebih dapat diterima).

Faktor lain untuk cacatan tersebut bahwa definisi dari U, yang mana dimaksudkan Unfinished, adalah ambigu. Ini dikarenakan beberapa cara untuk mengimplementasikan algoritma dijkstra tersebut, tidak ada yang lebih ketat dari semua cara. Untuk mengerti pilihan tersebut hal ini penting untuk diketahui bagaimana untuk dipikirna tentang efisiensi komputasi pada graf.

Untuk membicarakan tentang efektivitas pada grapf, disini ada 2 variable yang sangat menarik yaitu sisi( Edge) |E|, and dan Vertex |V|. Ingatlah selalu bahwa sisi (edge) tidak dapat dihitung |V|^2 (dan juga kalau tiap vertex terhubung untuk tiap vertex lainnya pada graf berarah). Algoritma yang bekerja pada "waktu yang seimbang" pada graf berjalan pada O(|E| + |V|) wakt.

Satu pilihan dari U sangat simple adalah mendaftarkan vertex yang belum dikunjungi. Pada kasus ini, Algoritma tersebut akan diperlukan untuk pergantian U tiap waktu untuk diambil pada vertex berikutnya. hal ni O(|V|) operasi diulang |V| waktu. untuk total waktu kerja O(|V|^2).

Pilihan lainnya digunakan tumpukan untuk menjaga agar tetap pada jalur yang mana node seharusnya menjadi salah satu property of heaps is that they always have the next element at the top (either the minimum or the maximum). Removal or update operations on heaps require O(log|V|) time. Since it's possible that in the above algorithm each edge may cause a vertex's position in the heap to change, a heap may require O(|E|log|V|) time. Overall, Dijkstra's algorithm takes O(|E|log|V|) time in this case, as all other terms (such as O(|V|log|V|) for finding the nearest vertex and updating the heap and the O(|V|) initialization) are dominated (assuming there are at least |V| edges in the graph.

Pendekatan Lain untuk Pencarian Jalur Terpendek

There are a variety of algorithms for solving the "single-source shortest path" problem--finding the shortest path from a single vertex to all the other possible vertices. Some algorithms only work in special cases, but are faster, relying on the properties of the special case. For instance, the algorithm we're interested in looking at, Dijkstra's algorithm, only works if none of the edges on the graph have negative weights -- the "time" it takes to traverse the edge is somehow less than 0. (When might this come up in practice?)

Algorithms that can handle even the case of negative edge weights do exist, and are interesting in their own right. They are, however, significantly less efficient computationally.

The algorithm that handles negative weighted edges runs in O(|E| * |V|) time, which is significantly slower -- for so-called "dense" graphs with many edges, it can approach a cubic time of O(|V|*|E|) as |E| is O(|V|^2).

On the other hand, Dijkstra's algorithm can be implemented in O(|V|^2) or O(|E|*log(|V|)) time depending on how the next node to consider is chosen. Importantly, as |E| increases, it approaches |V|^2, so choosing the right programming representation requires knowing something about the potential inputs (or choosing between two representations on the fly).

Keterbatasan

Once thing we haven't looked at is the problem of finding shortest paths that must go through certain points. This is a hard problem and is reducible to the Travelling Salesman problem--what this means in practice is that it can take a very long time to solve the problem even for very small inputs.

sumber