Dijkstra's Algorithm

Mobile robots have a wide range of applications. Path-planning is an important primitive for autonomous mobile robots that lets robots find the ‘shortest’, or the ‘otherwise optimal’ path between two points. ‘Otherwise optimal’ paths could be paths that minimize the amount of turning, the amount of braking or other constraints. Algorithms to find the shortest path are important not only in robotics, but also in network routing, video games and gene sequencing.

Path-planning requires a map of the environment and the robot to be aware of its location with respect to the map. We will assume for now that the robot is able to localize itself (determine its position), is equipped with a map, and capable of avoiding temporary obstacles on its way. The goals of this document are to:

• introduce suitable map representations, and
• explain Dijkstra’s Algorithm for basic path-planning.

You should check out this video on Dijkstra’s Algorithm

Map Representations

In order to plan a path, we somehow need to represent the environment in the computer. One of the ways to represent the path is by using a Weighted Graph, which is discussed as follows:

Weighted Graphs

A Graph is a non-linear data structure consisting of nodes and edges. The nodes are sometimes also referred to as vertices and the edges are lines or arcs that connect any two nodes in the graph.

Graphs are used to represent many real-life applications: They are used to represent networks. The networks may include paths in a city or a telephone network or a circuit network. Graphs are also used in social networks like LinkedIn, Facebook, etc. For example, in Facebook, each person is represented with a vertex (or node). Each node is a structure and contains information like user ID, name, gender and locale. A weighted graph is a graph in which each edge has a numerical value called weight. Given below is an example of a weighted graph:

The graph consists of five nodes and seven edges. Each edge has some weight. For example, the edge  has weight 7, the edge  has weight 1.

Weighted graphs are often used to model real objects and processes. For example, the graph above can be considered as a map, where the nodes are cities and the edges are roads. The weight of each edge is the distance between two cities.

The graph above is an undirected graph. But weighted graphs can also be directed. Given below is an example of a directed weighted graph:

Directed and undirected graphs are pretty self explanatory - edges can either by one - way or two - way.

Weighted directed graphs can also be used to model some real processes. For instance, node S in the graph above can be considered as a storage place, from where we need to transfer some resources to the destination point, say to the node D. The remaining nodes can be considered as intermediate places. Each edge shows a direction in which the resources can be transferred. The weight of an edge shows the cost of transferring the resources between the two corresponding nodes.

Note that for the graphs above all the weights are positive, but negative and zero weights are also allowed.

A weighted graph can be represented using an adjacency matrix. For a weighted graph with  nodes, an adjacency matrix is a  matrix , where  is the weight of an edge between nodes  and . If there is no edge between  and , the corresponding value is assigned to . The diagonal elements of the matrix are assigned to  (here we assume that there are no self- loops in the graph). For the directed graph above, an adjacency matrix is the following:

The first row and column of the matrix correspond to the nodes of the graph. The remaining cells correspond to the weights. For example,

 since there is an edge between the nodes A and C with the weight 4.  since there is no edge between C and A.

In a weighted graph, a path has a weight equal to the sum of the edge weights in the path. For example, consider a path  The path consists of three edges. The total weight of the path is the sum of the edges' weights: . One may note that there is another path from the node S to the node B: . The weight of this path is: .

The problem of finding the shortest path from a starting node to a target node in a weighted graph often arises. There are several algorithms that allow us to solve this shortest path problem. Dijkstra’s Algorithm is one such algorithm.

Dijkstra's Shortest Path Algorithm

Dijkstra’s algorithm, published in 1959 and named after its creator Dutch computer scientist Edsger Dijkstra, can be applied on a weighted graph. The graph can either be directed or undirected. One stipulation to using the algorithm is that the graph needs to have a nonnegative weight on every edge.

Dijkstra’s Algorithm in action on a non- directed graph. Courtesy: Wikipedia

Illustration of Dijkstra's algorithm finding a path from a start node (lower left, red) to a goal node (upper right, green) in a robot motion planning problem. Open nodes represent the "tentative" set (aka set of "unvisited" nodes). Filled nodes are visited ones, with color representing the distance: the greener, the closer. Nodes in all the different directions are explored uniformly, appearing more-or-less as a circular wavefront as Dijkstra's algorithm uses a heuristic identically equal to 0. Courtesy: Wikipedia

Let’s now try to figure out how this algorithm works. Suppose a student wants to go from home to school in the shortest possible way. She knows some roads are heavily congested and difficult to use. In Dijkstra's algorithm, this means the edge has a large weight— the shortest path tree found by the algorithm will try to avoid edges with larger weights. If the student looks up directions using a map service, it is likely they may use Dijkstra's algorithm, as well as others.

The shortest path, which could be found using Dijkstra's algorithm is:

.

Dijkstra’s algorithm finds the shortest path tree from a single source node, by building a set of nodes that have a minimum distance from the source.

The graph has the following:

• vertices, or nodes, denoted in the algorithm by  or , and
• weighted edges that connect two nodes:  denotes an edge, and  denotes its weight.

This is done by initializing three values:

• , an array of distances from the source node S to each node in the graph, initiated the following way: ; and for all other nodes , . This is done at the beginning because as the algorithm proceeds, the  from the source to each node  in the graph will be recalculated and finalized when the shortest distance to  is found.
• , a queue of all nodes in the graph which the algorithm has not visited. At the end of the algorithm's progress,  will be empty.
• , an empty set, to indicate which nodes the algorithm has visited. At the end of the algorithm's run,  will contain all the nodes of the graph.

The algorithm proceeds as follows:

1. While  is not empty, pop the node from  with the smallest . In the first run, source node S will be chosen because  was initialised to be 0. In the next run, the next node with the smallest  value is chosen.
2. Add node  to , to indicate that  has already been visited.
3. Update  values of adjacent nodes of the current node  as follows: for each new adjacent node ,

• if , there is a new minimal distance found for , so update  to the new minimal distance value;
• otherwise, no updates are made to .

4. Remove  from

The algorithm has visited all nodes in the graph and found the smallest distance to each node. dist now contains the lengths of the shortest paths for each vertex from the source node.

Note: The weight of an edge  is taken from the value associated with  on the graph.

Exercise: ‘dist’ is an array (a linear data structure, where one index is being used to extract values from it). Given that the starting vertex is s, and the destination vertex is d, how would you index ‘dist’ to get the length of the shortest path from s to d ? You must have also seen that we are extracting values from ‘weight’ by providing two indices - how many dimensions does ‘weight’ have ? And what is the ‘official’ name given to ‘weight’ ? (Hint: It’s in this article!)

(Advanced) Exercise: Can any of the variables returned by the above algorithm (Q, s, weight, dist) be used directly to compute the shortest path as a string ? If yes, explain how. If not, what modification can be made to return the shortest path as a string ?

Implementation:

Click here to see the pseudocode for Dijkstra's algorithm, mirroring Python syntax. It can be used in order to implement the algorithm in any language.

Let’s step through Dijkstra’s algorithm on the weighted graph given earlier in this resource:

1. Initialize distances according to the algorithm.

2. Pick the first node and calculate distances to adjacent nodes.

3. Pick the next node with minimal distance; repeat adjacent node distance calculations.

4. Final the result of the shortest-path tree.

Exercise: Run Dijkstra’s Algorithm on the following graph and determine the resulting shortest path tree. (As can be seen clearly, S is the start node and E is the destination). Tip: This example also proves why Dijkstra’s algorithm should visit every node.

For further learning:

Python Program for Dijkstra's shortest path algorithm | Greedy Algo-7

Dijkstra's Algorithm

3.6 Dijkstra Algorithm - Single Source Shortest Path - Greedy Method

Bibliography:

https://www.geeksforgeeks.org/graph-and-its-representations/

https://brilliant.org/wiki/dijkstras-short-path-finder/