30
Mar
09

[tugas PTI 5] algoritma

Algoritma Floyd-Warshall

Algoritma Floyd-Warshall menghitung jarak terpendek untuk semua pasangan titik pada sebuah graf, dan melakukannya dalam waktu berorde kubik.

Algoritma Floyd-Warshall memiliki input graf berarah dan berbobot (V,E), yang berupa daftar titik (node/vertex V) dan daftar sisi (edge E).

function fw(int[1..n,1..n] graph) {

// Inisialisasi

var int[1..n,1..n] jarak := graph

var int[1..n,1..n] sebelum

for i from 1 to n

for j from 1 to n

if jarak[i,j] < Tak-hingga

sebelum[i,j] := i

// Perulangan utama pada algoritma

for k from 1 to n

for i from 1 to n

for j from 1 to n

if jarak[i,j] > jarak[i,k] + jarak[k,j]

jarak[i,j] = jarak[i,k] + jarak[k,j]

sebelum[i,j] = sebelum[k,j]

return jarak


Algoritma Bellman-Ford

Algoritma Bellman-Ford menyelesaikan masalah garis terpendek single-source untuk grafik dengan dua simpul(node) positive and negative. Jika kamu hanya membutuhkan untuk menyelesaikan masalah jalur terpendek untuk node positive, Algoritma Dijkstra memberikN lternatif yg lebih efisien. Jika semua node sama BFS adalah alternative yang lebih efisien.

BELLMAN-FORD(G)

// Optional initialization

for setiap root u di V

d[u] := infinity

p[u] := u

end for

for i := 1 to |V|-1

for setiap node (u,v) di E

RELAX(u, v, w, d, p)

end for

end for

for setiap node (u,v) di E

if (w(u,v) + d[u] < d[v])

return (false, , )

else

end for

return (true, p, d)

Node uji (u,v)

node (u,v) tidak diminimalis

node (u,v) diminimalis


Depth-first search (DFS)

Depth-first search (DFS) melakukan pencarian secara preorder. Mengunjungi anak suatu simpul sebelum simpul tetangganya

Algoritma

Step 1: letakkan root parent di tempat yang paling atas

Step 2: Lakukan looping hingga titik terakhir

Step 3: letakkan titik yang terhubung dengan root parent pada satu garis lurus

Step 4: lakukan pengecekan, jika titik tidak memiliki child letakkan pada garis, pindah ke titik selanjutnya

Step 5: jika titik yang ditemui memiliki child hubungkan dengan titik sebelumnya

//

public void dfs()

{

//DFS menggunakan struktur data yang teratur

Stack s=new Stack();

s.push(this.rootNode);

rootNode.visited=true;

printNode(rootNode);

while(!s.isEmpty())

{

Node n=(Node)s.peek();

Node child=getUnvisitedChildNode(n);

if(child!=null)

{

child.visited=true;

printNode(child);

s.push(child);

}

else

{

s.pop();

}

}

//titik yang dikunjungi telah kosong

clearNodes();

}

//

· Dengan memakai stack yang direpresentasikan dengan array.

Procedure DFS_NonRekursif (input V : char)

{ I.S. terdefinisi A yaitu matriks ketetanggan dari sebuah graf V adalah simpul yang akan diproses

F.S. Simpul V telah di proses

}

Kamus

W : char

S : stack

Procedure CreateStack (output S : Stack)

{I.S : sembarang

F.S : sebuah stack S kosong siap dipakai terdefenisi }

Function IsEmptyStack (S : Stack ) <- boolean

{Test stack kosong: False jika tumpukan tidak kosong dan mengirim true jika tumpukan kosong

}

Procedure PushStack (input/output S : Stack; Input P : address)

{menambahkan elemen baru pada TOP, dengan Elemen yang sudah diketahui alamatnya

}

Procedure PopStack (input/output S : Stack; Output P : address)

{I.S : stack tidak kosong

F.S: alamat elemen TOP disimpan pada P, shg Informasi dapat diakses melalui P }

{Menghapus elemen stack, stack tidak boleh Kosong dan mungkin setelah penghapusan Stack menjadi kosong }

Procedure proses (input V : char)

{I.S: V adalah simpul yang akan Diproses

F.S: simpul V telah diproses

}

Algoritma

Proses (V)

Visited[ V] <- true

While not IsEmptyStack (S) do

PopStack (S,V)

While (V<>Nil) do

If (A[V,W] =1) and (not visited [W] ) then

Proses(W)

PushStack (S,W)

Visited[W] 􀃅 true

Endif

Endwhile

Endwhile

{IsEmptyStack (S)}


Breadth First Search (BFS)

Pencarian dilakukan pada semua node dalam setiap level secara berurutan dari kiri ke kanan. Jika pada satu level belum ditemukan solusi, maka pencarian dilanjutkan pada level berikutnya. Demikia n seterusnya sampai ditemukan solusi.

Pseucode BFS

Inisialisasi : 0 = {S}

While 0 ? empty

Tarik 1, elemen pertama di 0

If 1 = Goal

Sukses dan keluar

Else

Node_anak = ekspansi (1)

Eliminasi node anak yang loop

Anak yang tersisa dibelakang 0

End

source: wikipedia

Continue


0 Responses to “[tugas PTI 5] algoritma”



  1. Leave a Comment

Leave a Reply

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


WELCOME ON DARK_DEVIL

This is official site of darkdevil4bloodyvenus... A place where you can enjoy the darkness of life...

RULE #1!

i let you to take away half or a whole part of my posting, but please put a link on ur blog to mine.. okeii!! ^^ i'll really appreciate it...

RULE #2!

everybodies here must love korean stuff!! no harshing anyothers please...

RULE #3!

feel free to leave a comment!! your argument are very welcome...

Donate to Darkdevil4BloodyVenus for more download link, update news and more! ^^

SUPER JUNIOR!!

DBSK

SHINee

2PM

2AM

big bang

FT ISLAND

BI “RAIN”…

MBLAQ

U-Kiss

b2st

Yoon Eun Hye

WONDER GIRLS

Brown Eyed Girls

f(x)

SNSD

ZE:A

Daeguknamah (D-NA)

I’M A FAN OF…..

SHINEE – Lucifer

jaebum

DEATH NOTE

COFFEE PRINCE

OURAN HIGH SCHOOL

MARS

ADVERTISEMENT

March 2009
M T W T F S S
« Feb   Apr »
 1
2345678
9101112131415
16171819202122
23242526272829
3031  

Visitor

  • 231,625 hits

Top Clicks

  • None

CATEGORIES


%d bloggers like this: