Algoritma Dijkstra

Dari Wikipedia bahasa Indonesia, ensiklopedia bebas
Lompat ke: navigasi, cari
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

w: E → [0, ∞)

jadi w(u,v) adalah jarak tak-negatif dari vertex u ke vertex v.

Ongkos (cost) dari sebuah sisi dapat dianggap sebagai jarak antara dua vertex, yaitu jumlah jarak semua sisi dalam jalur tersebut. Untuk sepasang vertex s dan t dalam V, algoritma ini menghitung jarak terpendek dari s ke t.

Pseudocode[sunting | sunting sumber]

  function Dijkstra(Graph, source):
       for each vertex v in Graph:                                // Initializations
           dist[v] := infinity ;                                  // Unknown distance function from 
                                                                  // source to v
           previous[v] := undefined ;                             // Previous node in optimal path
       end for                                                    // from source
       
       dist[source] := 0 ;                                        // Distance from source to source
       Q := the set of all nodes in Graph ;                       // All nodes in the graph are
                                                                 // unoptimized - thus are in Q
      while Q is not empty:                                      // The main loop
          u := vertex in Q with smallest distance in dist[] ;    // Start node in first case
          remove u from Q ;
          if dist[u] = infinity:
              break ;                                            // all remaining vertices are
          end if                                                 // inaccessible from source
          
          for each neighbor v of u:                              // where v has not yet been 
                                                                 // removed from Q.
              alt := dist[u] + dist_between(u, v) ;
              if alt < dist[v]:                                  // Relax (u,v,a)
                  dist[v] := alt ;
                  previous[v] := u ;
                  decrease-key v in Q;                           // Reorder v in the Queue
              end if
          end for
      end while
  return dist;

Rujukan[sunting | sunting sumber]

Hendri Antomy--Master computer

Lihat pula[sunting | sunting sumber]

Pranala luar[sunting | sunting sumber]