Dijkstra Algorithm – Part I

Start learning all about the Dijkstra algorithm for finding the shortest path. We briefly review the Kruskal algorithm, Prim algorithm, Johnson algorithm and Bellman algorithm as well. We’ll cover:

• What is the Dijkstra algorithm?
• How does the Dijkstra algorithm work?
• Pseudo code of Dijkstra algorithm
• Dijkstra algorithm table
• Dijkstra algorithm time complexity
• When to use the Dijkstra algorithm?
• Dijkstra algorithm vs Kruskal algorithm
• Dijkstra algorithm vs Prim algorithm
• Prim algorithm vs Kruskal algorithm
• How to find the shortest path using the Dijkstra algorithm?
• Why does the Dijkstra algorithm fail for negative weights?

What is the Dijkstra algorithm?

Edsger W. Dijkstra (1930-2002) was an eminent physicist who made great advances in the world of distributed and concurrent computing and other fields of mathematics.

The algorithm that bears his name finds the optimal solution to obtain the shortest path in a graph or net, although as we will see below there are improvements to the algorithm to enhance efficiency.

The Dijkstra algorithm belongs to the family of so-called greedy algorithms as it makes its decisions only considering the present moment without regard to how that decision may affect the future, i.e. it makes the best decision at a given moment without thinking about future consequences.

Greedy algorithms are typically used to solve optimization problems, such as selecting the shortest path or the best order to execute tasks on a computer.

In this context, the greedy algorithm selects the most promising segment or task at a given instant, without ever reconsidering whether that was the best decision later on. It is therefore a simple algorithm to implement since there is no need to control alternatives and no follow-up to undo previous decisions.

Greedy algorithms such as Dijkstra algorithm, Kruskal algorithm or Prim algorithm are characterized by the following general properties:

• Algorithms require solving a problem in an optimal way, where to construct the solution we have a set or list of candidates such as the edges of a graph, the tasks to plan, etc.
• As the algorithm progresses, two sets are accumulated, one containing the candidates that have been evaluated and selected and the other containing the candidates that have been evaluated but rejected.
• There is a function that checks whether a set of candidates form a solution to the problem, ignoring for the moment whether this is the optimal solution.
• There is a second function that tests whether a given set of candidates is feasible, i.e. whether it is possible to reach a solution with other candidates to achieve the final solution. Again, it is ignored for the moment whether the solution is optimal.
• There is a third function that selects the candidate that has neither been selected nor rejected and is the most promising candidate for the solution at a given point in time.
• Finally, there is a fourth function called objective that returns the solution we have found, although it is strictly speaking not part of the greedy algorithm.

To solve the problem, we look for the set of candidates (first) that constitutes a solution and (second) that optimizes the value of the objective function. The greedy algorithms proceed step by step.

Initially the set of selected candidates is empty and at each step the best candidate is considered to be added to this set by the selection function.

• If the new extended set of selected candidates is not feasible for a solution, optimal or not, the candidate is rejected.
• If the extended set of candidates still forms a possible solution, optimal or not, the new candidate is added to the set of selected candidates.

In this way, we continue to advance step by step until we find a solution that must necessarily be optimal.

As we have said, these characteristics are common to the greedy algorithms although, as we will see later, the Dijkstra, Kruskal and Prim greedy algorithms have distinctive characteristics.

How does the Dijkstra algorithm work?

The Dijkstra algorithm solves the minimum path problem for a given graph.

Given a directed graph G = {N, E} where N is the set of nodes of G and E is the set of directed edges, each edge has a non-negative length, we can talk about weight or cost too, and one of the nodes is taken as the origin-node.

The problem is to determine the length of the minimum path from the origin to each of the other nodes.

As we have seen in the general characteristics of greedy algorithms, the Dijkstra algorithm uses two sets of nodes S and C. The set S holds the set of selected nodes and the distance to the origin-node of each node at a given time. The set C contains all candidate nodes that have not been selected and whose distance is not yet known.

From this we derive an invariant property N = S U C.

That is, the set of nodes is equal to the union of the sets of selected nodes and unselected nodes.

In the first step of the algorithm the set S has only the node-origin and when the algorithm finishes it contains all the graph nodes with the cost of each edge.

We talk about a special node if all the nodes involved in the path from the origin to it are within the set of selected nodes S. Dijkstra algorithm maintains a matrix D that is updated at each step with the lengths or weights of the shortest special path of each node of the set S.

When a new ‘v’ node is tried to be added to S, the shortest special path to ‘v’ is also the shortest path to all other nodes (see demonstration in the reference book). When the algorithm is finished, all the nodes are in S and the matrix D contains all the special paths from the origin to any of the other nodes in the graph and thus the solution to our minimum path problem.

In the next installment, Mario Pisa will discuss how the Dijkstra algorithm works in pseudo-code before looking at the Python implementation.

Visit QuantInsti for additional insight on this topic: https://blog.quantinsti.com/dijkstra-algorithm/