Algoritma Dijkstra

Assalamu’alaikum

Salam Sejahtera bagi kita semua,

Hai Sobat Mahir, kali ini mari KitaMahir akan membahas “Algoritma Dijkstra”,

Teruslah menuntut membaca dan manfaatkan ilmu sebaik mungkin.

Mungkin diantara kalian sudah ada yang sudah pernah mendengar atau bahkan sudah ada yang memahami algoritma dijkstra, untuk lebih jelasnya, mari kita bahas.

Algoritma Dijkstra atau algoritme rakus (greedy algorithm) merupakan algoritma pemecahan masalah dengan menggunakan jarak terpendek (shortest path problem) pada sebuah graf berarah dengan bobot - bobot garis bernilai nonnegative [0,∞), Input algoritme ini adalah sebuah graf berarah yang berbobot (G) dan sebuah titik asal (s) dalam himpunan garis (V). Misalnya, bila titik dari sebuah graf melambangkan kota-kota dan bobot garis melambangkan jarak antara kota-kota tersebut, algoritme Dijkstra dapat digunakan untuk menemukan jarak terpendek antara dua kota. Biaya (cost) dari sebuah garis dapat dianggap sebagai jarak antara dua simpul, yaitu jumlah jarak semua garis dalam jalur tersebut. Untuk sepasang titik s dan titik t dalam V, algoritme ini menghitung jarak terpendek dari titik s ke titik t.

Algoritma yang ditemukan oleh ilmuan computer bernama Edsger Dijkstra ini dipublikasikan pada tahun 1959  jurnal Numerische Mathematik yang berjudul “A Note on Two Problems in Connexion with Graphs” dan dianggap sebagai algoritma greedy.

Permasalahan rute terpendek dari sebuah titik ke akhir titik lain adalah sebuah masalah klasik optimasi yang banyak digunakan untuk menguji sebuah algoritma yang diusulkan. Permasalahan rute terpendek dianggap cukup baik untuk mewakili masalah optimisasi, karena permasalahannya mudah dimengerti (hanya menjumlahkan seluruh edge yang dilalui) namun memiliki banyak pilihan solusi.

Menurut Andrew Goldberg peneliti Microsoft Research Silicon Valley, mengatakan ada banyak alasan mengapa peneliti terus mempelajari masalah pencarian jalan terpendek. “Jalan terpendek adalah masalah optimasi yang relevan untuk berbagai macam aplikasi, seperti jaringan routing, game, desain sirkuit, dan pemetaan”.

Diskripsi matematis untuk grafik dapat diwakili G = {V. E}, yang berarti sebuah grafik (G) didefenisikan oleh satu set simpul (Vertex = V) dan koleksi Edge (E).

Algoritma Dijkstra bekerja dengan membuat jalur ke satu simpul optimal pada setiap langkah. Jadi pada langkah ke n, setidaknya ada n node yang sudah kita tahu jalur terpendek. Langkah-langkah algoritma Dijkstra dapat dilakukan dengan  langkah-langkah berikut:

1.      Tentukan titik mana yang akan menjadi node awal, lalu beri bobot jarak pada node pertama ke node terdekat satu per satu, Dijkstra akan melakukan pengembangan pencarian dari satu titik ke titik lain dan ke titik selanjutnya tahap demi tahap;

2.      Beri nilai bobot (jarak) untuk setiap titik ke titik lainnya, lalu set nilai 0 pada node awal dan nilai tak hingga terhadap node lain (belum terisi) 2;

3.      Set semua node yang belum dilalui  dan set node awal sebagai “Node keberangkatan”;

4.      Dari node keberangkatan, pertimbangkan node tetangga yang belum dilalui dan hitung jaraknya dari titik keberangkatan. Jika jarak ini lebih kecil dari jarak sebelumnya (yang telah terekam sebelumnya) hapus data lama, simpan ulang data jarak dengan jarak yang baru;

5.      Saat kita selesai mempertimbangkan setiap jarak terhadap node tetangga, tandai node yang telah dilalui sebagai “Node dilewati”. Node yang dilewati tidak akan pernah di cek kembali, jarak yang disimpan adalah jarak terakhir dan yang paling minimal bobotnya;

6.      Set “Node belum dilewati” dengan jarak terkecil (dari node keberangkatan) sebagai “Node Keberangkatan” selanjutnya dan ulangi langkah e .

Sebagai contoh hitunglah Jarak terdekat dari V1 ke V7 pada gambar berikut ini :

Hasil setiap stepnya dapat dilihat pada tabel berikut ini :

Dengan demikian jarak terpendek dari V1 ke V7 adalah 16 dengan jalur V1->V2->V3->V5->V6->V7.

Mungkin sekian dari KitaMahir, Semoga penjelasan tentang Algoritma Dijkstra kali ini dapat bermanfaat bagi kita Semua, Syukran.

Wassaalamu'alaikum

Daftar Pustaka

https://mti.binus.ac.id/2017/11/28/algoritma-dijkstra/

https://id.wikipedia.org/wiki/Algoritme_Dijkstra

https://id.wikipedia.org/wiki/Masalah_jarak_terpendek

.

Fisika - Arus Listrik dan Hambatan

Asssalamu'alaikum

salam sejahtera bagi kita semua 

sobat mahir, setelah sekian lama dan sempat di hapus semua postingannya, kali ini KitaMahir akan membahas  "Arus Listrik dan Hambatan". Teruslah menuntut membaca dan manfaatkan ilmu sebaik mungkin.

nah, sobat mahir, apa ada yang sudah paham apa yang di maksud dengan arus listrik dan juga hambatan, jika belum, mari kita bahas.

Arus Listrik

Electric Current, atau dalam bahasa Indonesia adalah arus listrik, arus listrik adalah muatan listrik yang mengalir dari satu titik ke titik lainnya melalui media konduktor dalam suatu rangkaian listrik tiap satuan waktu, arus listrik juga terjadi akibat adanya beda potensial atau tegangan pada media penghantar antara dua titik, semakin besar nilai tegangan antara dua titik tersebut, maka akan semakin besar pula nilai arus yang mengalir pada kedua titik tersebut. Atau bisa juga arus listrik dapat kita analogikan sebagai aliran air pada sebuah tangki air. Makin besar tekanan airnya dan makin kecil hambatan pada pipa (ukuran pipa yang besar) maka jumlah aliran air juga akan banyak. Demikian juga dengan aliran arus listrik, makin tinggi Tegangan yang diberikan dan makin kecil hambatan listrik pada suatu rangkaian, makin besar pula Arus listriknya.

Arus listrik juga telah di pilih sebagai besaran dasar atau besaran pokok karena nilainya bersifat mikroskopis sehingga arus listrik mudah untuk di ukur.

Di dalam sebuah aliran listrik terdapat muatan listrik, muatan listrik pada dasarnya dibawa oleh Elektron dan Proton di dalam sebuah atom. Proton memiliki muatan positif, sedangkan Elektron memiliki muatan negatif. Namun, Proton sebagian besar hanya bergerak di dalam inti atom. Jadi, tugas untuk membawa muatan dari satu tempat ke tempat lainnya ini ditangani oleh Elektron. Hal ini dikarenakan elektron dalam bahan konduktor seperti logam sebagian besar bebas bergerak dari satu atom ke atom lainnya.

Atom dalam bahan konduktor memiliki banyak elektron bebas yang bergerak dari satu atom ke atom lainnya dengan arah yang acak (random atau tidak teratur) sehingga tidak mengalir ke satu arah tertentu. Namun ketika diberikan Tegangan pada konduktor tersebut, semua elektron bebas akan bergerak  ke arah yang sama sehingga menciptakan aliran arus listrik. Arus listrik atau Electric Current biasanya dilambangkan dengan huruf “I” yang artinya “intesity (intensitas)”. Sedangkan satuan Arus Listrik adalah Ampere yang biasa disingkat dengan huruf “A” atau “Ampere”. 1 Ampere arus listrik dapat didefinisikan sebagai jumlah elektron atau muatan (Q atau Coulombs) yang melewati titik tertentu dalam 1 detik (I = Q/t).

Sedangkan dalam Hukum Ohm menyatakan bahwa besarnya Arus Listrik (I) yang mengalir melalui sebuah penghantar atau konduktor adalah berbanding lurus dengan beda potensial atau Tegangan (V) dan berbanding terbalik dengan hambatannya (R).  Rumus Hukum Ohm adalah I = V/R.

Pada teori aliran arus listrik, kita mengenal ada dua teori tentang aliran arus listrik yaitu aliran arus listrik konvensional (conventional current flow) dan aliran elektron (electron flow).

Secara konvensional kita sering menyebutkan bahwa aliran listrik dalam suatu rangkaian elektronika adalah mengalir dari arah positif (+) ke arah negatif (-). Arah aliran arus konvensional ini adalah aliran arus yang menggunakan prinsip muatan, dimana arus listrik atau current sering didefinisikan sebagai aliran muatan listrik positif pada suatu penghantar dari potensial tinggi ke potensial rendah. Namun arah aliran arus listrik ini berlawanan dengan prinsip aliran elektron pada suatu penghantar. Konsep rangkaian dengan aliran arus listrik konvensional ini digunakan untuk mempermudahkan pemahaman terhadap arah aliran muatan listrik yaitu dari postif ke negatif.

Sedangkan arah aliran elektron (electron flow) berlawanan dengan arah aliran arus listrik konvensional. Karena pada dasarnya elektron adalah partikel yang bermuatan negatif dan bergerak bebas yang ditarik ke terminal positif. Dengan demikian, arah aliran listrik pada suatu rangkaian adalah aliran elektron dari kutub negatif baterai (katoda) dan kembali lagi ke kutub positif baterai (anoda). Jadi arah aliran elektron adalah dari arah negatif (-) ke arah positif (+).

Ada dua jenis arus listrik berdasarkan arah aliran listriknya. Arus listrik yang mengalir satu arah atau pada arah yang sama disebut dengan Arus Searah atau dalam bahasa Inggris disebut dengan Direct Current yang disingkat dengan DC. Contoh sumber Arus searah adalah seperti Baterai, Aki, Sel Surya dan Pencatu Daya (Power Supply).

Sedangkan arus listrik yang mengalir dengan arah arus yang selalu beubah-ubah disebut dengan Arus Bolak-balik atau dalam bahasa Inggris disebut dengan Alternating Current yang disingkat dengan AC. Bentuk gelombang AC pada umumnya adalah gelombang Sinus. Namun pada aplikasi tertentu juga terdapat bentuk gelombang segitiga dan bentuk gelombang persegi. Contoh sumber Arus bolak-balik adalah listrik PLN dan listrik yang dibangkitkan oleh generator listrik. Selain itu, gelombang audio dan gelombang radio juga merupakan bentuk gelombang AC.

Hambatan

Hambatan adalah penahanan atau perlawanan yang diterima oleh elektron-elektron yang mengalir pada sebuah penghantar oleh molekul-molekul yang ada di dalamnya. Setiap penghantar memberikan penahanan aliran arus listrik Hambatan listrik adalah perbandingan antara tegangan listrik dari suatu komponen elektronik (misalnya resistor) dengan arus listrik yang melewatinya. Hambatan listrik yang mempunyai satuan Ohm dapat dirumuskan sebagai R = V / I  atau R= δV / I di mana V adalah tegangan dan I adalah arus listrik.

Jika arus listrik kita analogikan dengan aliran air pada sebuah tangki air, kita analogikan hambatan dengan perahu atau rakit yang melintasi sungai dan terhalangi batu-batu besar hingga batang pohon untuk sampai ke tujuan, jika semakin banyak pengahalang maka semakin lambat perahu sampai di tujuan, begitu pula  pada hambatan sebagai batu atau batang pohon dan perahu sebagai arus listrik, semakin besar hambatan, maka semakin berkurang arus listrik yang melalui resistor.

Hambatan memiliki alat ukur yang disebut Galvanometer, Galvanometer tidak dapat digunakan untuk mengukur kuat arus maupun beda potensial listrik yang relatif besar, karena komponen-komponen internalnya yang tidak mendukung. Galvanometer bisa digunakan untuk mengukur kuat arus maupun beda potensial listrik yang besar, jika pada galvanometer tersebut dipasang hambatan eksternal (pada voltmeter disebut hambatan depan, sedangkan pada ampermeter disebut hambatan shunt). Galvanometer terdiri atas sebuah komponen kecil berlilitan banyak yang ditempatkan dalam sebuah medan magnet begitu rupa sehingga garis-garis medan akan menimbulkan kopel pada kumparan apabila melalui kumparan ini ada arus.

nah, itu mungkin penjelasan dari KitaMahir, cukup sekian dari KitaMahir

Wassaalamu'alaikum

Sampai jumpa pada kesempatan lain

Daftar Pustaka

Jati, Bambang Murdaka Eka.; Priyambodo.;2010: FISIKA DASAR  Listrik-Magnet-Optika-Fisika Modern untuk mahasiswa;Yogyakarta-ANDI

gurupendidikan.co.id

teknikelektronika.com

blog.ruangguru.com/hambatan-listrik

id.wikipedia.org/wiki/Hambatan_listrik

academia.edu




.