Single source shortest pathdijkstra

Single source shortest pathdijkstra

wijanarto

Terminologi

• Dijkstra’s algorithm di pakai untuk menemukanshortest path dari satu source ke seluruh vertekdalam graph.

• Algo ini menggunakan 2 himp node yaitu S dan C.• Pada himp. S berisi node yang terpilih yang

memiliki jarak minimal dari source.• Pada himp. C berisi node selain yang terpilih

dalam S, yang belum di ketahui dan merupakankandidat yang akan di pilih pada langkahberikutnya

• Dijkstra’s algorithm di pakai untuk menemukanshortest path dari satu source ke seluruh vertekdalam graph.

• Algo ini menggunakan 2 himp node yaitu S dan C.• Pada himp. S berisi node yang terpilih yang

memiliki jarak minimal dari source.• Pada himp. C berisi node selain yang terpilih

dalam S, yang belum di ketahui dan merupakankandidat yang akan di pilih pada langkahberikutnya

Terminologi

• Dengan demikian kita akan peroleh N=SC• Pada saat algoritma berhenti, S berisi seluruh

node dari G dan masalah terselesaikan.• Tiap langkah yang terpilih dalam C merupakan

jarak terkecil pada source dan di tambahkanke S

• Dengan demikian kita akan peroleh N=SC• Pada saat algoritma berhenti, S berisi seluruh

node dari G dan masalah terselesaikan.• Tiap langkah yang terpilih dalam C merupakan

jarak terkecil pada source dan di tambahkanke S

Abstraksi

• Diberikan G={V,E}, directed graph denganfungsi l:ER+

• Problem mencari jalur terpendek dari S ke T

0.5

5

• Diberikan G={V,E}, directed graph denganfungsi l:ER+

• Problem mencari jalur terpendek dari S ke T

1.1

2

33.1

7

Ssource

T (destination)

Abstraksi

• Berapa path yang mungkin dari graph G tadi?

• Shortest path = 7.2

8.6

• Berapa path yang mungkin dari graph G tadi?

• Shortest path = 7.2

8.6

7.2

8.1

98.6

Abstraksi

• Dapatkah kita mencari SP dengan cara sepertisebelumnya ??? Kenapa ??

• Sebab dalam praktek, mungkin terdapat Gyang besar dengan path yang tidak di ketahui,misal :

• Jika terdapat k diamond, berapa vertek-nya• Berapa Path??

• Dapatkah kita mencari SP dengan cara sepertisebelumnya ??? Kenapa ??

• Sebab dalam praktek, mungkin terdapat Gyang besar dengan path yang tidak di ketahui,misal :

• Jika terdapat k diamond, berapa vertek-nya• Berapa Path??

S T

3k+1

2k diantara S dan T

Abstraksi

• Sehingga jika terdapat n vertek, maka terdapat2 n/3 path

• Lalu bagaimana kita mencari SP pada problemseperti ini??

• Untuk melakukannya kita harus tahu propertydari SP

• Sehingga jika terdapat n vertek, maka terdapat2 n/3 path

• Lalu bagaimana kita mencari SP pada problemseperti ini??

• Untuk melakukannya kita harus tahu propertydari SP

ST

0.5 1

1.1 0.2

0.3 0.4

0.5 0.8

Property SP(single short shortest path)

• Di berikan path dalam G, dari s ke t

• X salah satu vertek dalam path s-t, sehinggaterdapat path s-x dalam s-t, dimanamerupakan SP

• Jadi Algoritma yang akan di bicarakan adalahSP dalam setiap vertek dalam GSSSP

st

x

• Di berikan path dalam G, dari s ke t

• X salah satu vertek dalam path s-t, sehinggaterdapat path s-x dalam s-t, dimanamerupakan SP

• Jadi Algoritma yang akan di bicarakan adalahSP dalam setiap vertek dalam GSSSP

x

contoh

• Misal l1<l2<l3, merupakan adj vertek dari s kev1,v2,v3

• Dikatakan bahwa sp dari s –v1 adalah l1, danberlaku untuk semua path dari s ke setiap vdalam G, karena l adalah bernilai positive

• Dinotasikan distance/jarak padad[v1]=l1,d[v2]<=l2, dst

• Misal l1<l2<l3, merupakan adj vertek dari s kev1,v2,v3

• Dikatakan bahwa sp dari s –v1 adalah l1, danberlaku untuk semua path dari s ke setiap vdalam G, karena l adalah bernilai positive

• Dinotasikan distance/jarak padad[v1]=l1,d[v2]<=l2, dst

s

l3

l2

l1v1

v2

v3

IDE SSSP

• D[v1]=0.7, karena hanya terdapat 1 path• D[v2]=1.11.2, ada path lain (s-v1-v2) tp tdk update• D[v3]=2.3 1,ada path lain(s-v1-v3)– Path d[v2] dan d[v3] mengalami update utk mendapatkan

shortest path• D[v4]=1.1• D[v5]=1.2

s

2.3

1.1

0.7v1

v2

v3

v4

v5

0.4

0.50.5

0.3

• D[v1]=0.7, karena hanya terdapat 1 path• D[v2]=1.11.2, ada path lain (s-v1-v2) tp tdk update• D[v3]=2.3 1,ada path lain(s-v1-v3)– Path d[v2] dan d[v3] mengalami update utk mendapatkan

shortest path• D[v4]=1.1• D[v5]=1.2

v3

Algoritmaprocedure Dijkstra;{ Dijkstra menghitung cost shortest path dr vertex 1 ke

tiap vertex dr directed graph }begin1. S := {1};2. for i := 2 to n do3. D[i] := C[1, i]; { inisialkan D }4. for i := 1 to n-1 do begin5. Pilih vertex w dlm V-S sedemikian sehingga

D[w] adlh minimum;6. Tambahkan w ke S;7. for tiap vertex v dlm V-S do8. D[v] := min(D[v], D[w] + C[w, v])

endend; { Dijkstra }

procedure Dijkstra;{ Dijkstra menghitung cost shortest path dr vertex 1 ke

tiap vertex dr directed graph }begin1. S := {1};2. for i := 2 to n do3. D[i] := C[1, i]; { inisialkan D }4. for i := 1 to n-1 do begin5. Pilih vertex w dlm V-S sedemikian sehingga

D[w] adlh minimum;6. Tambahkan w ke S;7. for tiap vertex v dlm V-S do8. D[v] := min(D[v], D[w] + C[w, v])

endend; { Dijkstra }

SSSP Manual

• Misalkan source 1, maka

1 2 550

45

10

4

1 2 5

3

50

3515 20

36

10

10 20

15

30

SSSP Manual

• Cari Source Ke Akhir simpul, ternyata ada:– 1-2,1-3,1-4,1-5

• Cari jalur terpendek dari tiap-tiap simpul yangberhubungan dr source ke akhir– 1-2• 1-2 =50• 1-3-4-2 =45, terpendek• 1-5-4-2 =95

• Cari Source Ke Akhir simpul, ternyata ada:– 1-2,1-3,1-4,1-5

• Cari jalur terpendek dari tiap-tiap simpul yangberhubungan dr source ke akhir– 1-2• 1-2 =50• 1-3-4-2 =45, terpendek• 1-5-4-2 =95

SSSP Manual

– 1-3• 1-3 =10• 1-2-3 =65, terpendek• 1-2-5-4-2-3 =125• 1-5-4-2-3 =110

– 1-4• 1-3-4 =25, terpendek• 1-2-5-4 =90• 1-2-3-4 =80• 1-5-4 =75

– 1-3• 1-3 =10• 1-2-3 =65, terpendek• 1-2-5-4-2-3 =125• 1-5-4-2-3 =110

– 1-4• 1-3-4 =25, terpendek• 1-2-5-4 =90• 1-2-3-4 =80• 1-5-4 =75

SSSP Manual

– 1-5• 1-5 =45,terpendek• 1-2-5 =60• 1-3-4-2-5 =65• 1-3-4-5 =60

• Kumpulkan jalur terpendek dari masing-masing simpul yang berhubungan dr source keakhir

– 1-5• 1-5 =45,terpendek• 1-2-5 =60• 1-3-4-2-5 =65• 1-3-4-5 =60

• Kumpulkan jalur terpendek dari masing-masing simpul yang berhubungan dr source keakhir

SSSP Manual-Hasil AkhirJalur Jarak

1-3 10

1-3-4 25

1-3-4-2 45

1-5 45 45

4

1 2 5

3

2010

15

45

Problem

• Di ketahui G=(V,E), directed and weighted.• Hitung panjang (cost) shortest path dari node 1

ke setiap node dalam G.• source node 1 ke 3. Ada beberapa paths (1 -> 4 -

> 3, 1 -> 2 -> 3, dst.), tetapi shortest dari path tsbadalah 1 -> 4 -> 2 ->3 dg panjang 9.

• Tugas kita adalah bagaimana menemukan .

• Di ketahui G=(V,E), directed and weighted.• Hitung panjang (cost) shortest path dari node 1

ke setiap node dalam G.• source node 1 ke 3. Ada beberapa paths (1 -> 4 -

> 3, 1 -> 2 -> 3, dst.), tetapi shortest dari path tsbadalah 1 -> 4 -> 2 ->3 dg panjang 9.

• Tugas kita adalah bagaimana menemukan .

Algoritma Semi-Greedy

• Kompleksitas O(n*lg(lg(n))) hingga O(n2).• Ambil cost dari shortest path ke seluruh node

dan tandai dengan infinity (). Dan..• Tandai panjang (cost) shortest path pada

source dengan 0.

• Kompleksitas O(n*lg(lg(n))) hingga O(n2).• Ambil cost dari shortest path ke seluruh node

dan tandai dengan infinity (). Dan..• Tandai panjang (cost) shortest path pada

source dengan 0.

Algoritma (lanj.)

• Pilih node yg terdekat dg source dan blmoptimal dan yang menjanjikan adalah path kenode 2 dan 4.

• Update cost pada 2 dan 4– 20+10=10– 40+5=5 (node terpilih)

• Pilih node yg terdekat dg source dan blmoptimal dan yang menjanjikan adalah path kenode 2 dan 4.

• Update cost pada 2 dan 4– 20+10=10– 40+5=5 (node terpilih)

• Dari 4 kita akan update cost node 2, 3 dan 5,yaitu:• 2 5+2=7 (node terpilih)• 35+9=14• 55+2=7

Algoritma (lanj.)

• Dari 4 kita akan update cost node 2, 3 dan 5,yaitu:• 2 5+2=7 (node terpilih)• 35+9=14• 55+2=7

Algoritma (lanj.)

• Dari 2 kita akan update cost node 3 :• 2 5+2=7 (node terpilih)• 35+9=14• 55+2=7

• Dari 2 kita akan update cost node 3 :• 2 5+2=7 (node terpilih)• 35+9=14• 55+2=7

Algoritma (lanj.)

• Algoritma berhenti karena semua node sudahdi kunjungi dan terupdate optimal cost

• Panjang (cost) optimal =1-4-2-38

step DariA

1

2

3

SSSP Greedy

A

B

50F

C10

1020

40 10 20

20A

80A

90A

A

B 20A

30B

80A

90A

Cost selected

Current lowest cost

B C D E F G H

F 40F

70F

20A

90A

30B3

4

5

6

7

8

A

E

G

D

H50

30

90 20

20

80

40 1010

20 F 40F

70F

20A

90A

30B

C 60C

50C

20A

40F

30B

90A

D 70D

20A

40F

50C

30B

60C

H 70D

20A

40F

50C

30B

60C

G 70D

20A

40F

50C

30B

60C

E= artinya tidak ada path lagi,walau ada edgeKe B dan G tapi cost update tidak lebih baikDari yang sekarang

Total cost=

Algoritma Knapsack

• Ada beberapa versi dari masalah klasik ini. Salah satunya bisadiilustrasikan sebagai berikut. Diberikan n objek dan sebuahransel (knapsack). Masing-masing objek i mempunyai beratwi dan vi. Ransel tersebut bisa memuat objek maksimalseberat W. Masalah yang harus dipecahkan adalah bagaimanamengisi ransel dengan objek yang nilai maksimal tanpamelewati batas kapasitas dari ransel. Dalam versi ini,diasumsikan bahwa masing-masing objek dapat dibagimenjadi bagian yang lebih kecil, sehingga kita dapatmemutuskan untuk hanya membawa sebagian objek isebanyak x1. Dengan demikian, algoritma untuk masalah inidapat disusun sebagai berikut.

• Ada beberapa versi dari masalah klasik ini. Salah satunya bisadiilustrasikan sebagai berikut. Diberikan n objek dan sebuahransel (knapsack). Masing-masing objek i mempunyai beratwi dan vi. Ransel tersebut bisa memuat objek maksimalseberat W. Masalah yang harus dipecahkan adalah bagaimanamengisi ransel dengan objek yang nilai maksimal tanpamelewati batas kapasitas dari ransel. Dalam versi ini,diasumsikan bahwa masing-masing objek dapat dibagimenjadi bagian yang lebih kecil, sehingga kita dapatmemutuskan untuk hanya membawa sebagian objek isebanyak x1. Dengan demikian, algoritma untuk masalah inidapat disusun sebagai berikut.

Algoritma

• n adalah jumlah objek wi adalah variabel yangmenyatakan berat dari objek i, vi adalahvariabel yang menyatakan nilai dari objek i, xiadalah pecahan yang menyatakan beberapabagian dari objek i yang dimasukkan dalamransel. Variabel berat menyatakan jumlahberat objek yagn sudah dimasukkan dalamransel, sedangkan W adalah kapasitas dariransel.

• n adalah jumlah objek wi adalah variabel yangmenyatakan berat dari objek i, vi adalahvariabel yang menyatakan nilai dari objek i, xiadalah pecahan yang menyatakan beberapabagian dari objek i yang dimasukkan dalamransel. Variabel berat menyatakan jumlahberat objek yagn sudah dimasukkan dalamransel, sedangkan W adalah kapasitas dariransel.

Secara Matematis

• Fungsi Utama/Tujuan/Objektif– Fungsi yg mjd penyelesaian masalah dengan

mendapatkan solusi optimal, yaitu mendapatkannilai profit yg maksimal utk sejumlah obyek yangakan di muat dalam ransel yg sesuai kapasitasnya

• Fungsi Pembatas/Subyektif– Bertujuan memberikan batas maksimal setiap

obyek untuk di muatkan dalam ransel sesuaikapasitasnya

• Fungsi Utama/Tujuan/Objektif– Fungsi yg mjd penyelesaian masalah dengan

mendapatkan solusi optimal, yaitu mendapatkannilai profit yg maksimal utk sejumlah obyek yangakan di muat dalam ransel yg sesuai kapasitasnya

• Fungsi Pembatas/Subyektif– Bertujuan memberikan batas maksimal setiap

obyek untuk di muatkan dalam ransel sesuaikapasitasnya

rumus

i

n

ii XP1

Fungsi Tujuan

i

n

ii XP1

MXW i

n

i 1Fungsi Pembatas

0,0,10 iii WPX

Solusi Greedy

• Pilih obyek dengan nilai Pi maksimal• Pilih obyek dengan bobot Wi minimal• Pilih obyek dengan perbandingan Pi/Wi

terbesar

• Pilih obyek dengan nilai Pi maksimal• Pilih obyek dengan bobot Wi minimal• Pilih obyek dengan perbandingan Pi/Wi

terbesar

Algoritma Knapsack Greedyvoid GREEDY(int n,int c, int p[],int w[]){int cc,jj,j;cc=c; zg=0; jj=1;for(j=1;j<n;j++){if (w[j]>cc) x[j]=0; else {

x[j] = 1; cc=cc-w[j];zg=zg+p[j];

}if (p[j]>p[jj]) jj=j;

}if (p[jj]>zg){

zg=p[jj];for (j=1;j<n;j++) x[j]=0;

x[jj]=1;}}

void GREEDY(int n,int c, int p[],int w[]){int cc,jj,j;cc=c; zg=0; jj=1;for(j=1;j<n;j++){if (w[j]>cc) x[j]=0; else {

x[j] = 1; cc=cc-w[j];zg=zg+p[j];

}if (p[j]>p[jj]) jj=j;

}if (p[jj]>zg){

zg=p[jj];for (j=1;j<n;j++) x[j]=0;

x[jj]=1;}}

Psuedocode Algoritma– Inisiasi

• Untuk setiap i, set xi = 0• Set berat = 0

– Selama berat < W lakukan• Pilih i, yaitu objek yang paling potensial (lihat keterangan di

bawah) dari objek yang tersisa.• Jika berat + wi ≤ maka

xi = 1Berat = berat + wi

Jika tidak makaxi = (W – berat) / wi

berat = W

– Inisiasi• Untuk setiap i, set xi = 0• Set berat = 0

– Selama berat < W lakukan• Pilih i, yaitu objek yang paling potensial (lihat keterangan di

bawah) dari objek yang tersisa.• Jika berat + wi ≤ maka

xi = 1Berat = berat + wi

Jika tidak makaxi = (W – berat) / wi

berat = W

Contoh Soal

• Diketahui– n=3 dengan Wi(18,15,10) dan Pi(25,24,15) dan

M=20

• Ditanyakan– Tentukan berat tiap-tiap barang yang dpt di muat

dalam ransel dengan kapasitas M ?

• Diketahui– n=3 dengan Wi(18,15,10) dan Pi(25,24,15) dan

M=20

• Ditanyakan– Tentukan berat tiap-tiap barang yang dpt di muat

dalam ransel dengan kapasitas M ?

Secara Matematika

iii XP3

1

i

ii XP3

1

203

1 iiXW

0,0,10 iii WPXBatas atasBatas bawah

Step 1

• Tentukan solusi feasibel yaitu 2 X n dari batasbawah dan atas, lalu hitung sesuai kapasitasM<=20, untuk masing masing bobotnya

X1=0,X2=1,X3=?18X1+15X2+10X32018.0+15.1+10.X3 2010X3 20-15X3=1/2

X1=1,X2=0,X3=?18X1+15X2+10X32018.1+15.0+10.X3 2010X3 20-18X3=1/5

X1=1,X2=?,X3=018X1+15X2+10X32018.1+15X2+10.0 2015X2 20-18X2=2/15

X1=0,X2=1,X3=?18X1+15X2+10X32018.0+15.1+10.X3 2010X3 20-15X3=1/2

X1=1,X2=0,X3=?18X1+15X2+10X32018.1+15.0+10.X3 2010X3 20-18X3=1/5

X1=1,X2=?,X3=018X1+15X2+10X32018.1+15X2+10.0 2015X2 20-18X2=2/15

X1=0,X2=?,X3=118X1+15X2+10X32018.0+15. X2+10.1 2015X2 20-10X2=2/3

X1=?,X2=1,X3=018X1+15X2+10X32018X1+15.1+10.0 2018X1 20-15X1=5/18

X1=?,X2=0,X3=118X1+15X2+10X32018X1+15.0+10.1 2018X1 20-10X1=5/9

Step 2

• Buat tabel Untuk solusi fisibel

Solusi ke (X1,X2,X3) WiXi PiXiProfit

1 (0,1,1/2) 20 31.5 solusi fisibel1 (0,1,1/2) 20 31.5

2 (1,0,1/5) 20 28

3 (1,2/15,1) 20 28.2

4 (0,2/3,1) 20 31

5 (5/18,1,0) 20 30.9

6 (5/9,0,1) 20 28.8

solusi fisibel

Metode Greedy• Pilih barang dengan nilai profit Maksimal

– P1=25 x1=1, batas atas fungsi– P2=24 x2=2/15, hasil perhit. fungsi pembatas– P3=15 x3=0, batas bawah fungsi

• Pilih barang dengan berat Minimal– W1=18 x1=0, batas bawah fungsi– W2=15 x2=2/3, hasil perhit. fungsi pembatas– W3=10 x3=1, batas atas fungsi

• Hitung Wi/Pi– P1/W1=25/18 karena terkecil, maka x1=0, batas bawah fungsi– P2/W2=24/15 karena terbesar, maka x2=1, batas atas fungsi– P3/W3=15/10 di hit dengan F pembatas x3=1/2

• Pilih barang dengan nilai profit Maksimal– P1=25 x1=1, batas atas fungsi– P2=24 x2=2/15, hasil perhit. fungsi pembatas– P3=15 x3=0, batas bawah fungsi

• Pilih barang dengan berat Minimal– W1=18 x1=0, batas bawah fungsi– W2=15 x2=2/3, hasil perhit. fungsi pembatas– W3=10 x3=1, batas atas fungsi

• Hitung Wi/Pi– P1/W1=25/18 karena terkecil, maka x1=0, batas bawah fungsi– P2/W2=24/15 karena terbesar, maka x2=1, batas atas fungsi– P3/W3=15/10 di hit dengan F pembatas x3=1/2

0,0,10 iii WPXF pembatas

Metode Greedy

• Buat Tabel

Solusi ke (X1,X2,X3) WiXi PiXiProfit

Pi max (1,2/15,0) 20 28.2Pi max (1,2/15,0) 20 28.2

Wi min (1,2/3,1) 20 31

Pi/Wi (0,1,1/2) 20 31.5 solusi fisibel

Algortima Greedy

• Sorting Descending thd Pi/Wi– P1/W1=25/18 =1.39 urutan 3– P2/W2=24/15 =1.60 urutan 1– P3/W3=15/10 =1.50 urutan 2– Shg di peroleh urutan terhadap P dan W sbb:• W1,W2,W3 15,10,18• P1,P2,P3 24,15,25

• Sorting Descending thd Pi/Wi– P1/W1=25/18 =1.39 urutan 3– P2/W2=24/15 =1.60 urutan 1– P3/W3=15/10 =1.50 urutan 2– Shg di peroleh urutan terhadap P dan W sbb:• W1,W2,W3 15,10,18• P1,P2,P3 24,15,25

Running Algorithm

• Di Inputkan ke algo Knapsak GreedyX(1:n)0Isi20Mulai iterasii=1

W(i)>isi ? 15>20, tidak, makax(1)1, brg dpt dimuat seluruhnya dari W(1)=15isi=20-15, kapasitas ransel berkuran mjd 5

i=2W(2)>isi ? 5>10, ya, makax(2)5/10=1/2, brg dpt dimuat sebanyak ½ bagian saja dari W(2)=10isi=5-5, kapasitas ransel habis

i=3, X(3)=0, isi=0, selesai, karena isi=0

• Menghitung Profit(P1+P2+P3)=(24*1+15*1/2+18*0)=31.5

• Di Inputkan ke algo Knapsak GreedyX(1:n)0Isi20Mulai iterasii=1

W(i)>isi ? 15>20, tidak, makax(1)1, brg dpt dimuat seluruhnya dari W(1)=15isi=20-15, kapasitas ransel berkuran mjd 5

i=2W(2)>isi ? 5>10, ya, makax(2)5/10=1/2, brg dpt dimuat sebanyak ½ bagian saja dari W(2)=10isi=5-5, kapasitas ransel habis

i=3, X(3)=0, isi=0, selesai, karena isi=0

• Menghitung Profit(P1+P2+P3)=(24*1+15*1/2+18*0)=31.5