Algoritma Dijkstra dan pelaksanaannya

Ada daerah yang terpisah yang disebut teori graf dalam matematika dan ilmu komputer. Sebagai bagian dari set dan untuk memecahkan berbagai masalah, seperti mencari jalur terpendek antara simpul. Salah satu umum di kalangan matematikawan cara memecahkan masalah ini telah lama menjadi algoritma yang Dijkstra.

Apa grafik matematika

Hal ini diyakini bahwa gagasan grafik itu mulai digunakan pada abad kedelapan belas leonardom Eylerom. Dialah yang mengumumkan rumusan dan solusi dari salah satu masalah klasik teori ini - tujuh jembatan Königsberg. Dalam rangka untuk menjelaskan objek dari teori ini sering menggunakan analogi ini sebagai gerakan antara kota yang berbeda. Kemudian grafik di pesawat akan seluruh diagram rute, di mana simpul menjadi item tertentu (misalnya, kota), dan ujung-ujungnya - jalan dari satu titik ke yang lain (analog jalan antara kota). Algoritma Dijkstra, di samping metode lainnya, dapat memberikan solusi untuk masalah ini.

Menemukan jalan terpendek

Salah satu tugas umum dari teori graf adalah satu di mana Anda perlu untuk menentukan jalur biaya yang optimal antara dua titik. Hal ini dimungkinkan untuk mengurangi pesawat untuk keputusan grafik di mana simpul - kota - yang rusuk saling berhubungan, yang merupakan jalan mungkin. Setiap jalan memiliki panjang sendiri, oleh karena itu, di situ harus menghabiskan uang. Jumlah ini setara dengan berat tepi dalam grafik. Maka masalah dalam praktek dapat dirumuskan sebagai berikut: bagaimana untuk membuka jalan dari satu kota ke kota lain, akan dihabiskan untuk sarana minimum jalan.

cara untuk memecahkan

Untuk mengatasi masalah ini kita telah diciptakan oleh beberapa algoritma yang telah menjadi dikenal secara luas di dunia ilmiah. Sebagai contoh, algoritma Floyd - Uorshella, Ford - Bellman. Cara klasik untuk menemukan solusi juga algoritma Dijkstra. Hal ini dapat digunakan untuk tertimbang (berat dikenal dari setiap tepi) dari grafik, dan untuk mencairkan. Untuk menemukan cara utama Anda harus melakukan beberapa langkah.

algoritma Dijkstra

Titik metode ini terletak pada kenyataan bahwa semua simpul dari biaya, dimulai dengan yang diberikan, dimana setiap tag yang ditugaskan nilai tertentu. Maka hasilnya akan mencakup simpul yang label yang minimal. Di atas langkah awal pertama akan ditandai dengan nilai 0. Kemudian, semua puncak berikut dianggap, yaitu orang yang dapat dicapai dari sumber. Mereka diberi label, nilai yang ditentukan sebagai jumlah dari kode sumber dan berat dari jalan. Dari atas langkah berikutnya, pilih salah satu yang memiliki nilai terkecil dari label, dan mempelajari semua simpul dalam dari itu kita bisa pergi tanpa menggunakan node intermediate. Tentukan label baru sama dengan puncak label - kode sumber ditambah berat dari jalan. Jika nilai kurang dari label atas, label berubah. Jika tidak, itu tetap nilai asli. Pada saat yang sama dalam array terpisah, yang dimensi sama dengan jumlah simpul, menyimpan hasil optimasi, di mana dan dengan cara yang ditentukan. Untuk menerapkan metode seperti algoritma Dijkstra, Pascal menawarkan cara yang sangat nyaman. Algoritma ini memiliki keuntungan yaitu dapat dengan mudah menjadi dasar untuk sebuah program yang memiliki ukuran kecil. Contoh produk perangkat lunak tersebut mudah untuk menemukan di Internet.

solusi dle alat yang berbeda Anda dapat menggunakan tugas untuk menemukan jalan optimal. Untuk solusi seperti algoritma Dijkstra, Delphi akan membuat bentuk yang nyaman input data visual dan output hasil akhir.