, ,

Dijkstra Rute Terpendek

Terjemahkan dalam bahasa
Terjemahkan dalam bahasa Inggris

Seperti banyak metode software Map. Salah satu metode yang sering digunakan untuk mengukur atau menghitung arah dari A ke B dengan menggunakan Dijkstra Algoritma Shortest Path. Saya telah mengembangkan dan menemukan banyak kode sumber untuk bagaimana menggunakan algoritma ini.

Algoritma Dijkstra, dikandung oleh ilmuwan komputer Edsger Dijkstra pada tahun 1956 dan diterbitkan pada tahun 1959, adalah algoritma pencarian grafik yang memecahkan satu sumber masalah jalan terpendek untuk grafik dengan biaya jalur tepi non-negatif, menghasilkan pohon jalur terpendek (SPT). Algoritma ini sering digunakan dalam routing dan sebagai subroutine dalam algoritma grafik lainnya. * Algoritma Dijkstra

Untuk titik tertentu sumber (node) dalam grafik, algoritma menemukan jalan dengan biaya terendah (yaitu jalur terpendek) antara yang simpul dan setiap simpul lainnya

Pertama jangan bingung dengan simpul, simpul atau node. Mereka semua mewakili fungsi yang sama. Mewakili lokasi.

contoh:

Jika kita bekerja di sebuah situs web yang dirancang untuk Sistem Informasi Geografis dan memiliki sistem perhitungan rute, Dijkstra dapat digunakan untuk menghitung tujuan dari node A ke B. Untuk melakukannya, kita perlu membuat peta yang terdiri dari berbagai lokasi. Sebuah lokasi diwakili dengan node atau simpul. Jadi sebagai kesimpulan, Dijkstra sebenarnya suatu algoritma yang akan memilih yang terbaik atau SPT dari node terpilih sebagai contoh dari node A ke node B. Hasilnya datang dari semua node dihitung yang terdiri antara node A ke node B. Untuk setiap node antara node tujuan A ke B disebut grafik dan dihubungkan sebagai matriks adjacency, dan adjacency matriks ini merupakan peta.

Jadi ini adalah contoh jika kita menggunakan Dijkstra di Website Information Peta, seperti biasanya beberapa situs digabung dengan algoritma Google Map, dan banyak orang lain sumber bebas peta seperti Open Street Map, Bing, dll

Untuk menghitung rute dengan Dijkstra pada peta, kita harus membuat peta. Peta itu merupakan node yang terhubung. Dan masing-masing dari semua node yang terhubung disebut grafik. Dan semua node terhubung sebagai grafik terhubung disebut adjacency matriks atau juga bisa mewakili sebagai daftar adjacency.

Apa simpul atau juga disebut node?

“Simpul / node / vertex merupakan representasi dari lokasi.”

Contoh :

langkah1

Node 1 : Jalan Teuku Umar
Node 2 : Jalan Imam Bonjol
Node 3 : Jalan Raya Kuta
dan seterusnya.

Apa yang dimaksud dengan graph ?

Graph adalah struktur data yang terdiri dari dua komponen berikut:
1 Satu set terbatas simpul juga disebut sebagai node.
2. himpunan terhingga pasangan terurut berbentuk (u, v) disebut sebagai tepi. Pasangan bentuk (u, v) menunjukkan bahwa ada keunggulan dari titik u ke simpul v. Tepi mungkin berisi berat / nilai / biaya.

langkah1

Node 1: Jalan Teuku Umar, terhubung dengan Node 2: Jalan Imam Bonjol dan disebut graph, katakanlah graph 1, dan memiliki berat / biaya 7 KM.
Node 1 Node terhubung dengan 3: Jalan Raya Kuta, dan kami menyebutnya graph 2, dan memiliki berat 9 KM.
Selanjutnya, kita harus Node 2 Node terhubung dengan 3, dan kami menyebutnya graph 3, dan memiliki berat 13 KM.
dan seterusnya.

Berikutnya adalah node adjacency, Apakah yang dimaksud dengan adjacency?

“Node Adjacency adalah Representasi Graph. Adjacency dapat dibangun sebagai matriks atau dalam daftar. Jika membangun dalam matriks itu disebut matriks adjacency, dan jika membangun dalam daftar itu disebut daftar adjacency. ”

allnodes

Representasi Node Adjacency Matrix

Sekarang saya akan menjelaskan bagaimana algoritma baca node (cara bekerja Dijkstra itu sendiri 😀 )

1. Pertama menemukan titik di mana itu akan menjadi simpul awal, dan memberikan bobot dengan jarak simpul pertama ke simpul terdekat satu per satu, Dijkstra pencari akan berkembang dari satu titik ke titik yang lain dan titik ke tahap berikutnya demi tahap . Ini adalah urutan logis dari algoritma Dijkstra:

2. Berikan nilai bobot (jarak) untuk setiap titik ke titik yang lain, dan kemudian menetapkan nilai 0 pada node awal dan nilai tak terbatas ke node lain (tidak diisi)
3. Set semua node “Belum terjamah” dan set node awal sebagai “Node keberangkatan”
4. Of keberangkatan node, pertimbangkan node tetangga yang belum terjamah dan menghitung jarak dari titik keberangkatan. Misalnya, jika keberangkatan titik A ke B memiliki berat 6 dan jarak dari B ke node C adalah 2, maka jarak ke C melewati B menjadi 6 + 2 = 8 Jika jarak ini lebih kecil dari jarak sebelumnya (yang telah direkam sebelumnya) hapus data lama, menyimpan data pada jarak ke jarak yang baru.
5. Ketika kita dilakukan mengingat jarak ke setiap node tetangga, node yang telah menyentuh tandai sebagai “Node terjamah”. Node terjamah tidak akan pernah diperiksa lagi, jarak yang disimpan adalah jarak yang terakhir dan paling sedikit berat badan.
6. Set “Node belum terjamah” dengan jarak terkecil (dari keberangkatan node) sebagai “Node Keberangkatan” dan kemudian lanjutkan untuk kembali ke langkah 4

Berikut adalah langkah-demi-langkah secara rinci pencarian jalur terpendek dimulai dari node awal ke node tujuan dengan nilai jarak terkecil.

1. Perlakukan node 1 sebagai simpul keberangkatan, Node tujuan adalah nilai simpul 5, setiap tepi yang dihubungkan antara node telah memiliki nilai

langkah 1

 

Langkah 1

2. Dijkstra melakukan kalkulasi terhadap node tetangga yang terhubung langsung dengan node keberangkatan (node 1), dan hasil yang didapat adalah node 2 karena bobot nilai node 2 paling kecil dibandingkan nilai pada node lain, nilai = 7 (0+7).

langkah2

Langkah 2

3. Node 2 diset menjadi node keberangkatan dan ditandai sebagi node yang telah terjamah. Dijkstra melakukan kalkulasi kembali terhadap node-node tetangga yang terhubung langsung dengan node yang telah terjamah. Dan kalkulasi dijkstra menunjukan bahwa node 3 yang menjadi node keberangkatan selanjutnya karena bobotnya yang paling kecil dari hasil kalkulasi terakhir, nilai 9 (0+9).

langkah3

 

Langkah 3

4. Perhitungan berlanjut dengan node 3 ditandai menjadi node yang telah terjamah. Dari semua node tetangga belum terjamah yang terhubung langsung dengan node terjamah, node selanjutnya yang ditandai menjadi node terjamah adalah node 6 karena nilai bobot yang terkecil, nilai 11 (9+2).

langkah4

 

Langkah 4

5. Node 6 menjadi node terjamah, dijkstra melakukan kalkulasi kembali, dan menemukan bahwa node 5 (node tujuan ) telah tercapai lewat node 6. Jalur terpendeknya adalah 1-3-6-5, dan niilai bobot yang didapat adalah 20 (11+9). Bila node tujuan telah tercapai maka kalkulasi dijkstra dinyatakan selesai

langkah5

 

Langkah 5

Maka gambarannya secara detil, sebagai berikut:

Dijkstra_Animation

 

Semoga membantu,

GZ

 

0 replies

Leave a Reply

Want to join the discussion?
Feel free to contribute!

Leave a Reply

Your email address will not be published. Required fields are marked *