Today's lesson continues on detailed discussion on Dijkstra Algorithm. Dijkstra Algorithm is an excellent approach for finding the shortest paths from a source node to all other nodes in a network. It is generally more efficient than the Bellman-Ford algorithm, but it will cause each link cost to be positive, which is the case in communication network. The main idea, is to progressfully identify the closest nodes from the source node, in order of increasing past cost. The process is iterative. And in the first iteration, it finds the closest node from the source node from its neighbors. And to the second iteration, it finds the second closest node from the source node; which must be the neighbor of either source node or the closest node to the source node. And at the third iteration, the third closest node must be the neighbor of the source node or the first two closest nodes. And in the k_th iteration, you will now determine the k_th closest node from the source node. In the example network graph, the first step is to find a closest node to the destination node S, which might be one hop away. The second to closest node to s is one hop away from s or w. And the third closest the node to s is a one hop away from s, w or x. Dijkstra Algorithm can be implemented by a set of N permanently label nodes, which consists of these nodes; which shortest the paths have been determined. At each iteration, the next closest node is added to the set N, under the distance to the remaining nodes of either new node is evaluated. The pseudo code is given in this few graph. Let's illustrate the execution of Dijkstra's algorithm. The graph describes the distance of cost of links into connecting routers. And initially, in table set N only contains the source node one. And in the first iteration, not one compares its costs to directly attached nodes and finds that nodes three is a closest to one with a cost of two. Nodes three is added to the set N. The tree diagram is started up by linking node one to node three. And it is also found that because of adding nodes three to set N, the new minimum distance to node four, and the new minimum distance to node of six are updated. And iteration two, node of two and node of six, are tied for the second closest the node from node one. Suppose another tree is selected? And it is added two set of N. The tree diagram is updated by connecting node one to node two. The new minimal costs from node one, are now calculated for the pass, so the node two. It is a font that node five, has a cost of a seven, sort of node of two. At iteration three, node six is next added to a set N. The tree diagram is updated by connecting node three to node of six. A new shortiest-path to node five, so the node of six is found with a cost of five. At the iteration four, node four is found to be, fourth closest node from node one, it is added to set N. The tree diagram is updated again by connecting node three to node of four. No new shortest the path [inaudible] on node four. At iteration five, node five is added to the set M. Is connected to node one, by node three, and a six. And the tree diagram is updated accordingly. This completes the Dijkstra's algorithm, as we keep updating the tree diagram. Finally resulted in a shortest path three from node one to all other nodes, which can be used by the link state route. Indeed by applying the, the Dijkstra's algorithm, each of all the nodes can also have its own shortest-path tree. This concludes today's lesson.
