The goal of the Dijkstra’s Algorithm is to find the shortest path between the vertices of the given graph (Wikipedia, Dijkstra’s algorithm).
Things to consider in the Dijkstra’s Algorithm are there are tentative distance values that label every vertex. For the initial vertex, the person sets it up as zero. For the other nodes, the person sets it up as infinity. After, the person will create a “visited” list, this list entails all the vertices that will be used for the shortest path.
The decided initial vertex will always be at the start of the visited list. The person should consider the unvisited vertices neighboring the initial vertex and calculate the distance to the current vertex added to the distance from the current vertex from its neighbor. As the person is finished with considering the neighboring vertices of the current vertex, the person should mark the current vertex as visited and take it away from the unvisited list. The algorithm is finished when the destination verte has been marked as visited. The Dijkstra’s algorithm is typically used in Google Maps.This helps with the calculation of the time to reach a destination using different vehicles and using different routes. It is also typically used in telephone networks to get the optimal signal route with less interference. Another use of this Algorithm is for IP routing, where the goal is to transfer data from multiple routers using the shortest path, Dijkstra’s algorithm.
Here is an example of the application of the Dijkstra’s Algorithm. First, you should label the initial vertex as 0 and the rest of the vertices will be labeled infinity. The next thing that you will have to do is label the neighboring vertices with the distance to the current vertex + the distance of the current vertex from it’s neighbor. In this case, the infinity signs of B,C,E will be changed to 4,3,7 respectively. You will choose C as the succeeding visited vertex because it has the lowest distance. The next thing you should do is, change the label of the vertices neighboring our current vertex of C. For B, we will get a value of 9 (6+3). This is bigger than its current value so, we’ll leave it like that.
Best services for writing your paper according to Trustpilot
For D, we will get 14 which is lower than infinity so we will change the infinity into 14 (3+11). For E, the value is 11 so, we also leave it be. So, the next lowest distance vertex is 4. C and A have already been visited so, we only recalculate D. You will get 9 from 4+5, which is higher than E’s 7. Therefore, the next visited vertex is E. The next thing to do is to calculate G’s weighted distance, which is lower than infinity.
Therefore, it changes to 12 (7+5). There are 2 possible ways but D has the lower distance number so we choose D as the next visited vertex. Then, you calculate the distance for G and F. However, G (19) has a higher distance than 12. So, we don’t do anything with it. We change F’s infinity with 11 because it’s lower than infinity. Now, we add F to the visited vertices list because it has the lower distance. We’re done!The shortest path from A to F is A-B-D-F.
