Download - SHORTEST PATH ALGORITHM.pdf
-
8/10/2019 SHORTEST PATH ALGORITHM.pdf
1/78
SHORTEST PATH ALGORITHM
(Dijkstra, Bellman-Ford)
-
8/10/2019 SHORTEST PATH ALGORITHM.pdf
2/78
-
8/10/2019 SHORTEST PATH ALGORITHM.pdf
3/78
Masalah Shortest Path
3
Terdapat sebuah graph berbobot (weighted graph) dandua vertices u dan v, kita ingin menemukan sebuah pathdengan bobot minimum antara u dan v.
panjang path adalah penjumlahan dari bobot sisi-sisinya(edges).
Contoh : Shortest path antara jakarta surabayaAplikasi
Internet packet routing Flight reservations Driving directions
-
8/10/2019 SHORTEST PATH ALGORITHM.pdf
4/78
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
-
8/10/2019 SHORTEST PATH ALGORITHM.pdf
5/78
Shortest Path Properties
Jika G tidak memiliki bobot, maka shortest pathnya diperoleh dari panjang path
yang paling minimal (jumlah edge-nya paling sedikit).
Jika G merupakan graph dengan bobot tertentu
Bobot dari p adalah
pvu
vuwpw,
,
5
-
8/10/2019 SHORTEST PATH ALGORITHM.pdf
6/78
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
-
8/10/2019 SHORTEST PATH ALGORITHM.pdf
7/78
Syarat
7
Syarat yang harus dipenuhi oleh sebuah shortest path:
Shortest path tidak memiliki cycle.
Sebuah shortest path memiliki
1V edge.
-
8/10/2019 SHORTEST PATH ALGORITHM.pdf
8/78
Single Source Shortest Path
8
Contoh shortest path dari vertex 1 ke 5
-
8/10/2019 SHORTEST PATH ALGORITHM.pdf
9/78
algoritma single source shortest path
9
Ada 2 macam algoritma yang digunakan dalammemecahkan masalah single source shortest path, yaitu:
Algoritma Bellman Ford ialah algoritma yang digunakan
untuk memecahkan masalah single shortest path yang memilikiedge dengan bobot negatif.
Algoritma Djikstra ialah algoritma yang digunakan untukmemecahkan masalah single shortest path yang memiliki edgedengan bobot positif.
-
8/10/2019 SHORTEST PATH ALGORITHM.pdf
10/78
DIJKSTRA
10
EdsgerWybe Dijkstra lahir di Rotterdam 11 May 1930.ibunya seorang ahli metematika dan ayahnya seorangahli kimia .
th 1956 Dijkstra lulus dari Universitas Leiden dalambidang mathematika dan teori fisika
Th 1959 Dijkstra menerima PhD UniversitasAmsterdam untuk thesisnya yg berjudul
Communication with an Automatic Computer,
-
8/10/2019 SHORTEST PATH ALGORITHM.pdf
11/78
algoritma DIJKSTRA
11
Algoritma dijkstra adalah salah satu algoritma untukmemecahkan masalah single source shortest path
Pada algoritma dijkstra pemecahan masalahdiperuntukkan untuk sebuah Graph G=(V,E) yang
berbobot non negatif.
Diasumsikan w(i,j) 0 untuk masing-masing edge (i,j)
E
-
8/10/2019 SHORTEST PATH ALGORITHM.pdf
12/78
-
8/10/2019 SHORTEST PATH ALGORITHM.pdf
13/78
13
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
-
8/10/2019 SHORTEST PATH ALGORITHM.pdf
14/78
Metode algoritma DIJKSTRA menggunakan metode
relaksasi
14
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
-
8/10/2019 SHORTEST PATH ALGORITHM.pdf
15/78
Metode algoritma DIJKSTRA
15
Output algoritma dijkstra adalah spanning tree T, dimanapath dari vertex s (sumber) ke masing-masing vertex vadalah sebuah shortest path dari s ke v dalam sebuah graphG.
Label pada sebuah vertex adalah jarak dari s ke masing-masing vertex
-
8/10/2019 SHORTEST PATH ALGORITHM.pdf
16/78
Contoh 1
16
Tentukan shortest path dari A ke setiap v pada graph Gberikut:
A
DC
E
7
10
6
48
5
2
15
9
B
-
8/10/2019 SHORTEST PATH ALGORITHM.pdf
17/78
Contoh 1(cont)
17
Spanning tree T kosong1. Inisialisai 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
-
8/10/2019 SHORTEST PATH ALGORITHM.pdf
18/78
-
8/10/2019 SHORTEST PATH ALGORITHM.pdf
19/78
Contoh 1(cont)
19
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 Dditambahkan 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
-
8/10/2019 SHORTEST PATH ALGORITHM.pdf
20/78
20
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 Bditambahkan 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
-
8/10/2019 SHORTEST PATH ALGORITHM.pdf
21/78
Contoh 1(cont)
21
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 nilaiterkecil,sehingga E ditambahkan ke T
Beri label d(E) =13
6. Semua vertex sudah diberi label7. 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
-
8/10/2019 SHORTEST PATH ALGORITHM.pdf
22/78
soal
22
Tentukan shortest path dari A ke D graph berikut :
-
8/10/2019 SHORTEST PATH ALGORITHM.pdf
23/78
23
-
8/10/2019 SHORTEST PATH ALGORITHM.pdf
24/78
24
-
8/10/2019 SHORTEST PATH ALGORITHM.pdf
25/78
25
-
8/10/2019 SHORTEST PATH ALGORITHM.pdf
26/78
26
-
8/10/2019 SHORTEST PATH ALGORITHM.pdf
27/78
27
-
8/10/2019 SHORTEST PATH ALGORITHM.pdf
28/78
28
-
8/10/2019 SHORTEST PATH ALGORITHM.pdf
29/78
-
8/10/2019 SHORTEST PATH ALGORITHM.pdf
30/78
30
-
8/10/2019 SHORTEST PATH ALGORITHM.pdf
31/78
31
-
8/10/2019 SHORTEST PATH ALGORITHM.pdf
32/78
32
-
8/10/2019 SHORTEST PATH ALGORITHM.pdf
33/78
33
-
8/10/2019 SHORTEST PATH ALGORITHM.pdf
34/78
Aplikasi dijkstra
34
Dijkstra's algorithm determines the distances (costs) between agiven vertex and all other vertices in a graph.This may be usefulto determine alternatives in decision making.
For example, a telephone company may forgo the decision toinstall a new telephone cable in a rural area when presented withthe option of installing the same cable in a city, reaching twice thepeople at half the cost.
Routing Algorithms Link State Routing for internet
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.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 -
8/10/2019 SHORTEST PATH ALGORITHM.pdf
35/78
-
8/10/2019 SHORTEST PATH ALGORITHM.pdf
36/78
contoh
36
-
8/10/2019 SHORTEST PATH ALGORITHM.pdf
37/78
-
8/10/2019 SHORTEST PATH ALGORITHM.pdf
38/78
contoh
38
-
8/10/2019 SHORTEST PATH ALGORITHM.pdf
39/78
contoh
39
-
8/10/2019 SHORTEST PATH ALGORITHM.pdf
40/78
contoh
40
-
8/10/2019 SHORTEST PATH ALGORITHM.pdf
41/78
contoh
41
-
8/10/2019 SHORTEST PATH ALGORITHM.pdf
42/78
BELLMAN FORD
42
Algoritma ini merupakan pengembangan dari algoritma Djikstra,Algoritma Bellman Fordakan benar jika dan hanya jika graph tidak
terdapat cycle dengan bobot negatif yang dicapai dari sumber s.
No cycleDiasumsikan shortestpaths tidak mempunyaicycles.
shortest path maksimummempunyai |V|-1 edge
-
8/10/2019 SHORTEST PATH ALGORITHM.pdf
43/78
Ciri ciri Algoritma Bellman-Ford :
43
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.
-
8/10/2019 SHORTEST PATH ALGORITHM.pdf
44/78
Contoh algoritma bellman ford
44
BF(G,w,s) // G = Graph, w = weight, s=sourceDetermine 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
-
8/10/2019 SHORTEST PATH ALGORITHM.pdf
45/78
Algoritma :
45
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)foreach edge (u,v) E[G] ;untuk mencek apakah ada atau tidak cycle dgn bobot negatif
do ifd[v] > d[u] +w ((u,v)) ;jika hasil algoritma yang diinginkan belum didapat
then return FALSEreturn TRUE;
-
8/10/2019 SHORTEST PATH ALGORITHM.pdf
46/78
Teknik relaksasi
46
Untuk setiap vertexv V, d (v) adalahbobot upper boundsebuah shortest
path dari s ke v,
d(v) disebutestimasishortest-path
-
8/10/2019 SHORTEST PATH ALGORITHM.pdf
47/78
relaksasi
47
1. pada algorithm Dijkstra dan algoritma shortest-paths untukdirected acyclic graphs (DAG), setiap edge direlaksasi sekali.
2. pada algoritma Bellman-Ford, setiap edge direlaksasi beberapa kali.
T i l I lit
-
8/10/2019 SHORTEST PATH ALGORITHM.pdf
48/78
Triangle Inequality
48
Lemma 1Untuk stiap edge (u; v) E, mempunyai (s;v) (s;u)+w(u;v)
U b d P t
-
8/10/2019 SHORTEST PATH ALGORITHM.pdf
49/78
Upper-bound Property
49
Lemma 2 Kita selalu mempunyai d[v] (s;v) untuk seluruh vertices vV dan satu d[v]
achieves the value (s;v), yang tidak pernah berubah
Corollary 1
Jika tidak terdapat path dari s ke v, maka kita selalu mempunyai d[v] =(s;v) = .
C P t
-
8/10/2019 SHORTEST PATH ALGORITHM.pdf
50/78
Convergence Property
50
Lemma 3 If s u v is a shortest path in
G for some u; v V and if d[u] = (s;u) atany time prior to relaxing edge (u;v), then
d[v] = (s;v) at all times afterward.
P th l ti P t
-
8/10/2019 SHORTEST PATH ALGORITHM.pdf
51/78
Path-relaxation Property
51
-
8/10/2019 SHORTEST PATH ALGORITHM.pdf
52/78
pplications in routing
52
A distributed variant of Bellman-Ford algorithm is used in theRouting Information Protocol (RIP). The algorithm isdistributed because it involves a number of nodes (routers)within an Autonomous system, a collection of IP networkstypically owned by an ISP. It consists of the following steps:
Each node calculates the distances between itself and all othernodes within the AS and stores this information as a table.
Each node sends its table to all neighbouring nodes. When a node receives distance tables from its neighbours, it
calculates the shortest routes to all other nodes and updatesits own table to reflect any changes.
http://en.wikipedia.org/wiki/Routing_Information_Protocolhttp://en.wikipedia.org/wiki/Autonomous_system_(Internet)http://en.wikipedia.org/wiki/Autonomous_system_(Internet)http://en.wikipedia.org/wiki/Routing_Information_Protocol -
8/10/2019 SHORTEST PATH ALGORITHM.pdf
53/78
pplications in routing
53
The main disadvantages of Bellman-Ford algorithm in thissetting are
Does not scale well
Changes in network topology are not reflected quickly since
updates are spread node-by-node. Counting to infinity
http://en.wikipedia.org/wiki/Network_topologyhttp://en.wikipedia.org/wiki/Infinityhttp://en.wikipedia.org/wiki/Infinityhttp://en.wikipedia.org/wiki/Network_topology -
8/10/2019 SHORTEST PATH ALGORITHM.pdf
54/78
algoritma Bellman Ford
54
algoritma Bellman Ford menggunakan suatu label D[u] yang selalubekerja pada jarak d(v,u) dari v ke u.
Bellman Fordmerupakan suatu algoritma yang bekerja pada graphdengan bobot edge negative tetapi tidak memiliki negative cycle.
-
8/10/2019 SHORTEST PATH ALGORITHM.pdf
55/78
algoritma Bellman Ford
55
Ada dua hal yang harus menjadi catatan pada algoritmaBellman-Ford, yaitu :
Shortest path tidak akan terdiri lebih dari V-1 edge dari graph yang
bersangkutan, dengan asumsi tidak ada negative cycle.Jika terdapatlebih dari V-1 edge pada shortest path, maka ada node yang dilewatilebih dari satu kali.Hal tersebut akan mengakibatkan shortest pathtidak optimal.
Pada tiap iterasi, harus dipertimbangkan edge mana yang akandigunakan terlebih dahulu.
-
8/10/2019 SHORTEST PATH ALGORITHM.pdf
56/78
contoh
56
develop algorithm using the following working example
use a table to show changes inestimates of distances andpredecessors initialize table nopredecessors
-
8/10/2019 SHORTEST PATH ALGORITHM.pdf
57/78
contoh
57
Revise estimates of distances Ulangi sebanyak v-1 kali
Untuk masing-masing edge (u, v) dalam graph, set d(v) =
min[d(v), d(u) + w(u, v)]
Jika jarak direvisi, tentukan vertex predecessor baru edges dapat diambil dengan berbagai cara misalnya sesuai
dengan urutan abjad: (a, b), (a,c), (a, d), (b, a), (c, b), . . . , (s,
b)
-
8/10/2019 SHORTEST PATH ALGORITHM.pdf
58/78
contoh
58
show how we can use predecessor information to tracepaths from source
-
8/10/2019 SHORTEST PATH ALGORITHM.pdf
59/78
-
8/10/2019 SHORTEST PATH ALGORITHM.pdf
60/78
Check for negative loops
60
at end, for each edge (u, v) , check to see if d(v) d(u) >w(u, v)
if so, we have a problem try to convince them with anexample:
show diagram when d(u) = 3, d(v) = 6, w(u, v) = 2 in such a case, algorithm returns the value false
-
8/10/2019 SHORTEST PATH ALGORITHM.pdf
61/78
contoh
61
-
8/10/2019 SHORTEST PATH ALGORITHM.pdf
62/78
contoh
62
-
8/10/2019 SHORTEST PATH ALGORITHM.pdf
63/78
contoh
63
-
8/10/2019 SHORTEST PATH ALGORITHM.pdf
64/78
contoh
64
Iterasi ke 1
-
8/10/2019 SHORTEST PATH ALGORITHM.pdf
65/78
65
Iterasi ke 2
-
8/10/2019 SHORTEST PATH ALGORITHM.pdf
66/78
contoh
66
Iterasi ke 3
-
8/10/2019 SHORTEST PATH ALGORITHM.pdf
67/78
67
Iterasi ke 4
-
8/10/2019 SHORTEST PATH ALGORITHM.pdf
68/78
contoh
68
Iterasi ke 5
-
8/10/2019 SHORTEST PATH ALGORITHM.pdf
69/78
69
Iterasi ke 6
-
8/10/2019 SHORTEST PATH ALGORITHM.pdf
70/78
contoh
70
Iterasi ke 7
-
8/10/2019 SHORTEST PATH ALGORITHM.pdf
71/78
contoh
71
Iterasi ke 8
-
8/10/2019 SHORTEST PATH ALGORITHM.pdf
72/78
72
-
8/10/2019 SHORTEST PATH ALGORITHM.pdf
73/78
73
-
8/10/2019 SHORTEST PATH ALGORITHM.pdf
74/78
74
-
8/10/2019 SHORTEST PATH ALGORITHM.pdf
75/78
75
-
8/10/2019 SHORTEST PATH ALGORITHM.pdf
76/78
76
-
8/10/2019 SHORTEST PATH ALGORITHM.pdf
77/78
77
-
8/10/2019 SHORTEST PATH ALGORITHM.pdf
78/78