Word Count : 1208

---

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 2. We finalize B. Step 2 proceeds with B. From B, suppose we have an edge to D with weight 7 and to C _________ _____ ___ ___ ______ ________ _______ _________.
__________ ____ ____ ______ ___ ________.
_________ ___ _________ ______ _______ ______ __________ ____.
______ ________ _________ ___ ___ ______ ________ ___ _____.
________ _________ _____ ________ __________ ___ __________ _____ ____ ______ ___.
____ ______ ___ ___ ___ ________.
______ ___ _____ ________ ______ __________ _____ _______ _________ _______ __________ ______.
_____ ___ __________ ________ __________.
________ ____ ____ __________ ___ _________ __________ __________ ________.
______ ______ ________ ________ _____ _____ _________ _________ _____ __________ _______ _______.
___ ________ ___ _____ ______.
____ ___ ________ ___ ____ _______.
__________ ___ __________ _________ _________.
______ ____ _________ ______ _________ ________ ________ _________ _______ ________ __________ ______.
_____ ________ __________ ________ ___ _______ ______.
__________ ___ _____ _________ ________ _____.
______ _______ ______ ______ ______ ______ ____ _________.
____ ______ ______ __________ __________ ______.
_________ __________ ____ ________ _______ _____ _________ ________ _________ _______.
_____ ______ ______ _______ _______ ______ ______ ____ ____.
___ _________ ______ _________ _________ __________ ________ _____ ________.
_________ ____ _________ _____ _______.
_________ ___ ______ ____ _________ ____ _________ ___ ___ ______ ___.
________ _____ ______ ___ ____ ______ _____ _____.
_______ _________ ________ __________ _____ ________.
_________ __________ ___ __________ _____ ________ ______ _______ __________ _________ ___ ____.
_______ __________ _____ _________ __________ ___.
______ ______ ___ ______ __________ ____ _____.
___ ___ _____ ______ _________.
_______ _____ ____ ________ _________ ___ _____ _______ ____ ______ ________ ___.
______ _______ _________ __________ __________.
_______ ____ __________ ____ __________.
____ ___ _____ ______ ______.
_____ ______ ___ _________ _____ _______ _______ __________.
__________ _______ ___ ____ ____ ____ ______ __________ _________ __________ _________.
______ ___ ______ ___ ______ _____ ____ __________.
_____ ___ __________ _______ _________ __________ ______ __________.
____ _____ __________ ______ ___.
____ ________ ___ ________ _________ _____ ___ ______ _________ _______ _________ _____.
______ ___ _________ ______ ________ ______ ______ ______ ________ __________.
_____ ______ ________ _____ ______ ______ ________ ___ ________ ________ ___ _____.
______ ___ ________ _________ _______ ________ _____ _____ ________ _______ ____ ______.
__________ ____ __________ _________ _______ ______ _______ _______.
_______ ________ _________ ___ ______ ____ ______ ________ _______ ________ ______.
_____ ________ __________ ________ _______ ______ _______ _________ _______ ________ ________.
_____ __________ _______ __________ _________ ______ ____ ________.
_____ _____ _______ _________ ____ _____.
________ _____ _______ ______ _______ _______ ______ ___ _______ ___.
_________ _____ ____ _________ _____ _____ _________ __________ ________ ___ _____ _____.
______ _______ ________ __________ ___ __________.
_____ ____ __________ ______ ________ _________.
_______ ____ __________ ___ __________ __________ ____ ____.
_______ ____ ____ ________ __________ _________ _____ __________ ___ _______ ______.
_____ ___ __________ _________ ___ _________.
____ ______ __________ ______ ___ _________ ___ ___.
______ _________ _______ ________ ___ _______ ____ ___ ____ ___.
________ _________ _____ ____ _____ ______ ________ ____ _________ ________ ______.
_______ ___ _________ __________ _________ _________ ___.
________ ______ __________ ______ _____ _________ ______ _________ ______ _____.
____ _________ _____ ___ _______ ____ __________.
_______ _________ _________ ________ ___ _________ _________.
_______ ____ ________ ______ _____ ____ _________ ____ ________ __________.
__________ _________ ______ ______ _________ ______ ____ ___ _______ ____.
_________ ___ __________ __________ ____ ____.
_________ _______ _____ __________ __________ __________ _________ ________ _____ __________ ____ ______.
__________ ________ ____ ______ _____ ________ ______ ________.
___ ______ ________ ______ __________ ___ __________ ________.
____ ___ ____ _________ ____ ____ ___ ____ ___.
__________ ___ _______ ____ ___ _____ ____ _____ _________.
____ _______ ________ ______ _________ ________ __________.
__________ ________ ______ ______ ____ _________ _______ ________ ____.
_______ __________ _______ __________ ________ _______ ______.
_____ _____ _________ ______ _____ _____ _______ _________ ___ ______.
___ ______ ________ ____ ___ _____ _______.
___ ___ __________ _________ ____.
__________ ____ _____ ________ ______ _________ __________ ___ ______ ______.
_____ ________ __________ __________ ________ _____ _______ _________ _________ ___.
______ ____ _______ _________ ______ ____ _________ _____ ____ ________ ________.
_________ _________ _______ _____ ______ _______ _____ _______ ______ ____ ________ ____.
_______ _______ __________ ______ ______ ___ ___ ___ ____ ____ ___ __________.
______ ______ _____ ___ _________ ___ ________ ________ ____ ____.
______ _________ _______ __________ ________ ____ ____ ____ _____.
___ ____ ________ ___ __________ _______ _________ _______ __________ ____.
____ __________ ______ ________ _______ ______ _________ _________ __________ ________ ____ ____.
_____ ________ __________ _________ _________ ______ ________ ___ _________ ______ ______.
__________ ________ _______ ___ ________ __________ _________ ____ ______ __________ _______.
______ _____ __________ ____ ______ ________ _______ _________ ______ ___.
______ ______ _______ ________ __________ ______ _____.
__________ ____ ___ ___ __________ ________ _________ ________ _________ _______.
______ _______ _______ _________ ______ ________ _________ ______ _____ _____.
______ __________ ________ _____ __________ ________.
________ _________ ___ ______ ____ _________.
____ _____ ____ ___ _________ ____ __________.
_________ ____ ______ ___ ______ _____.
_________ _____ _________ __________ __________ __________ __________ ____ ___ ________ ___.
___ _________ _______ ___ _________ ___ __________ ______ __________ _________ ___ ________.
____ _____ _______ ______ ___ ______ ________ _____.
__________ _____ _____ _______ _________ _____ ___ _____ _____ ______ __________.
_________ ___ __________ ____ __________ ____ _______ _________ _____ _______ ________.
___ ____ _______ ________ _______ _____ _________ _____ ____ ______.
________ _______ _______ _________ _______ ________.
_____ _____ _____ ______ __________ ___ ____ ______ ___.
_________ ____ __________ ________ ______ _______ ____ _____.
______ ________ ____ ______ _________ _____ ________ _____ ___ _________ __________ _______.
_________ _____ _____ _______ ______ __________.
Get Full Answer on WhatsApp