Memahami Prinsip Kerja Algoritma Dijkstra
Dijkstra’s algorithm, conceived by Dutch computer scientist Edsger Dijkstra in 1956 and published in 1959, is a graph search algorithm that solves the single-source shortest path problem for a graph with nonnegative edge path costs, producing a shortest path tree. This algorithm is often used in routing and as a subroutine in other graph algorithms. For a given source vertex (node) in the graph, the algorithm finds the path with lowest cost (i.e. the shortest path) between that vertex and every other vertex. It can also be used for finding costs of shortest paths from a single vertex to a single destination vertex by stopping the algorithm once the shortest path to the destination vertex has been determined. For example, if the vertices of the graph represent cities and edge path costs represent driving distances between pairs of cities connected by a direct road, Dijkstra’s algorithm can be used to find the shortest route between one city and all other cities. As a result, the shortest path first is widely used in network routing protocols, most notably IS-IS and OSPF (Open Shortest Path First).
Dijkstra’s original algorithm does not use a min-priority queue and runs in O(|V|2). The idea of this algorithm is also given in (Leyzorek et al. 1957). The common implementation based on a min-priority queue implemented by a Fibonacci heap and running in O(|E| + |V| log |V|) is due to (Fredman & Tarjan 1984). This is asymptotically the fastest known single-source shortest-path algorithm for arbitrary directed graphs with unbounded nonnegative weights. (Wikipedia)
While people such as network designers and analysts need to have a thorough understanding of Dijkstra’s algorithm, a simple close examination is sufficient for the rest of us. Rather than listing the algorithm in stepwise form, let’s simply walk through a sample solution. The goal of our example will be to find, in Figure 9-10, the least-cost routes from Node A to each of the other nodes.
To begin, you will first need to create a table, like Table 10-2(a) (below), with a column for each node in the network except the starting node, Node A. The table also needs to include a column called “Visited,” in which you will list each node that has been visited. More precisely, when you list a node in this column, it indicates that you have gone to that node and examined all of the node’s immediate neighbors. In addition, the table should include a final row called “Next” to denote the next node (but only the next node) that the packet should traverse after it leaves Node A. For example, if the Next value under column Node G is B, then a packet that is leaving Node A and is destined for Node G should next be transmitted to Node B. As you work through this example, you should keep in mind that the way this algorithm works is that this table, once it’s complete (see Table 10-2(h) at the end of this section), shows only the very next hop that should be made from Node A to each of the other nodes. With respect to the example, this means that once you got to Node B (on your way to Node G), you would have to consult a different table—namely, the Dijkstra table for Node B—for the next hop.
Table 10-2(a) Initial table for Dijkstra’s algorithm
After you’ve created the table, select the starting node, Node A, visit it, and add the starting node to the Visited list, as shown in Table 10-2(b). After that, locate each immediate neighbor (a node only one link or hop away) of Node A that is not yet in the Visited list. Calculate the cost to travel from Node A to each of these neighbors, and enter these values into the table. For example, Node B is one hop away from Node A, it has not yet been visited, and it costs 2 units to travel from A to B. In this case, you should enter 2 in the column for Node B in Table 10-2(b) to indicate the cost of the path from Node A to Node B, and enter B in the Next row to note that to get to B, you go directly to B on the next hop. You can also go from A to C in one hop with a cost of 4 and a Next value of C, and from A to D with a cost of 5 and a Next value of D. These values are also recorded in Table 10-2(b). Note that we have not yet “visited” B, C, or D. We have only visited A, and we are simply examining the costs of the links that run between A and B, A and C, and A and D.
Next B C D
Table 10-2(b) Table for Dijkstra’s algorithm after visiting Node A
No more nodes are immediate neighbors of A, and all of Node A’s immediate neighbor links have been examined, so you need to select the next node to visit. According to the algorithm, the next node to visit must be the one that has the least cost in our table thus far. Therefore, you must choose Node B. By specifying that you select the next node with the least cost, the algorithm will find the least cost in all situations. Locate the immediate neighbors of Node B that have not yet been visited (so far only A has been visited), and determine the cost of traveling from Node A to each immediate neighbor of B via Node B. Note that Node A has been visited, so you should exclude it from being considered at this stage (no sense in going backwards). The immediate neighbors of Node B that have not yet been visited are D, E, and G. The cost of going from Node A to Node D via node B is 4 (the link from A to B costs 2, and the link from B to D costs 2). Since this cost is less than the cost of going directly from A to D (which, as can be seen in Table 10-2(b), is 5), replace the value 5 with the new value 4, to update the table. This update is highlighted in Table 10-2(c). You should also replace the D in the Next row under column D with a B, since the new least-cost path from Node A to Node D now begins with the packet going to Node B first after leaving Node A.
Next B C B
Table 10-2(c) Table for Dijkstra’s algorithm after visiting Nodes A and B
The cost of going from A to E via B is 6 (2 + 4), and the cost of going from A to G via B is 9 (2 + 7). Enter the values 6 and 9 in the E and G columns, respectively, as shown in Table 10-2(d). B is also the Next value for both E and G.
Next B C B B B
Table 10-2(d) Table for Dijkstra’s algorithm after visiting Nodes A and B, continued
Let’s visit Node C next since, as you can see in Table 10-2(d), it has the next smallest cost. The immediate neighbors of C that have not yet been visited are F and G. The cost of going from A to F via C is 7 (4 + 3). Enter the value 7 in the F column and the value C in the Next row, as shown in Table 10-2(e). The cost of traveling from Node A to G via C is 9 (4 + 5). Since this new value, 9, is not less than the current value (also 9) in Table 10-2(d), there is no need to update the table in this case.
Next B C B B C B
Table 10-2(e) Table for Dijkstra’s algorithm after visiting Nodes A, B, and C
Let’s visit Node D next, since it has the next smallest cost. The immediate neighbors of D that have not yet been visited are E, F, and G. The cost of going from A to E via D (via B) is 5 (4 + 1). Since this value is less than the current cost from A to E (less than 6), update the table by entering 5 in the E column (see Table 10-2(f) for reference). We still get to E by first going to B after leaving A, so the value B in the Next row does not change. The cost of going from A to F via D is 10 (5 + 5). The cost of going from A to G via D is also 10. Because the values already entered in the F and G columns are less than 10 (in other words, the table already reflects the least-cost path for those nodes), you do not update the table.
Next B C B B C B
Table 10-2(f) Table for Dijkstra’s algorithm after visiting Nodes A, B, C, and D
The next node to visit is E. The immediate neighbor of E that has not yet been visited is G. The cost of traveling from Node A to Node G via Node E (via D via B) is 7 (2 + 2 + 1 + 2). The cost of this path, 7, is smaller than the value already entered in Column G, so you should replace the current value in the table with this new, smaller value, as is shown in Table 10-2(g).
Next B C B B C B
Table 10-2(g) Table for Dijkstra’s algorithm after visiting Nodes A, B, C, D, and E
The next node to visit is F. The only immediate neighbor of F that has not yet been visited is G. The cost of traveling from Node A to Node G via F (via C) is 8. This cost is not less than the current value for F, so do not update the table.
The final node to visit is G. There are, however, no immediate neighbors of G that have not already been visited, so we are finished.
Table 10-2(h) shows the final results. From this table, you can now easily look up the least-cost path from Node A to any other node. If a data packet originates from Node A and is destined for Node x, the software in the router will simply consult Column x of the table to determine where the data packet should go Next. To find the least-cost route starting from another node, you would need to apply Dijkstra’s algorithm again. For example, if you wished to find the least-cost path from, say, Node C to any other node, you would generate a new table by repeating the least-cost algorithm with Node C as the starting position.
Next B C B B C B
Table 10-2(h) The results of Dijkstra’s algorithm applied to a seven-node sub-network starting from Node A
(Supplemental Material to Accompany Data Communications and Computer Networks by Curt M. White)
Contoh Soal ke 2
Pada soal kedua kita diminta untuk mencari jalur paling efektif (cost/Path) dari Router A menuju ke Router F, Total router yang berada pada jaringan adalah sebanyak 6 router, nilai cost antar node seperti tampak pada gambar diatas, kita diminta menggunakan algoritma dijkstra untuk menyelesaikan kasus ini.
Hasil Visit ke Dua D ke B adalah 3 melalui B, namun karena nilai visit sebelumnya lebih kecil yaitu 2 maka yang digunakan adalah nilai sebelumnya
Selanjutnya cari nilai cost/path terkecil untuk dijadikan Node Visited (ada dua node yang bernilai 2 yaitu B dan E) maka yang dipilih adalah Node B karena path terpendek, berlaku juga untuk kunjungan kunjungan selanjutnya.
Sehingga hasil akhir dari path/cost paling efisien adalah sebagai berikut.