Dijkstra's Algorithm
Notation:
Di = Length of shortest path from node 'i' to node 1. di,j = Length of path between nodes i and j .
Algorithm
Every node j is labeled with Dj, which is an estimate of cost of path from node j to node 1. At first, let the estimates be infinity, indicating that nothing is known about the paths. We now iterate on the length of paths, every time revising our estimate to lesser values, as we obtain them. In reality, we divide the nodes into 2 groups ; the 1st one, called set P contains the nodes whose shortest distances have been found, and the other Q containing all the left behind nodes. Firstly P contains only the node 1. At every step, we select the node that has least cost path to node 1. This node is transferred to set P. At the first step, this corresponds to shifting the node closest to 1 in P. Its least cost to node 1 is now known.
At the next step, select the next closest node from set Q and update the labels corresponding to every node using :
Dj = min [ Dj , Di + dj,i ]
At last, after N-1 iterations, the shortest paths for all nodes are recognized, and the algorithm terminates.
Principle
Let the closest node to one at some step be i. Then i is shifted to P. at this time, for each node j , the closest path to one either passes through i or it doesn't. In the first case Dj remains the same. In the 2nd case, the revised estimate of Dj is the sum Di + di,j . thus we take the minimum of these 2 cases and update Dj accordingly. As every of the nodes get transferred to set P, the estimates get closer to the lowest possible value. When a node is transferred, its shortest path length is known. So lastly all the nodes are in P and the Dj 's represent the minimum costs.
The algorithm is guaranteed to end in N-1 iterations and its complexity is O( N2 ).
Email based Computer Science assignment help - homework help at Expertsmind
Are you searching Computer Science expert for help with Dijkstra's Algorithm questions? Dijkstra's Algorithm topic is not easier to learn without external help? We at www.expertsmind.com offer finest service of Computer Science assignment help and computer science homework help. Live tutors are available for 24x7 hours helping students in their Dijkstra's Algorithm related problems. We provide step by step Dijkstra's Algorithm question's answers with 100% plagiarism free content. We prepare quality content and notes for Dijkstra's Algorithm topic under computer science theory and study material. These are avail for subscribed users and they can get advantages anytime.
Why Expertsmind for assignment help
- Higher degree holder and experienced experts network
- Punctuality and responsibility of work
- Quality solution with 100% plagiarism free answers
- Time on Delivery
- Privacy of information and details
- Excellence in solving computer science questions in excels and word format.
- Best tutoring assistance 24x7 hours