Aplikasi Graph- PENCARIAN LINTASAN TERPENDEK

Pencarian lintasan terpendek banyak digunakan pada
sistem navigasi GPS (Global Positioning System) dan juga
pada jaringan komunikasi.
Pada GPS, lintasan terpendek dicari dan juga
dikombinasikan dengan kondisi lalu-lintas pada saat
tersebut untuk mencari waktu tercepat untuk sampai pada
tujuan yang diinginkan. Keadaan lalu lintas didapatkan
melalui hubungan GPS dengan satelit.
Alat GPS kemudian menghitung berapa lama waktu
yang dibutuhkan untuk melalui jalur tertentu dan memilih
jalur yang memiliki waku tempuh minimal. Selanjutnya
GPS akan memandu pengendara kendaraan untuk melalui
lintasan yang dimaksud.
Pada jaringan kounikasi, lintasan terpendek dicari untuk
menghemat waktu dan biaya pengiriman. Dengan mencari
lintasan terpendek, waktu untuk mengirim pesan agar
sampai ke tujuan menjadi lebih singkat dibanding tidak
melalui lintasan terpendek. Biaya pengiriman pesan pun
menjadi lebih efisien menggunakan lintasan terpendek.
Selain itu, dengan penggunaan lintasan terpendek, akan
mengurangi beban pada sistem yang bekerja.
4.2 Aplikasi Graf
Pencarian lintasan terpendek telah dilakukan oleh
banyak orang. Algoritma untuk mencari lintasan
terpendek yang paling terkenal adalah algoritma yang
ditemukan oleh Edsger Wybe Dijkstra yang disebut
algoritma Dijkstra.
Algoritma Dijkstra mencari lintasan terpendek
menggunakna prinsip greedy. Prinsip greedy pada
algoritma Dijkstra menyatakan bahwa pada setiap langkah
kita memilih sisi yang berbobot minimum dan
memasukkannya ke dalam himpunan solusi.
Berikut ini adalah algoritma Dijkstra dalam bahasa
pseudocode [7]:
1 function Dijkstra(Graph, source):
2 for each vertex v in Graph:
Pencarian lintasan terpendek banyak digunakan pada
sistem navigasi GPS (Global Positioning System) dan juga
pada jaringan komunikasi.
Pada GPS, lintasan terpendek dicari dan juga
dikombinasikan dengan kondisi lalu-lintas pada saat
tersebut untuk mencari waktu tercepat untuk sampai pada
tujuan yang diinginkan. Keadaan lalu lintas didapatkan
melalui hubungan GPS dengan satelit.
Alat GPS kemudian menghitung berapa lama waktu
yang dibutuhkan untuk melalui jalur tertentu dan memilih
jalur yang memiliki waku tempuh minimal. Selanjutnya
GPS akan memandu pengendara kendaraan untuk melalui
lintasan yang dimaksud.
Pada jaringan kounikasi, lintasan terpendek dicari untuk
menghemat waktu dan biaya pengiriman. Dengan mencari
lintasan terpendek, waktu untuk mengirim pesan agar
sampai ke tujuan menjadi lebih singkat dibanding tidak
melalui lintasan terpendek. Biaya pengiriman pesan pun
menjadi lebih efisien menggunakan lintasan terpendek.
Selain itu, dengan penggunaan lintasan terpendek, akan
mengurangi beban pada sistem yang bekerja.
4.2 Aplikasi Graf
Pencarian lintasan terpendek telah dilakukan oleh
banyak orang. Algoritma untuk mencari lintasan
terpendek yang paling terkenal adalah algoritma yang
ditemukan oleh Edsger Wybe Dijkstra yang disebut
algoritma Dijkstra.
Algoritma Dijkstra mencari lintasan terpendek
menggunakna prinsip greedy. Prinsip greedy pada
algoritma Dijkstra menyatakan bahwa pada setiap langkah
kita memilih sisi yang berbobot minimum dan
memasukkannya ke dalam himpunan solusi.
Berikut ini adalah algoritma Dijkstra dalam bahasa
pseudocode [7]:
1 function Dijkstra(Graph, source):
2 for each vertex v in Graph:
3 dist[v] := infinity //
Unknown distance function from source to v
4 previous[v] := undefined //
Previous node in optimal path from source
5 dist[source] := 0 //
Distance from source to source
6 Q := the set of all nodes in Graph
// All nodes in the graph are unoptimized
- thus are in Q
7 while Q is not empty: //
The main loop
8 u := vertex in Q with smallest dist[]
9 if dist[u] = infinity:
10 break //
all remaining vertices are inaccessible from
source
11 remove u from Q
12 for each neighbor v of u: //
where v has not yet been removed from Q.
13 alt := dist[u] + dist_between(u,
v)
14 if alt < dist[v]: //
Relax (u,v,a)
15 dist[v] := alt
16 previous[v] := u
17 return dist[]
Jika kita hanya ingin mendapatkan jarak terdekat antara
simpul asal dan tujuan, kita dapat menghilangkan
pencarian pada baris 11 jika u = target sehingga kita dapat
mencari lintasan terdekat menggunakan iterasi:
1 S := empty sequence
2 u := target
3 while previous[u] is defined:
4 insert u at the beginning of S
5 u := previous[u]

Sumber : http://webmail.informatika.org/~rinaldi/Matdis/2009-2010/Makalah0910/MakalahStrukdis0910-069.pdf