Flashindo Academy
Selamat datang di Flashindo Academy, akademi pembuat Flash :wave:
Di sini Anda bisa berbagi proyek/karya Flash-mu dan lain-lain disini :)

Ayo langsung join :D dan akun langsung aktif lho.. :-


Akademi Pembuat Flash
 
HomeTata TertibFAQSearchMemberlistUsergroupsRegisterLog in

Share | 
 

 [Programming] Dijkstra's Algorithm

View previous topic View next topic Go down 
AuthorMessage
ListRA-92
The Headmaster
avatar

Posts : 93
Cash : 394
Appreciations : 0
Location : antara ada dan tiada~ :-
Jenjang Pendidikan : Kuliah
Join date : 2010-10-15
Status : ADT Listra Linier Berkait :hammer:

PostSubject: [Programming] Dijkstra's Algorithm   Fri Oct 22, 2010 1:26 pm


Algoritma Dijkstra
Algoritma Dijkstra, yang ditemukan oleh ilmuwan komputer asal Belanda Edsger Dijkstra pada tahun 1956 dan dipublikasikan tahun 1959, adalah sebuah algoritma pencarian graf yang menyelesaikan persoalan jalan terpendek untuk suatu graf dengan jarak nonnegatif, menghasilkan suatu pohon jalan terpendek. Algoritma ini sering digunakan untuk mencari rute.

Untuk verteks (titik) sumber yang diberikan dalam graf, algoritma mencari jalan dengan jarak terpendek di antara verteks itu dan tiap verteks lain. Ini dapat pula digunakan untuk mencari jarak jalan terpendek dari verteks tunggal ke verteks tujuan tunggal dengan menghentikan algoritma sekali jalan terpendek ke tujuan telah ditentukan. Algoritma ini adalah sebagai berikut.
Algoritma RSA:
 

Pseudocode (Pseudopascal)
Dalam pseucode algoritma berikut ini, kode u := vertex in Q with smallest dist[] mencari verteks u dalam set verteks Q yang mempunyai nilai dist[u] terkecil.
Code:
 1  function Dijkstra(Graph, source):
 2      for each vertex v in Graph:          // Initializations
 3          dist[v] := infinity ;              // Unknown distance function from source to v
 4          previous[v] := undefined ;        // Previous node in optimal path from source
 5      end for ;
 6      dist[source] := 0 ;                    // Distance from source to source
 7      Q := the set of all nodes in Graph ;
        // All nodes in the graph are unoptimized - thus are in Q
 8      while Q is not empty:                // The main loop
 9          u := vertex in Q with smallest dist[] ;
10          if dist[u] = infinity:
11              break ;                        // all remaining vertices are inaccessible from source
12          fi ;
13          remove u from Q ;
14          for each neighbor v of u:        // where v has not yet been removed from Q.
15              alt := dist[u] + dist_between(u, v) ;
16              if alt < dist[v]:            // Relax (u,v,a)
17                  dist[v] := alt ;
18                  previous[v] := u ;
19              fi  ;
20          end for ;
21      end while ;
22      return dist[] ;
23  end Dijkstra.
Jika kita hanya tertuju pada alur jalan terpendek antara verteks sumber dan tujuan, kita dapat menghentikan pencarian pada pseudocode baris 11 jika u = tujuan. Sekarang kita dapat membaca jalan terpendek dari sumber ke tujuan dengan iterasi:
Code:
1  S := empty sequence
2  u := target
3  while previous[u] is defined:
4      insert u at the beginning of S
5      u := previous[u]

Beberapa keterangan dan penjelasan mengenai Algoritma Dijkstra yang perlu diperhatikan
- "Tetangga" verteks di sini maksudnya adalah verteks-verteks yang dituju oleh koneksi dari verteks current.
- Koneksi antarverteks tidak selalu dua arah, untuk koneksi satu arah (misalnya yang menghubungkan verteks A ke B), B adalah tetangga A, namun B bukan tetangga A.

Sumber
- http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
Back to top Go down
View user profile http://flashindo.forumotion.net
 
[Programming] Dijkstra's Algorithm
View previous topic View next topic Back to top 
Page 1 of 1
 Similar topics
-
» Which programming languages are required for web development?

Permissions in this forum:You cannot reply to topics in this forum
Flashindo Academy :: Education Class :: Programming-
Jump to: