Dijkstra algorithm for realizing the shortest path algorithm in Java

preface

Dijkstra algorithm is a well-known shortest path algorithm. It is a single starting point full path algorithm. The algorithm is known as the successful model of "greedy algorithm". Next, this article will try to introduce this great algorithm in the most popular language and give Java implementation code.

1、 Knowledge preparation:

1. Data structure of representation diagram

There are many data structures for storing graphs. In this algorithm, the author uses adjacency matrix.

The adjacency matrix of a graph is stored in two arrays. A one-dimensional array stores the vertex information in the graph, and a two-dimensional array (adjacency matrix) stores the edge or arc information in the graph.

Let graph G have n vertices, then the adjacency matrix is an n * n square matrix, which is defined as:

As can be seen from the above, the edge array of an undirected graph is a symmetric matrix. The so-called symmetric matrix is that the elements of the n-order matrix satisfy AIJ = Aji. That is, the main diagonal from the upper left corner to the lower right corner of the matrix is the axis, and the elements in the upper right corner and the corresponding elements in the lower left corner are all equal.

From this matrix, it is easy to know the information in the figure.

(1) It is easy to judge whether any two vertices have edges or not;

(2) You should know that the degree of a vertex is actually the sum of the elements of the vertex VI in row I or column I of the adjacency matrix;

(3) To find all adjacent points of vertex VI is to scan the elements in row I of the matrix, and arc [i] [J] is 1, which is the adjacent point;

The directed graph pays attention to in degree and out degree. The in degree of vertex VI is 1, which is exactly the sum of the numbers in column I. The exitance of vertex VI is 2, that is, the sum of the numbers in row I.

The definition of directed graph is similar, so it will not be repeated.

2. Single starting point full path

The so-called single starting point full path refers to the shortest path from one starting point to all nodes in a graph.

3. Basic knowledge of graph theory (readers need to find relevant materials by themselves)

4. Complementary relaxation condition

Let the scalars D1, D2, DN satisfied

DJ < = Di + AIJ, (I, J) belongs to a,

And P is the road starting from I1 and ending at IK, if

DJ = Di + AIJ, for all edges of P (I, J)

If yes, then p is the shortest path from I1 to IK. Among them, the complementary relaxation condition of the above two equations, which is called the shortest path problem, is satisfied.

2、 Algorithmic thought

1. Let g = (V, e) be a weighted undirected graph. If there are two adjacent nodes in G, I and J. AIJ (which is expressed as subscript, please note) is the weight from node i to node j, which can be understood as distance in this algorithm. Each node has a value di (node tag) that represents its distance from the starting point to one of its roads.

2. At the beginning of the algorithm, an array V is used to store the list of unreached nodes, which is temporarily called the candidate list. Select node 1 as the starting node. At the beginning, D1 of node 1 = 0, Di of other nodes = infinity, and V is all nodes. After initializing the condition, then start the iterative algorithm until V is an empty set. The specific iterative steps are as follows:

Remove the node Di with the lowest D value from the candidate list. (in this example, the data structure of V adopts the priority queue to realize the minimum value out of the column. It is best to use the Fibonacci pair. It has been introduced in previous articles, and the performance has been greatly prompted). For each edge starting from this node, excluding the node removing V, (I, J) belongs to A. if DJ > Di + AIJ (violating the relaxation condition), make

DJ = Di + AIJ, (if J has been removed from V, its minimum distance has been calculated and will not participate in this calculation)

It can be seen that in the operation engineering of the algorithm, the D value of the node is monotonic and does not increase

The specific algorithm is illustrated as follows

3、 Java code implementation

The above is the whole content of this article. I hope it will be helpful to your study, and I hope you can support programming tips.