shortest path algorithm (djikstra, bellman-ford) ?· algoritma dijkstra, algoritma bellman ford...

Download SHORTEST PATH ALGORITHM (Djikstra, Bellman-Ford) ?· Algoritma Dijkstra, Algoritma Bellman Ford ...…

Post on 21-Jul-2018

213 views

Category:

Documents

0 download

Embed Size (px)

TRANSCRIPT

  • SHORTEST PATH ALGORITHM

    (Dijkstra, Bellman-Ford)

  • SHORTEST PATH ALGORITHM

    2

    Macam macam shortest Path

    Shortest path dapat dibedakan menjadi :

    Single Source Shortest Path

    Menentukan shortest path dari verteks sumber s V ke setiap verteks v VAlgoritma Dijkstra , Algoritma Bellman Ford

    Single Destination Shortest Path Menentukan shortest path ke suatu tempat t dari tiap verteks v

    Single Pair shortest path Menentukan shortest path dari u ke v jika diketahui pasangan u dan v

    All pair shortest path

    Untuk semua pasangan (u,v) ditentukan kemungkinan shortest pathnya. Floyd-Warshall

  • Masalah Shortest Path

    3

    Terdapat sebuah graph berbobot (weighted graph) dan dua vertices u dan v, kita ingin menemukan sebuah path dengan bobot minimum antara u dan v.

    panjang path adalah penjumlahan dari bobot sisi-sisinya (edges).

    Contoh :Shortest path antara jakarta surabaya Aplikasi

    Internet packet routing Flight reservations Driving directions

  • Pengertian Shortest Path

    4

    Misalkan sebuah directed graph EVG ,

    kvvvp ,....,, 10

    adalah

    Bobot dari sebuah path

    k

    i

    ii vvwpw1

    1 ,

    Bobot shotest path dari u ke v adalah

  • Shortest Path Properties

    Jika G tidak memiliki bobot, maka shortest pathnyadiperoleh dari panjang path yang paling minimal (jumlah edge-nya paling sedikit).

    Jika G merupakan graph dengan bobot tertentu, maka bobot darip adalah

    pvu

    vuwpw,

    ,

    5

  • Shortest Path Properties

    6

    Property 1:

    Sebuah subpath dari sebuah shortest path adalah sebuah shortest

    path

    Property 2:

    Terdapat sebuah tree dari shortest paths dari start vertex ke seluruh

    vertex lainnya

  • Syarat

    7

    Syarat yang harus dipenuhi oleh sebuah shortest path:

    Shortest path tidak memiliki cycle.

    Sebuah shortest path memiliki

    1V edge.

  • algoritma single source shortest path

    8

    Ada 2 macam algoritma yang digunakan dalam memecahkan masalah single source shortest path, yaitu:

    Algoritma Bellman Ford ialah algoritma yang digunakan untuk memecahkan masalah single shortest path yang memiliki edge dengan bobot negatif.

    Algoritma Djikstra ialah algoritma yang digunakan untuk memecahkan masalah single shortest path yang memiliki edge dengan bobot positif.

  • DJIKSTRA

    9

    Edsger Wybe Dijkstra lahir di Rotterdam 11 May 1930. ibunya seorang ahli metematika dan ayahnya seorang ahli kimia .

    th 1956 Dijkstra lulus dari Universitas Leiden dalam bidang mathematika dan teori fisika

    Th 1959 Dijkstra menerima PhD Universitas Amsterdam untuk thesisnya yg berjudul Communication with an Automatic Computer,

  • algoritma DIJKSTRA

    10

    Algoritma dijkstra adalah salah satu algoritma untuk memecahkan masalah single source shortest path

    Pada algoritma dijkstra pemecahan masalah diperuntukkan untuk sebuah Graph G=(V,E) yang berbobot non negatif.

    Diasumsikan w(i,j) 0 untuk masing-masing edge (i,j) E

  • Metode algoritma DIJKSTRA

    11

    1. Inisialisasi s (sumber) Pilih salah satu vertex sebagai sumber Maka d(s) = 0 Beri label 0 pada vertex s

    2. Untuk masing-masing edge e E Jika i adalah endpoint dari e yang sudah diberi label dan j

    adalah endpoint yang belum diberi label maka p(i,j) adalah = d(i) + w(i,j)

  • 12

    3. e adalah edge untuk T yang mempunyai nilai P terkecil Jika i adalah endpoint dari e yang sudah diberi label dan j

    adalah endpoint yang belum diberi label maka tambahkan e dan vertex j ke tree T

    d(j)=P(ij)

    Beri label d(j) pada vertex j

    4. Kembali ke no 2

    Metode algoritma DIJKSTRA

  • Metode algoritma DIJKSTRA menggunakan metode

    relaksasi

    13

    Relaksasi (i,j,w)

    Jika d(j)>d(i)+w(i,j)

    Maka d(j) adalah d(i) + w(i,j)

    Beri label d(j) pada j

    Metode dijkstra

  • Metode algoritma DIJKSTRA

    14

    Output algoritma dijkstra adalah spanning tree T, dimana path dari vertex s (sumber) ke masing-masing vertex v adalah sebuah shortest path dari s ke v dalam sebuah graph G.

    Label pada sebuah vertex adalah jarak dari s ke masing-masing vertex

  • Contoh 1

    15

    Tentukan shortest path dari A ke setiap v pada graph G

    berikut:

    A

    DC

    E

    7

    10

    6

    48

    5

    2

    15

    9

    B

  • Contoh 1(cont)

    16

    Spanning tree T kosong1. Inisialisasi s (sumber)

    pilih vertex A sebagai sumber. S=A, maka d(A)=0. beri label 0 pada A

    2. Untuk semua edge E, i adalah endpoint yg sudah di label , i = A j adalah endpoint yg belum dilabel j= B,C,D,E P(AB)=10, P(AC)=7, P(AE)=15

    A

    DC

    E

    7

    10

    6

    48

    5

    2

    15

    9

    B

    d(A)=0

  • Contoh 1(cont)

    17

    A

    DC

    E

    7

    10

    6

    48

    5

    2

    15

    9

    B

    d(A)=0

    d(C)=7

    3 . AC yang mempunyai nilai P terkecil sehingga C ditambahkan ke spanning tree T d(c)=P(AC)=7

    Beri label d (c) pada vertex c

  • Contoh 1(cont)

    18

    4. Kembali ke no 2 P(AB)=10,P(AE)=15,

    P(CB)=22,P(CD)=9,P(CE)=15

    CD yg mempunyai nilai P terkecil, sehingga D ditambahkan ke T

    Beri label d(D)=9

    A

    DC

    E

    7

    10

    6

    48

    5

    2

    15

    9

    B

    d(A)=0

    d(C)=7

    d(D)=9

  • 19

    Contoh 1(cont)

    5. Kembali ke no 2 P(AB)=10,P(AE)=15,

    P(CB)=22,P(CE)=15,P(DB)=15,P(DE)=13

    AB yg mempunyai nilai terkecil,sehingga B ditambahkan ke T

    Beri label d(B) =10

    A

    DC

    E

    7

    10

    6

    48

    5

    2

    15

    9

    B

    d(A)=0

    d(C)=7

    d(D)=9

    d(B)=10

  • Contoh 1(cont)

    20

    5. Kembali ke no 2 P(AE)=15, P(CB)=22,

    P(CE)=15,P(DB)=15,P(DE)=13, P(BE)=18

    DE yg mempunyai nilai terkecil,sehingga E ditambahkan ke T

    Beri label d(E) =13

    6. Semua vertex sudah diberi label

    7. selesai

    A

    DC

    E

    7

    10

    6

    48

    5

    2

    15

    9

    B

    d(A)=0

    d(C)=7

    d(B)=10

    d(D)=9

    d(E)=13

  • Aplikasi dijkstra

    21

    Dijkstra's algorithm determines the distances (costs) between a given vertex and all other vertices in a graph.This may be useful to determine alternatives in decision making.

    Dijkstra's algorithm is almost identical to that of Prim's.The algorithm begins at a specific vertex and extends outward within the graph, until all vertices have been reached.

    The only distinction is that Prim's algorithm stores a minimum cost edge whereas Dijkstra's algorithm stores the total cost from a source vertex to

    the current vertex.

    More simply, Dijkstra's algorithm stores a summation of minimum cost edges whereas Prim's algorithm stores at most one minimum cost edge.

    http://www.cs.usask.ca/resources/tutorials/csconcepts/1999_8/tutorial/definitions.htmlhttp://www.cs.usask.ca/resources/tutorials/csconcepts/1999_8/tutorial/definitions.htmlhttp://www.cs.usask.ca/resources/tutorials/csconcepts/1999_8/tutorial/definitions.htmlhttp://www.cs.usask.ca/resources/tutorials/csconcepts/1999_8/tutorial/definitions.htmlhttp://www.cs.usask.ca/resources/tutorials/csconcepts/1999_8/tutorial/definitions.html

  • contoh

    22

  • contoh

    23

  • contoh

    24

  • contoh

    25

  • contoh

    26

  • contoh

    27

  • soal

    28

    Tentukan shortest path dari A ke semua node pada graph berikut :

  • BELLMAN FORD

    29

    Algoritma ini merupakan pengembangan dari algoritma Djikstra,

    Algoritma Bellman Ford akan benar jika dan hanya jika graph tidak terdapat cycle dengan bobot negatif yang dicapai dari sumber s.

    No cycleDiasumsikan shortest paths tidak mempunyai cycles.

    shortest path maksimum mempunyai |V|-1 edge

  • Ciri ciri Algoritma Bellman-Ford :

    30

    Bekerja walaupun terdapat edge dengan bobot negative. Harus directed edge (jika tidak graph akan memiliki cycle dengan

    bobot negatif) Iterasi i menemukan seluruh shortest path dengan menggunakan i

    edge. Dapat mendeteksi cycle dengan bobot negatif jika ada.

  • Contoh algoritma bellman ford

    31

    BF(G,w,s) // G = Graph, w = weight, s=source Determine Single Source(G,s); set Distance(s) = 0; Predecessor(s) = nil; for each vertex v in G other than s,

    set Distance(v) = infinity, Predecessor(v) = nil;for i Distance(u) + w(u,v) then

    set Distance(v) = Distance(u) + w(u,v), Predecessor(v) = u; for each edge (u,r) in G do

    if Distance(r) > Distance(u) + w(u,r);return false; //This means that the graph contains a cycle of negative weight

    //and the shortest paths are not well defined

    return true; //Lengths of shortest paths are in Distance array

  • Algoritma :

    32

    Bellman-Ford(G,w,s)Inisialisasi single source(G,s)

    for i=1 to |V[G]|-1do for each edge (u,v) E[G]

    do RELAX(u,v)for each edge (u,v) E[G] ;untuk mencek apakah ada atau tidak cycle dgn bobot negatif

    do if d[v] > d[u] +w ((u,v)) ;jika hasil algoritma yang diinginkan belum didapat

    then return FALSEreturn TRUE;

  • Teknik relaksasi

    33

    Untuk setiap vertex v V, d (v) adalah bobot upper bound sebuah shortest path dari s ke v,

    d(v) disebut estimasi shortest-path

  • relaksasi

    34

    1. pada algorithm D

Recommended

View more >