Question
Apply Dijkstra’s algorithm to find the shortest path from the vertex ‘S’ to all other vertices for the following graph:
Answer :
Word Count : 1208
______ ___ _____ _____ _____ _______ _______ _____ _____ __________.
______ ______ ____ ______ __________ ____ __________ ______ _______ ____ ________.
________ ______ ___ ___ _______ ___ _____ __________ ______ _________.
__________ ____ _____ ____ __________ _______ ____ _______ ________.
________ _________ ________ _________ ________ _____ __________.
___ __________ __________ ____ ________ _____ _____ ________ ________ ____.
____ ___ ______ _______ ______ ______.
____ _____ ________ __________ _____ ________ _________ ___.
_______ _____ ______ _____ _____ _________ ________ _________.
___ ________ ________ ______ _________.
___ _______ ______ ______ ____ ____ __________ _______ _______ ______ _____.
__________ _________ ___ ________ ___ ____.
_______ _________ ________ __________ ________ __________ _____ _________ ___ ____.
__________ _______ ________ __________ _____ ____ ________.
________ ______ _______ _____ ______ _______ _________ ______ ___.
________ _________ _________ _____ ________ ____ __________ ___ ____.
____ ___ ______ ________ ___ ___.
__________ ________ ____ ___ ______ _________ __________ ________ __________ __________ ________.
__________ ___ _____ __________ ________ ______ ______ ________.
_______ ____ _______ ____ _______ ____.
___ __________ ________ ________ ___ __________.
______ ________ __________ __________ ________ __________ ______ ___ ______ _____.
_______ ___ ____ _______ _____.
__________ _________ ___ __________ ___ _______ __________ _____ ___ ________ __________.
____ __________ __________ _____ ________ ______.
____ ____ _______ _______ _________ _____ _______ _______.
_______ ____ ________ __________ ________ _________ _______.
_______ _______ ____ __________ _____ ______.
______ ______ _________ _______ ______.
__________ __________ _____ ___ _________ _____.
______ __________ ____ ___ _____ _______ ______.
____ ________ __________ ________ ____ ____ _______ _________ ___.
_________ ________ ___ ______ __________ ______ __________ _______ ___ ________ _______.
____ ___ _____ _____ ___ _____ __________ ____ _____.
___ ___ ___ __________ ____ ________ ______.
_____ _________ ______ __________ ________ ____ ___.
_______ ____ ______ __________ ___ __________ ____ _________ _________ ______.
______ __________ _______ ___ ______ ________ ________ ______ ________ ____ ________ ______.
____ _______ _____ __________ ___ _______ _________ ________ ____ __________.
_______ ____ _________ ________ ____ ________.
________ ______ ________ ______ ___ ___ ____ __________ ___ ____ __________.
_________ ______ ____ _______ ________.
________ _______ ______ ______ __________.
_______ _______ ________ ___ _____ __________ _______ _______.
_____ _______ ____ ________ _____ __________ __________ ________ _____ ___ ______.
______ __________ ________ __________ ____ _____ _____.
_______ _______ ___ _____ _______ _______ ________ ________.
______ _____ _________ _____ _____ ________ _________ ______ ___ _________.
________ _______ _____ _________ __________ _______ ____ ______.
________ ____ ________ ___ ___ ____ _________ ________ __________.
____ ________ ____ ____ ______.
___ ________ ________ ___ _____ ____ ________ _________.
__________ _____ _______ ___ _______.
__________ ________ _____ _________ _______ _____ _______ ______ ______.
_______ ____ ____ _____ __________ ___ _________ _____ ___ ________ ________.
_____ ______ ___ ____ _______ ______ __________ ________ ______ _______ _______.
________ ____ _______ ________ _____.
_______ __________ _______ ________ ______ ___ _______ _______ ________ ____ _______.
_______ _______ _____ ______ ______.
__________ ____ ________ _____ ____ ____ _____ _________ _______ _____ _____ _________.
________ _______ _________ ________ ___ ________.
__________ ____ __________ ___ ______ ______ ___ ____ __________ ______ ______ ____.
________ _________ _________ _______ ____ ___.
_______ _____ ____ _______ _____ ________ ___ _______ ____ ____.
__________ _____ ___ _____ ___ ________ _____ ____ ______ ________ ___.
_____ _______ _____ _________ __________.
_________ __________ __________ _____ ____ ___ _________ ____ ___ ________ _________.
__________ ______ __________ ___ _________ _______ ______ ___ ___ __________ _____ ____.
_____ ____ ___ ________ _______ _________ ___ ______.
_____ _________ _____ ___ _______ ________.
____ ______ ______ ___ _________ __________ _______ ____ ___ ______ _______ _________.
___ _________ ______ _________ _________ _______ ____ ___.
__________ __________ ________ ______ _________ ___ _________ __________.
______ ____ ___ __________ _______ ___ ____ ___ ________ _________.
_______ ______ __________ _________ _________ _______.
_________ ___ _____ ______ ____ _______.
________ ____ __________ _____ _______ ___ ________ ____ ______.
___ _______ ____ ___ ______ _____ _________.
____ ______ ______ ____ ____ _________.
___ __________ _________ ___ ____.
_____ _________ _____ _____ __________ ___ _________ _______.
_________ ________ _____ _____ _______ _____.
______ _________ ____ _______ _______ ______.
______ ______ _____ _____ ___ ____ _______ __________ ______.
__________ ___ _____ _____ _____ ________ ____.
__________ _______ __________ ______ _______ _______.
________ _________ ___ __________ ______ _____ ______ ________ _____ _______.
_______ ___ _______ ____ ___.
______ ______ ________ _________ __________ _______ _____ ______ ____ ___.
______ _________ _______ ____ _____ _______ _____ _____ _________ ___ _______.
________ ____ __________ ___ ____ __________.
_______ _______ ____ _________ ______ _________ _______ ________ ____ ________ ___.
___ ________ ___ ________ _________ ________ _____ ___ __________ ____.
_____ ______ _______ _________ _________.
___ _________ ________ __________ ________ ______ __________ ______ _______ _____.
________ _______ ___ _________ ____.
_________ _____ ____ _________ ______ ____ _____ ___.
______ ____ _____ ________ ________ ___ ____ ________ ______.
________ ________ __________ _________ __________ _________.
____ ____ __________ ______ __________ ________ ___ _____.
____ ___ ____ ___ ____ _________ ________.
_________ _____ ______ __________ ________ __________ ___ ____ ______ _______ ____.
____ ______ _________ __________ __________.
_______ ________ ______ _______ ____ ________ ______ ______ _______ _________ ______ ____.
__________ ___ _______ _________ __________ ___ __________ __________ _______ __________ ________.
___ _______ _________ ______ ________ _________ _______ _____ _______ ____ ___ _________.
_________ _______ _______ ______ ________ _____ ___ ______.
_____ ______ ______ ________ _______ ____ _______.
_________ _________ __________ _____ _______ __________ ______ ____ ________.
____ ___ _____ __________ ______ ____.
_____ ___ ____ _______ _______.
__________ ________ ________ _____ _______ _______ __________ __________ _____ ______ _________ ______.
_____ _________ _________ ___ _________ _____ _______.
Skip in 10
Dijkstra’s algorithm is one of the most widely used shortest path algorithms in graph theory. It works on graphs with non-negative edge weights and finds the shortest distance from a given source vertex to all other vertices in the graph. The basic principle is greedy: at each step, the algorithm selects the vertex with the minimum tentative distance, finalizes it, and then relaxes the edges from this vertex to its neighbors. To apply Dijkstra’s algorithm, we maintain a set of visited vertices, an array of distances initialized to infinity except for the source vertex which is set to zero, and a priority mechanism to always pick the vertex with the current smallest distance. Let us apply this step by step on the given graph with source vertex ‘S’. We first initialize the distance of S as 0 and all other vertices as infinity. We also mark all vertices as unvisited. The priority queue initially contains only S with distance 0. The steps proceed as follows. At each iteration, the vertex with the minimum tentative distance is selected, marked as visited, and its adjacent edges are relaxed. Relaxation means that if the distance to the neighbor through the current vertex is shorter than its present recorded distance, then we update the distance with the new value. Step 1 begins with the source S. Distance(S) = 0, all others are infinity. We check neighbors of S. Suppose S has edges to A, B, and C with weights 4, 2, and 5 respectively. Then distance(A) = 4, distance(B) = 2, distance(C) = 5. These are updated. Now among unvisited vertices, the one with the smallest tentative distance is B with distance
_____ _________ ___ _____ ___ _________ ______ ______ ____.______ ___ _____ _____ _____ _______ _______ _____ _____ __________.
______ ______ ____ ______ __________ ____ __________ ______ _______ ____ ________.
________ ______ ___ ___ _______ ___ _____ __________ ______ _________.
__________ ____ _____ ____ __________ _______ ____ _______ ________.
________ _________ ________ _________ ________ _____ __________.
___ __________ __________ ____ ________ _____ _____ ________ ________ ____.
____ ___ ______ _______ ______ ______.
____ _____ ________ __________ _____ ________ _________ ___.
_______ _____ ______ _____ _____ _________ ________ _________.
___ ________ ________ ______ _________.
___ _______ ______ ______ ____ ____ __________ _______ _______ ______ _____.
__________ _________ ___ ________ ___ ____.
_______ _________ ________ __________ ________ __________ _____ _________ ___ ____.
__________ _______ ________ __________ _____ ____ ________.
________ ______ _______ _____ ______ _______ _________ ______ ___.
________ _________ _________ _____ ________ ____ __________ ___ ____.
____ ___ ______ ________ ___ ___.
__________ ________ ____ ___ ______ _________ __________ ________ __________ __________ ________.
__________ ___ _____ __________ ________ ______ ______ ________.
_______ ____ _______ ____ _______ ____.
___ __________ ________ ________ ___ __________.
______ ________ __________ __________ ________ __________ ______ ___ ______ _____.
_______ ___ ____ _______ _____.
__________ _________ ___ __________ ___ _______ __________ _____ ___ ________ __________.
____ __________ __________ _____ ________ ______.
____ ____ _______ _______ _________ _____ _______ _______.
_______ ____ ________ __________ ________ _________ _______.
_______ _______ ____ __________ _____ ______.
______ ______ _________ _______ ______.
__________ __________ _____ ___ _________ _____.
______ __________ ____ ___ _____ _______ ______.
____ ________ __________ ________ ____ ____ _______ _________ ___.
_________ ________ ___ ______ __________ ______ __________ _______ ___ ________ _______.
____ ___ _____ _____ ___ _____ __________ ____ _____.
___ ___ ___ __________ ____ ________ ______.
_____ _________ ______ __________ ________ ____ ___.
_______ ____ ______ __________ ___ __________ ____ _________ _________ ______.
______ __________ _______ ___ ______ ________ ________ ______ ________ ____ ________ ______.
____ _______ _____ __________ ___ _______ _________ ________ ____ __________.
_______ ____ _________ ________ ____ ________.
________ ______ ________ ______ ___ ___ ____ __________ ___ ____ __________.
_________ ______ ____ _______ ________.
________ _______ ______ ______ __________.
_______ _______ ________ ___ _____ __________ _______ _______.
_____ _______ ____ ________ _____ __________ __________ ________ _____ ___ ______.
______ __________ ________ __________ ____ _____ _____.
_______ _______ ___ _____ _______ _______ ________ ________.
______ _____ _________ _____ _____ ________ _________ ______ ___ _________.
________ _______ _____ _________ __________ _______ ____ ______.
________ ____ ________ ___ ___ ____ _________ ________ __________.
____ ________ ____ ____ ______.
___ ________ ________ ___ _____ ____ ________ _________.
__________ _____ _______ ___ _______.
__________ ________ _____ _________ _______ _____ _______ ______ ______.
_______ ____ ____ _____ __________ ___ _________ _____ ___ ________ ________.
_____ ______ ___ ____ _______ ______ __________ ________ ______ _______ _______.
________ ____ _______ ________ _____.
_______ __________ _______ ________ ______ ___ _______ _______ ________ ____ _______.
_______ _______ _____ ______ ______.
__________ ____ ________ _____ ____ ____ _____ _________ _______ _____ _____ _________.
________ _______ _________ ________ ___ ________.
__________ ____ __________ ___ ______ ______ ___ ____ __________ ______ ______ ____.
________ _________ _________ _______ ____ ___.
_______ _____ ____ _______ _____ ________ ___ _______ ____ ____.
__________ _____ ___ _____ ___ ________ _____ ____ ______ ________ ___.
_____ _______ _____ _________ __________.
_________ __________ __________ _____ ____ ___ _________ ____ ___ ________ _________.
__________ ______ __________ ___ _________ _______ ______ ___ ___ __________ _____ ____.
_____ ____ ___ ________ _______ _________ ___ ______.
_____ _________ _____ ___ _______ ________.
____ ______ ______ ___ _________ __________ _______ ____ ___ ______ _______ _________.
___ _________ ______ _________ _________ _______ ____ ___.
__________ __________ ________ ______ _________ ___ _________ __________.
______ ____ ___ __________ _______ ___ ____ ___ ________ _________.
_______ ______ __________ _________ _________ _______.
_________ ___ _____ ______ ____ _______.
________ ____ __________ _____ _______ ___ ________ ____ ______.
___ _______ ____ ___ ______ _____ _________.
____ ______ ______ ____ ____ _________.
___ __________ _________ ___ ____.
_____ _________ _____ _____ __________ ___ _________ _______.
_________ ________ _____ _____ _______ _____.
______ _________ ____ _______ _______ ______.
______ ______ _____ _____ ___ ____ _______ __________ ______.
__________ ___ _____ _____ _____ ________ ____.
__________ _______ __________ ______ _______ _______.
________ _________ ___ __________ ______ _____ ______ ________ _____ _______.
_______ ___ _______ ____ ___.
______ ______ ________ _________ __________ _______ _____ ______ ____ ___.
______ _________ _______ ____ _____ _______ _____ _____ _________ ___ _______.
________ ____ __________ ___ ____ __________.
_______ _______ ____ _________ ______ _________ _______ ________ ____ ________ ___.
___ ________ ___ ________ _________ ________ _____ ___ __________ ____.
_____ ______ _______ _________ _________.
___ _________ ________ __________ ________ ______ __________ ______ _______ _____.
________ _______ ___ _________ ____.
_________ _____ ____ _________ ______ ____ _____ ___.
______ ____ _____ ________ ________ ___ ____ ________ ______.
________ ________ __________ _________ __________ _________.
____ ____ __________ ______ __________ ________ ___ _____.
____ ___ ____ ___ ____ _________ ________.
_________ _____ ______ __________ ________ __________ ___ ____ ______ _______ ____.
____ ______ _________ __________ __________.
_______ ________ ______ _______ ____ ________ ______ ______ _______ _________ ______ ____.
__________ ___ _______ _________ __________ ___ __________ __________ _______ __________ ________.
___ _______ _________ ______ ________ _________ _______ _____ _______ ____ ___ _________.
_________ _______ _______ ______ ________ _____ ___ ______.
_____ ______ ______ ________ _______ ____ _______.
_________ _________ __________ _____ _______ __________ ______ ____ ________.
____ ___ _____ __________ ______ ____.
_____ ___ ____ _______ _______.
__________ ________ ________ _____ _______ _______ __________ __________ _____ ______ _________ ______.
_____ _________ _________ ___ _________ _____ _______.
IGNOU ACADEMY
Your IGNOU journey, made easier.
- Solved Assignments
- Study Notes
- Guess Papers
- Question Papers
Continue Reading — It's Free
Sign in with Google to unlock more of this answer.
✓ Free access
✓ Unlock up to 60% of the answer
✓ No payment required
✓ Unlock up to 60% of the answer
✓ No payment required
Quick Google sign-in. No separate registration form.