Algoritma Dijkstra

Algoritma Dijkstra, (dinamai menurut penemunya, seorang ilmuwan komputer, Edsger Dijkstra), adalah sebuah algoritma rakus (greedy algorithm) yang dipakai dalam memecahkan permasalahan jarak terpendek (shortest path problem) untuk sebuah graf berarah (directed graph) dengan bobot-bobot sisi (edge weights) yang bernilai tak-negatif.

Misalnya, bila vertices dari sebuah graf melambangkan kota-kota dan bobot sisi (edge weights) melambangkan jarak antara kota-kota tersebut, maka algoritma Dijkstra dapat digunakan untuk menemukan jarak terpendek antara dua kota.

Input algoritma ini adalah sebuah graf berarah yang berbobot (weighted directed graph) G dan sebuah sumber vertex s dalam G dan V adalah himpunan semua vertices dalam graph G.

Setiap sisi dari graf ini adalah pasangan vertices (u,v) yang melambangkan hubungan dari vertex u ke vertex v. Himpunan semua tepi disebut E.

Bobot (weights) dari semua sisi dihitung dengan fungsi

Algoritma pencarian

Dalam ilmu komputer, sebuah algoritma pencarian dijelaskan secara luas adalah sebuah algoritma yang menerima masukan berupa sebuah masalah dan menghasilkan sebuah solusi untuk masalah tersebut, yang biasanya didapat dari evaluasi beberapa kemungkinan solusi. Sebagian besar algoritma yang dipelajari oleh ilmuwan komputer adalah algoritma pencarian. Himpunan semua kemungkinan solusi dari sebuah masalah disebut ruang pencarian. Algortima pencarian brute-force atau pencarian naif/uninformed menggunakan metode yang sederhana dan sangat intuitif pada ruang pencarian, sedangkan algoritma pencarian informed menggunakan heuristik untuk menerapkan pengetahuan tentang struktur dari ruang pencarian untuk berusaha mengurangi banyaknya waktu yang dipakai dalam pencarian.

Algoritma Bellman-Ford

Algoritma Bellman-Ford menghitung jarak terpendek (dari satu sumber) pada sebuah digraf berbobot. Maksudnya dari satu sumber ialah bahwa ia menghitung semua jarak terpendek yang berawal dari satu titik node. Algoritma Dijkstra dapat lebih cepat mencari hal yang sama dengan syarat tidak ada sisi (edge) yang berbobot negatif. Maka Algoritma Bellman-Ford hanya digunakan jika ada sisi berbobot negatif.

Algoritma Bellman-Ford menggunakan waktu sebesar O(V.E), di mana V dan E adalah banyaknya sisi dan titik.

Dalam konteks ini, bobot ekivalen dengan jarak dalam sebuah sisi.

Daftar algoritma

Sumber Ini Dari : http://id.wikipedia.org/wiki/Daftar_algoritma

Algoritma kombinatorial

Algoritma kombinatorial umum

• Algoritma pencari-siklus Floyd: iterasi untuk mencari siklus dalam barisan/sekuens
• (uniformly distributed) Pseudorandom number generators:
  • Blum Blum Shub
  • Mersenne twister
• Robinson-Schensted algorithm: generates permutations from pairs of Young tableaux

Algoritma graph

• Algoritma Bellman-Ford: menghitung jarak terpendek pada graf berbobot, di mana sisi bisa memiliki bobot negatif
• Algoritma Dijkstra: menghitung jarak terpendek pada graf berbobot, tanpa sisi berbobot negatif.
• Algoritma Floyd-Warshall: menghitung solusi jarak terpendek untuk semua pasang titik pada sebuah graf berarah dan berbobot
• Algoritma Kruskal: mencari pohon rentang minimum pada sebuah graf
• Algoritma Prim: mencari pohon rentang minimum pada sebuah graf
• Algoritma Boruvka: mencari pohon rentang minimum pada sebuah graf
• Algoritma Ford-Fulkerson: computes the maximum flow in a graph
• Algoritma Edmonds-Karp: implementation of Ford-Fulkerson
• Nonblocking Minimal Spanning Switch say, for a telephone exchange
• Spring based algorithm: algorithm for graph drawing
• Topological sort
• Algoritma Hungaria: algorithm for finding a perfect matching

Pengertian Algoritma

Dalam matematika dan komputasi, algoritma atau algoritme merupakan kumpulan perintah untuk menyelesaikan suatu masalah. Perintah-perintah ini dapat diterjemahkan secara bertahap dari awal hingga akhir. Masalah tersebut dapat berupa apa saja, dengan catatan untuk setiap masalah, ada kriteria kondisi awal yang harus dipenuhi sebelum menjalankan algoritma. Algoritma akan dapat selalu berakhir untuk semua kondisi awal yang memenuhi kriteria, dalam hal ini berbeda dengan heuristik. Algoritma sering mempunyai langkah pengulangan (iterasi) atau memerlukan keputusan (logika Boolean dan perbandingan) sampai tugasnya selesai.

Desain dan analisis algoritma adalah suatu cabang khusus dalam ilmu komputer yang mempelajari karakteristik dan performa dari suatu algoritma dalam menyelesaikan masalah, terlepas dari implementasi algoritma tersebut. Dalam cabang disiplin ini algoritma dipelajari secara abstrak, terlepas dari sistem komputer atau bahasa pemrograman yang digunakan. Algoritma yang berbeda dapat diterapkan pada suatu masalah dengan kriteria yang sama.

Kompleksitas dari suatu algoritma merupakan ukuran seberapa banyak komputasi yang dibutuhkan algoritma tersebut untuk menyelesaikan masalah. Secara informal, algoritma yang dapat menyelesaikan suatu permasalahan dalam waktu yang singkat memiliki kompleksitas yang rendah, sementara algoritma yang membutuhkan waktu lama untuk menyelesaikan masalahnya mempunyai kompleksitas yang tinggi.