A summarized analysis of Dijkstra’s Algorithm
Proposed in 1959 by the Dutch computer scientist Edsger W. Dijkstra, this is an iterative algorithm for finding the shortest paths between nodes in a graph.
The algorithm originally was used for finding the shortest path between two given nodes, but now commonly, it is being used for finding the shortest paths from the source to all other nodes in the graph where a single node is fixed as the source node.
This forms a shortest-path tree.
It differs from the least spanning tree in that the shortest distance between two vertices may not involve all of the graph’s vertices.
Edsger Dijkstra elaborated the motivation for his algorithm in an interview -
What’s the shortest way to travel from Rotterdam to Groningen?
It is the algorithm for the shortest path, which I designed in about 20 minutes.
One morning I was shopping in Amsterdam with my young fiancée, and tired, we sat down on the café terrace to drink a cup of coffee and I was just thinking about whether I could do this, and I then designed the algorithm for the shortest path. As I said, it was a 20-minute invention. In fact, it was published in 1959, three years later. The publication is still quite nice.
One of the reasons that it is so nice was that I designed it without pencil and paper.
Without pencil and paper, you are almost forced to avoid all avoidable complexities.
Eventually that algorithm became, to my great amazement, one of the cornerstones of my fame.
Dijkstra’s algorithm uses the idea of relaxation, in which an approximation of the accurate distance is gradually displaced by more appropriate values until the shortest distance is reached. The predicted distance to each node is always an overestimate of the true distance, and it is usually replaced with the distance of a freshly discovered path.
It uses a priority queue to pick the nearest node that hasn’t been visited yet and runs the relaxing process on all of its edges greedily.
Dijkstra’s Algorithm requires that all the weights in the graph be positive.
In Dijkstra’s algorithm, once a vertex is marked as “closed” (and out of the open set) — the algorithm finds the shortest path to it,
and will never have to develop this node again — it assumes the path developed to this path is the shortest.
But with negative weights — this might not be true.
Because this algorithm does not use negative weights, it is able to run faster than other algorithms where negative values of weight are admissible (such as Bellman-Ford Algorithm).
Working of the Algorithm –
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 initially start with infinite distances and will try to improve them step by step.
Mark all nodes unvisited. Create a set of all the unvisited nodes called the unvisited set.
Assign to every node a tentative distance value: set it to zero for our initial node and to infinity for all other nodes. The tentative distance of a node v is the length of the shortest path discovered so far between the node v and the starting node. Since initially no path is known to any other vertex than the source itself (which is a path of length zero), all other tentative distances are initially set to infinity. Set the initial node as current.
For the current node, consider all of its unvisited neighbors and calculate their tentative distances through the current node. Compare the newly calculated tentative distance to the current assigned value and assign the smaller one. For example, if the current node A is marked with a 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 B was previously marked with a distance greater than 8 then change it to 8. Otherwise, the current value will be kept.
When we are done considering all of the unvisited 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.
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; occurs when there is no connection between the initial node and remaining unvisited nodes), then stop. The algorithm has finished.
Otherwise, select the unvisited node that is marked with the smallest tentative distance, set it as the new current node, and go back to step 3.
When planning a route, it is actually not necessary to wait until the destination node is “visited” as above: the algorithm can stop once the destination node has the smallest tentative distance among all “unvisited” nodes (and thus could be selected as the next “current”).
This animation will better explain the algorithm -
PseudoCode –
1. For the general case –
COST = 0 // Used to index cost
PREVIOUS = 1 // Used to index previous node
FUNCTION dijkstras_shortest_path(graph, start_node)
// Initialise visited and unvisited lists
unvisited = {} // Declare unvisited list as empty dictionary
visited = {} // Declare visited list as empty dictionary
// Add every node to the unvisited list
FOREACH key IN graph
// Set distance to infinity and previous to Null value
unvisited[key] = [∞, NULL]
NEXT key
// Set the cost of the start node to 0
unvisited[start_node][COST] = 0
// Repeat the following steps until unvisited list is empty
finished = False
WHILE finished == False
IF LEN(unvisited) == 0 THEN
finished = True // No nodes left to evaluate
ELSE
// Get unvisited node with lowest cost as current node
current_node = get_minimum(unvisited)
// Examine neighbours
FOREACH neighbour IN graph[current_node]
// Only check unvisited neighbours
IF neighbour NOT IN visited THEN
// Calculate new cost
cost = unvisited[current_node][COST] + graph[current_node][neighbour]
// Check if new cost is less
IF cost < unvisited[neighbour][COST] THEN
unvisited[neighbour][COST] = cost // Update cost
unvisited[neighbour][PREVIOUS] = current_node // Update previous
ENDIF
ENDIF
NEXT neighbour
// Add current node to visited list
visited[current_node] = unvisited[current_node]
// Remove from unvisited list
DEL(unvisited[current_node])
ENDIF
ENDWHILE
RETURN visited
ENDFUNCTION
2. Finding the shortest path between two nodes-
FUNCTION display_shortest_paths(start, visited)
FOREACH key IN visited
IF key != start THEN // Don’t print path for start node
current = key
path = current
WHILE current != start
previous = visited[current][PREVIOUS] // Get value of previous node
path = previous + path // Add value to path
current = visited[current][PREVIOUS] // Backtrack
ENDWHILE
PRINT(“Path for: “ + key)
PRINT(path)
PRINT(“Cost: “ + visited[key][COST])
ENDIF
NEXT key
ENDFUNCTION
Advantages of the algorithm –
1. Nearly Linear complexity
2. It can be used to find the shortest path between a single node and all other nodes, as well as the shortest path between a single source node and a single destination node, by ending the process once the shortest distance is found for the destination node.
Disadvantages –
1. It wastes a lot of time in blind searching.
2. It cannot be used for negative edges.
3. As it approaches the acyclic graph, it is unable to find the exact shortest path.
4. It has to keep track of all the visited vertices.
Usage in the real world –
1. In map applications (e.g. — Google Maps) for measuring the shortest feasible distance and to check the distance between two locations, check locations pointing to the vertices of a graph, etc.
2. Social Media applications — The standard Dijkstra algorithm can be applied using the shortest path between users measured through handshakes or connections among them. When the graph is becoming bigger and bigger, the standard algorithm takes a few several seconds to count and alternate advanced algorithms are used.
3. Telephone networks — this is used to reduce the obstacles encountered during transmission in data transfer in the networking and telecommunications domains.
4. Finding the shortest path in robots/drones — To optimise the speed of movement in robots or drones, this algorithm is used.
5. File server designation — The idea is to use Dijkstra’s algorithm to minimize the shortest path between the networks resulting in the minimum number of hops.
6. I.P. routing — Dijkstra’s algorithm is widely used in the routing protocols required by the routers to update their forwarding table. The algorithm provides the shortest cost path from the source router to other routers in the network.
7. Flighting Agenda: For example, If a person needs software for making an agenda of flights for customers. The agent has access to a database with all airports and flights. Besides the flight number, origin airport, and destination, the flights have departure and arrival time. Specifically, the agent wants to determine the earliest arrival time for the destination given an origin airport and start time. There this algorithm comes into use.
8. The algorithm has also been used to calculate optimal long-distance footpaths in Ethiopia and contrast them with the situation on the ground.
9. For efficiently establishing tracks of electricity lines or oil pipelines
