single source shortest path dijkstraeprints.dinus.ac.id/14265/1/slide_10b.pdf · algoritma...
Post on 29-Jul-2020
28 Views
Preview:
TRANSCRIPT
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
top related