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, ___ _____ ______ ____ ____.
______ __________ _____ _________ ______ ______ _______ ______ ____ ________ ______.
____ ____ __________ ______ __________ _________.
_________ ________ ____ __________ ___ _________ _________ ___ ________ _______.
____ _____ _______ __________ ___.
_______ ______ ________ ___ _____ _________.
______ _______ _____ ___ ____.
____ _______ __________ _________ __________ ________.
___ __________ ___ ____ _______ _________ ____.
_______ ________ ____ ___ ____ _________.
_________ ____ ________ __________ _____ __________ ____.
______ ______ ________ ____ ____ ________ _______.
_______ ________ ___ __________ _______ _____ _________ ________ ____ ____ _________ ______.
_________ _______ ________ ______ ________ _____ _____ ___ _______.
______ _______ _______ _____ __________ _____ ______ _________ ______.
______ _________ ___ ______ __________.
_____ ______ ____ _________ ____ _________ ________ __________.
____ _____ ____ _______ ____ ___ _____ ________ __________ ______.
________ ______ __________ ______ _____.
_____ ______ ___ ________ _________ ____ ________ ___ ________.
____ _______ ____ ___ ______ ____.
___ ____ __________ ____ _________ _________ ___ ________ ________ _______ __________.
_______ __________ _________ _______ _____ __________ _________ ____ ____.
____ _____ ____ _________ ________ _________.
_____ ______ __________ _______ __________ _______ ________ __________ _______.
_______ ______ _______ _______ _________ _____ ____ _____.
__________ ____ _________ ___ ______ _____ _____ __________ _______ _________ ______.
________ ________ _______ ____ ________.
___ _______ _________ _____ ________ _______ ______.
_________ ________ _____ ________ ______ _________ __________ _____ ____ ___ _______ _________.
_____ ___ __________ ________ ___ ________.
_________ _______ ________ __________ ________ _______ _________ ________ ___ ____.
_____ _____ _______ _______ ___ _____ _________ _______ __________ ___.
____ _____ ____ _______ ________ _______ ______.
_______ _______ _______ _____ _____ ____ ______.
_________ _________ _____ ___ ______.
________ _______ __________ _____ _________ ________ ____ ____ __________ _______.
________ _____ _____ _________ _________ _____ ___.
__________ _______ __________ _____ ____.
______ _______ __________ __________ ___ __________ ________ ___.
_________ ________ ________ ________ _________ __________ _____ ____ ____ _____ _____ ___.
________ _______ ___ __________ ________ _______ __________ _______ _________ __________.
____ _______ ______ ______ ____ _______ ___ ___ ___ _________ ___.
__________ ___ _________ ___ ____ ___ _______ ______ ________ ___ _________ __________.
_____ ________ ________ ___ ________.
__________ ___ __________ ________ __________ __________ _______ ___.
_____ _________ _________ ____ __________ ________ ________.
_____ ______ ________ __________ ______ ___ __________ _________ __________ ________.
________ ______ ___ __________ ________ ________ ____ ______ _________.
_____ ___ ___ _____ _____ ____ _____ _________.
________ ____ ______ ___ ______ ___.
_____ __________ _______ _______ ______ _________ __________.
____ ________ _______ __________ _________ ______.
____ ________ ________ _______ ________.
___ _________ _____ ____ ____ _____ _________ ____ _________ ______.
_____ __________ ____ _________ __________ ________ _______ _____.
_____ _________ _______ _________ ________ ________ _______ ______.
___ _____ ________ ____ ________ ____ ____ _________ _________ _______ ___.
___ __________ _______ ____ _________.
________ ______ _________ _______ __________ ______ ____ ________ _________.
________ ________ _______ ___ ____ __________.
_________ ____ ______ ______ _______ ________ ___ __________ ___ ___.
_______ ______ _______ _________ _________ _____ __________ ________ _______ ________.
_____ ___ _______ __________ ________ _________ ________ _________ ____ ____ ______ __________.
______ ________ ____ ____ ___ ____ ______.
________ ________ _________ ________ _________ ____ _____.
______ _________ __________ __________ _____ ____ ________ ________ ____ _____ _____ _________.
__________ _____ _______ ___ ______.
________ _________ ____ ______ __________.
_________ _______ _________ __________ ________ _____ _____ _________.
___ ________ ______ ____ _______ ________ _______.
_________ ________ _______ ______ _____ ____ ______ ______ ______ ________ _____.
_______ _____ ___ ______ _____ _____ _____ _________ ____ ________ ______.
___ ________ ________ __________ ______ _______ ___ ________.
________ _________ _______ ________ ______ ____ ____ _____ ________ ________ ____ ___.
__________ _______ _________ _________ ____ __________ _____ _____.
___ _________ _________ ________ __________ ____.
_____ ____ __________ ___ _________ __________ ____ ___ ______.
_____ _________ ________ ____ _______.
____ ____ ____ ___ ___ ________ ________ _______ ____ ________ _______ ___.
_________ ________ _________ _______ _______ ________ _______ _____ ________.
_________ ___ ______ ________ ________ _____ ___ __________ _______.
____ ____ __________ ___ ____.
______ ____ _____ ______ _______ _________ _______ ______ _____ _______ _______ ___.
_____ __________ __________ ___ _________ __________ __________.
__________ ____ ______ _______ ________ __________ _________.
___ _________ _______ ____ ____ ____ _______ ______ ___.
_____ ___ ______ __________ _________ ___ _____ ___.
______ __________ ____ _________ ______ ________ __________ _______ ______ _____.
______ _______ _________ ______ __________ ____ __________ _____ ____ _________ ___.
________ _____ ________ __________ _______ ______.
________ __________ ____ _____ ___ _____ ______ ________ _______ ____ ______ ___.
___ _________ ____ ____ ________ _________ ______.
___ ____ __________ __________ ____ ____ __________ _____.
_________ _______ _________ _______ ____ __________ ___.
___ ______ ____ _______ __________ _______ ___ ___ ________ _________.
__________ ________ ______ _________ __________ _____ _______.
_____ ______ ________ _______ _________ __________ _______ _________.
_____ _________ _______ ________ _____ _____ ____ __________ ______ _________ _______ _____.
______ ________ _____ ____ _________ ___ _____ ______.
_______ _____ __________ _____ _____ ______ ______ ____ __________.
_________ ___ _________ _____ ______ __________.
__________ _________ __________ ______ _____ _______.
_______ _______ ______ _____ ____ ___ ________ _________ ___.
________ __________ _____ ____ ________ __________ _______ _____ _____ ______.
____ _______ ________ ____ ____ ________ ______.
________ ____ ___ ____ ______.
____ __________ __________ __________ _________ _______ ________ _________ ___ __________ _____.
________ ______ _______ _________ ______ __________.
__________ _______ _____ _____ ________.
_______ ______ ________ _____ ________.
_____ ___ _______ __________ ________ ___ __________.
_______ ______ __________ _____ _____ _________ _______ ________.
_______ ________ __________ ______ ______ ____ _____ __________ _________ ________.
_____ ________ ____ _____ _________ ____ ______ _________.
___ ______ _____ _____ ___ ______.
________ _______ ___ _________ ________ ___ ____ ________ ___ __________ _________.
____ ___ ____ _____ _____ __________ ______ _____ ____ ____ __________.
________ _______ ____ _________ ______ __________ ________ _____ ___.
________.
Get Full Answer on WhatsApp