### Archive

Posts Tagged ‘Understanding Dijkstra’s Algorithm’

## 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.

Visited                                                           Node

–                                                    B      C      D     E      F      G

Next

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. Visited                                                           Node

B      C      D     E      F      G

A                                                   2      4      5      –       –       –

Next                                              B      C      D

Table 10-2(b)  Table for Dijkstra’s algorithm after visiting Node A