Dijkstra’s algorithm was conceived by Dutch computer scientist Edsger Dijkstra in 1956 and published in 1959. It is a graph search algorithm that solves the single-source shortest path problem for a graph with non-negative edge path costs, producing a shortest path tree. This algorithm is often used in routing and as a subroutine in other graph algorithms. In this post, we will use this algorithm to finding the shortest (or cheapest) path for a car travelling from one city to another city by using given roads. This algorithm can also be called a Satellite Navigation System that can show drivers which way they should better go. You can download the source code of this software at the bottom of this page.
Let the node at which we are starting be called the initial node. Let the distance of node Y be the distance from the initial node to Y. Dijkstra’s algorithm will assign some initial distance values and will try to improve them step by step.
- Assign to every node a tentative distance value: set it to zero for our initial node and to infinity for all other nodes.
- Mark all nodes unvisited. Set the initial node as current. Create a set of the unvisited nodes called the unvisited set consisting of all the nodes except the initial node.
- For the current node, consider all of its unvisited neighbors and calculate their tentative distances. For example, if the current node A is marked with a tentative distance of 6, and the edge connecting it with a neighbor B has length 2, then the distance to B (through A) will be 6+2=8. If this distance is less than the previously recorded tentative distance of B, then overwrite that distance. Even though a neighbor has been examined, it is not marked as “visited” at this time, and it remains in the unvisited set.
- When we are done considering all of the neighbors of the current node, mark the current node as visited and remove it from the unvisited set. A visited node will never be checked again; its distance recorded now is final and minimal.
- If the destination node has been marked visited (when planning a route between two specific nodes) or if the smallest tentative distance among the nodes in the unvisited set is infinity (when planning a complete traversal), then stop. The algorithm has finished.
- Set the unvisited node marked with the smallest tentative distance as the next “current node” and go back to step 3.
- Graph in Grid Form
- Total No of Vertices/Nodes: 50
- Nodes numbering from 0-49
- No of Rows = 5
- No of Columns = 10
- Nodes in Each Row = 10
- Nodes in Each Column = 5
- Weights are predefined between each vertices/nodes
- Initially Nodes color is black
- Initially lines color is white
- After running the algorithm visited nodes are represented by blue color and visited paths are represented by light green color.
As described above, this algorithm can be used to find the shortest (or cheapest) path for a car from one city to another by using given roads. So consider following graph for this example. Suppose each node represents a town and path between towns (nodes) represent the roads. Weight associated with path (roads) represents the cost of travelling through that road.
Now you can specify any of the town as source town and destination town. Your goal is to find the shortest path from source to destination. Suppose we enter,
Source Node = 0
Destination Node = 25
After giving source and destination nodes this algorithm will generate the shortest path and show it on console window.
This algorithm can also be called a “Satellite Navigation System” that shows to drivers which way they should better go.
Download Source code for graphical path finding system.
- This Pointer, Static Members and destructors in C++
- All pairs Shortest Path (APSP) Floyd Warshall C++ Source Code
- Applications of Dijkstra Algorithm
- Implementing Dijkstra Algorithm using Priority Queue (Heap) in C++
- Operator Overloading in C++
- Introduction to Classes and Objects in C++
- More on Destructors and Static Data Members in C++
- TIC TAC TOE Game in C++
- Applications of Circular Linked List in Data Structures
- Finding Longest Common Subsequence in two String using C++
- File Input-Output (I/O) in C++
- Exception Handling in C++
Popular Posts (last 30 days)
- Applications of Stack in … 1032 view(s)
- Circular Linked Lists 1000 view(s)
- Attendance Management Sys… 848 view(s)
- Simple Currency Converter… 642 view(s)
- Recursive Factorial funct… 548 view(s)
- Implementing Stack Data S… 496 view(s)
- Graph Implementation in C… 463 view(s)
- Finding Minimum, Maximum … 407 view(s)
- Finding Maximum Number in… 296 view(s)
- GRASP Design Patterns 276 view(s)
TagsAndroid C-Sharp C/C++ language Classes Data structures Design Pattern Eclipse Game Development Graphics Design Books HTML iPhone JAVA JAVA GUI MIPS Assembly Mobile Programming Books Object Oriented PDF PHP Programming Programming Books Programming Languages Books Python RaphaelJS REST Source Code Threads Tutorial Web Development Books