0:00

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.

Â