lifelong learner — urip iku urup, currently working on accenture.

Cara mencari jarak terpendek dengan menggunakan R

0
Degananda.com -

Untuk memecahkan masalah dalam mencari jarak terpendek dari suatu jaringan kita dapat menggunakan teori graf atua teori grafik yakni suatu teori yang mempelejari mengenai sifat-sifat dari grafik. Graf atau grafik sendiri dapat diartikan suatu simpul atau “node”  atau ada juga yang menyebutnya dengan “vertex” yang saling terhubung. Hubungan antar node ini akan menghasilkan suatu “sisi” yang disebut dengan busur atau “edge”.

Implementasi teori graph pada R dapat kita jumpai pada beberapa package. Pada level pengaplikasian kita tidak perlu dari awal membuat algoritma dari teori graf itu sendiri. namun jika memang ingin mendalami sangat disarankan untuk tidak menggunakan package atau library yang telah ada.

Cara mencari jarak terpendek dengan menggunakan R

pada R kita dapat memanfaatkan library igraph untuk mendapatkan jarak terpendah dari suatu jaringan atau network. Contohnya kita ibaratkan memiliki jaringan seperti berikut ini.

dari gambar diatas maka dapat kita gambarkan networknya yakni sebagai berikut

  • A-B 10
  • B-D 15
  • A-C 5
  • C-D 5

Goal atau Tujuan

tujuan kita adalah untuk mendapatkan node atau simpul yang harus kita lalui dari A ke D dengan jarak terpendek.

Install package igraph

Langkah pertama adalah melakukan installasi package igraph. Jalankan perintah dibawah ini untuk melakukan installasi package igraph pada R.

## Download and install the package
install.packages("igraph")

Proses install dan download igraph pada R ini cukup memakan waktu tergantung dari kecepatan internet anda jadi bersabarlah untuk menunggu. Setelah itu untuk dapat menggunakan igraph pada workspace R kita maka jalankan perintah load terharap package igraph tersebut

## Load package
library(igraph)

untuk memastikan igraph telah berhasil terinstall dan terload pada workspace kita tuliskan graph [dot] diconsole. Jika installasi dan loading berhasil maka auto complete akan memunculkan fungsi-fungsi yang dapat dijalankan oleh igraph.

Membuat network node.

Langkah kedua adalah kita tuliskan network node yang telah didefinisikan sebelumnya

  • A-B 10
  • B-D 15
  • A-C 5
  • C-D 5

network node diatas akan kita masukan pada data frame.

df = as.data.frame(rbind(
  c("a","b",10),
  c("b","d",15),
  c("a","c",5),
  c("c","d",5)
))
names(df) = c("start_node","end_node","dist")

jika anda memiliki lebih dari empat network node maka silahkan keseluruhan network node tersebut dengan format seperti ini : c(“a”,”b”,10) yang mengikuti format yang telah kita definsikan c(“start_node”,”end_node”,”dist”).

Langkah ketiga adalah mengubah model network node diatas menjadi igraph class. Proses ini sangat penting karena igraph hanya dapat membaca igraph class. Perintah yang digunakan adalah

gdf <- graph.data.frame(df, directed=FALSE)

Langkah ke empat adalah mendapatkan shortest path (jarak terpendek) dari network kita berdasarkan igraph class yang telah kita buat.

oke selanjutnya untuk mendapatkan jarak terpendek kita dapat memanfaatkan perintah all_shortest_path sehingga perintahnya menjadi seperti ini

sp=get.all.shortest.paths(gdf, "a", "d",weights=E(gdf)$dist)
sp

Sehingga dari network diatas maka jarak terpendek adalah

Hasilnya adalah A-C-D yakni dengan jarak 10.