• Dijkstra’s algorithm is a Link-state algorithm which computes the least-cost path from one node to all other nodes in the network.
• Dijkstra’s algorithm is iterative.
• The least-cost paths are known to k destination nodes after the iteration of the algorithm. These k paths will have the k smallest costs among the least-cost paths to all destination nodes.
The following terms are used in the algorithm:
D(v) = least cost of the path from the source to the destination for the node v.
p(v) = previous node along the current path with least cost from source to node v.
N’ = subset of nodes.
The following table represents the computation of shortest path from source x to all the nodes in the network is as follows:
Therefore, the following are shortest paths from x along with their costs: t: xvt = 7; u: xvu = 6; v: xv = 3; w: xw = 6; y: xy = 6; z: xz = 8
If you found this answer helpful, please upvote and share with other students in your network.