ALGORITMA DIJKSTRA

ALGORITMA DIJKSTRA  digunakan untuk mencari rute terpendek……

berikut ini contohnya ::

Graph G dengan matrik berhubungan langsung sebagai berikut ::

A B C D E F G
A 0 60 70
B 60 0 50 50 20
C 70 50 40 70
D 50 40 0 60 50
E 20 60 0 30 40
F 70 50 30 0 50
G 40 50 0

GAMBAR GRAPHNYA SEPERTI INI ::

untuk bobotnya dapat dilihat pada tabel yang sebenarnya sebuah “matrik berhubungan langsung” di atas..

PENYELESAIANNYA ::

Titik Vi A B C D E F G
x (Vi) 0
T A B C D E F G
Titik Vi A B C D E F G
x (Vi) 40 50 0
T A B C D E F
Titik Vi A B C D E F G
x (Vi) 60 100 40 50 0
T A B C D F
Titik Vi A B C D E F G
x (Vi) 60 120 100 40 50 0
T A B C D
Titik Vi A B C D E F G
x (Vi) 120 60 110 100 40 50 0
T A C D
Titik Vi A B C D E F G
x (Vi) 120 60 110 100 40 50 0
T A C
Titik Vi A B C D E F G
x (Vi) 120 60 110 100 40 50 0
T A
Titik Vi A B C D E F G
x (Vi) 120 60 110 100 40 50 0
T

Jadi secara umum cara untuk menyelesaikan algoritma dijkstra adalah ::

Input :: Graph bobot G dengan s,t elemen V(G)

Step 1 :: Label titik dengan λ(s)=0 dan untuk setiap titik v di G selain s, label titik v dengan λ(v)=∞ (dalam praktek ∞ diganti dengan bilangan yang “sangat besar” atau diibaratkan sebagai bilangan yang sangat besar). Tulis T = V(G).

Step 2 :: Misalkan u ε T denga λ(u) minimum

Step 3 :: Jika u = t, STOP, dan beri pesan: “Panjang lintasan terpendek dari s ke t adalah λ(t)”.

Step 4 :: untuk setiap sisi e = uv, v ε T, diganti label v dengan λ(v)= minimum {λ(v),λ(u)+W(e)}.

Step 5 :: Tulis T = T – {u}, dan kembali ke step 2………

keterangan simbol ::

λ = Lamda

ε = elemen

About NICO MATEMATIKA

Welcome to my blog. My name is Nico. Admin of this blog. I am a student majoring in mathematics who dreams of becoming a professor of mathematics. I live in Kwadungan, Ngawi, East Java. Hopefully in all the posts I can make a good learning material to the intellectual life of the nation. After the read, leave a comment. I always accept criticism suggestion to build a better me again .. Thanks for visiting .. : mrgreen:

Posted on June 15, 2011, in teory graph and tagged , , . Bookmark the permalink. 7 Comments.

LEAVE A COMMENT IN HERE. COMMENTING IN HERE IS ALWAYS AUTO APPROVE. PLEASE NO SPAM!!! BECAUSE I HATE SPAM... THANKS A LOT..... :mrgreen:

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: