Shortest Path Problem — Dijkstra Algorithm

Scan the qr code below or search wechat public account Rookie Fei Yafei, you can follow wechat public account, read more Spring source code analysis, Java concurrent programming, Netty source code series and MySQL working principle articles.

Vacation is too long, resulting in a long time to stop, review an algorithm to find a feeling.

Some time ago, I saw an article, which mentioned the ten algorithms governing the world, one of which is Dijkstra algorithm, which mainly solves “shortest path” this kind of problem. Although it is an exaggeration, it is indeed widely used in real life, such as map software, automatic path finding and other functions in most games, and the A* search algorithm used is also based on the optimization of dijkstra algorithm. So how does the Dijkstra algorithm work?

Suppose we now have a directed graph with six vertices numbered from 1 to 6, the lines with arrows indicate the distance between one vertex and another, and the numbers on the lines indicate the distance between the two vertices. Now find the shortest distance between vertex 1 and vertex 6.

Because the number of points in the graph is relatively small, we can calculate this result directly by hand, but if there are many vertices, there are thousands of vertices, it is difficult to calculate by hand, we can only calculate through the program, so how to write our program?

Train of thought

As we can see from the figure, vertex 1 can only go directly to vertex 2, 3, and 5, but not to vertex 6, so to go from 1 to 6, we must transfer from other vertices.

We define an array that represents the distance from each vertex to vertex 1. The index of the array represents the vertex number, and the value of the array element represents the minimum distance to vertex 1.

1. We start at vertex 1, vertex 1 can go to 2, 3, 5, and the array looks like this.

   The index	1	2	3	4	5	6
   The minimum distance	0	60	10	null	50	null

2. From vertex 2, vertex 2 can reach vertex 4 at a distance of 35, so the distance from vertex 1 to vertex 4 is 60+35=95, and the array state is as follows:

3. It goes from vertex 3, vertex 3 goes to vertex 4, distance is 30. If you go through vertex 3, then the distance from 1 to 4 is 40, which is less than the distance from vertex 2, so the distance from vertex 4 in the array is updated to 40. Vertex 3 can also reach vertex 5. Similarly, through vertex 2, the distance from 1 to 5 is 10+25=35, which is less than the distance from 1 to 5 directly. Therefore, the distance from the array to vertex 5 is updated to 35.

4. If vertex 1 reaches 2 through vertex 5, the distance is 35+30=65. If vertex 1 reaches 2 through vertex 5, the distance is larger than vertex 1 and it directly reaches 2, so no update is made. Since vertex 2 has already traversed all the points it can reach, it doesn’t need to be traversed again. Vertex 5 can also reach vertex 6, so the distance from 1 to 6 is 35+105=140, and the array state is as follows:

5. From vertex 4, vertex 4 can also reach vertex 6. If you go through vertex 4, then the distance from 1 to 6 is 40+15=55, which is less than the distance from 5, so update the array. After update, the array state is as follows:

The above process is the core process of Dijkstra algorithm in calculating the shortest path problem.

Code implementation

First of all, we need to express the directed graph in code. Usually, there are two ways to express the graph: the first is the adjacency matrix (that is, the two-dimensional array), and the second is the adjacency list (that is, the array + linked list). Here, we choose the adjacency list method to represent a directed graph.

In addition, we also need to define edges between vertices. An Edge has a starting point and an ending point, and the weight information of the Edge, namely the length, is represented by Edge class. The code is as follows:

private class Edge {
    // Start point
    public int s;
    // Terminate point
    public int t;
    // Edge weights
    public int weight;

    Edge(int s, int t, int weight) {
        this.s = s;
        this.t = t;
        this.weight = weight; }}Copy the code

The directed Graph is represented by the class Graph, which has two properties: the number of vertices v and the array addEdge that describes the information about edges between vertices. We also provide a method, addEdge, to add an edge between two vertices. The code is as follows:

public class Graph {

    // Number of vertices (vertices are numbered from 0; in this example, vertices numbered 0 do not exist)
    private int v;

    // Record the edges of each vertex
    private LinkedList<Edge>[] adj;

    public Graph(int v) {
        this.v = v;
        / / initialization
        this.adj = new LinkedList[v];
        for (int i = 0; i < v; i++) {
            adj[i] = newLinkedList(); }}
    // Add an edge from s to t
    public void addEdge(int s, int t, int weight) {
        Edge edge = newEdge(s, t, weight); adj[s].add(edge); }}Copy the code

After the description of the graph is defined, the dijkstra algorithm is implemented through the code, and its code and notes are as follows.

There are two pieces of logic to explain a little bit. The first place: So the flag array is a record of vertices that have been walked through, to prevent infinite loops, so for example vertex 1 can go to 2, and then we decide what points 2 can go to, vertex 1 can go to 5, and then 5 can go to 2, and if there’s no flag array for vertex 2 we’ve already walked through, So we’re going to keep going through 2, which is going to cause an infinite loop. The predecessor array records path information. The index of the array represents the number of vertices, and the value of the element represents which vertex reaches the current vertex. For example, predecessor[3]=1 represents the vertex 3 reached through vertex 1.

// Use dijkstra algorithm to find the shortest path from s to t
public void dijkstra(int s, int t) {
    int[] dist = new int[v];    // Record the minimum distance from s to each vertex, the array subscript indicates the vertex number, the value indicates the minimum distance
    boolean[] flag = new boolean[v];    // The array subscript indicates the vertex number, and the value indicates whether the vertex was traversed
    for (int i = 0; i < v; i++) {
        dist[i] = Integer.MAX_VALUE;    // Set the initial distance between vertex S and other vertices to infinity
    }
    int[] predecessor = new int[v];     // Record the path, index indicates the number of the vertex, the value indicates which vertex reached the current vertex
    Queue<Integer> queue = new LinkedList<>();
    queue.add(s);
    dist[s] = 0;    // the path of s->s is 0
    while(! queue.isEmpty()) { Integer vertex = queue.poll();if (flag[vertex]) continue; // The vertex is already traversed, so it is not traversed again
        flag[vertex] = true;
        for (int i = 0; i < adj[vertex].size(); i++) {
            Edge edge = adj[vertex].get(i);
            if (dist[vertex] < (dist[edge.t] - edge.weight)) {  // If a path smaller than the current path appears, update it to a smaller pathdist[edge.t] = dist[vertex] + edge.weight; predecessor[edge.t] = vertex; } queue.add(edge.t); }}// Prints the path
    System.out.println("Shortest distance:" + dist[t]);
    System.out.print(s);
    print(s, t, predecessor);
}
Copy the code

The print function prints the points that need to be passed in the shortest path from vertex S to vertex T. The code is as follows:

// Prints the path
private void print(int s, int t, int[] predecessor) {
    if (t == s) {
        return;
    }
    print(s, predecessor[t], predecessor);
    System.out.print("- >" + t);
}
Copy the code

test

Based on the example, build a graph and test the results as follows:

public static void main(String[] args) {
    / / build
    Graph graph = new Graph(7);
    graph.addEdge(1.2.60);
    graph.addEdge(1.3.10);
    graph.addEdge(1.5.50);
    graph.addEdge(2.4.35);
    graph.addEdge(3.4.30);
    graph.addEdge(3.5.25);
    graph.addEdge(4.6.15);
    graph.addEdge(5.2.30);
    graph.addEdge(5.6.105);
    // Calculate the shortest distance
    graph.dijkstra(1.6);
}
Copy the code

Test results:

conclusion

The idea of dijkstra is similar to that of breadth-first search (BFS), where you find the vertices you can reach and then spread out until you have traversed all the vertices.