You have to –Dijkstra — single source shortest path problem

I. Algorithm principle

1. Fundamentals

Dijkstra algorithm is a single-source shortest path algorithm using breadth first search (BFS). Compared with the simple and crude time complexity O(n^3) Floyed algorithm (see my other blog for details, only five rows of Floyed algorithm and full path output), Dijkstra’s algorithm has a much better time complexity, O(n^2).

The algorithm takes the starting point as the center, adds adjacent edges to the priority queue, and every time the point nearest to the starting point in the queue is opened, the nearest distance between each adjacent node of the point and the source point is updated by means of relaxation operation (greedy algorithm principle is used here), which is stored into a set disTo. The closest distance between each point and the source point is recorded in this collection.

Pseudo code:

while(!queue.isEmpty())
	// Use the minimum priority queue to fetch the nearest node from the source point
	node = queue.poll()
	forEach neighbor node is a neighboring nodeifNeighbor is not visitedqueue.push(neightbor)
		ifGet (neighbor) > disto. get(node) + node distance to the neighboring point// Record the path
			neighbor.parent = node;
			//relaxation expansion operationDisto. put(Neighbor, disto. get(node) + node to the neighboring point distance)// Other operations
			todo...
Copy the code

2. How do I save the shortest path?

In the pathTo collection, set the previous node of this node. If this has not been visited, it added to the priority queue, so repeated operation layer traversal outward, finally you can generate a shortest path tree, for from the source point to a point of the shortest path problem, as long as see if this point is visited, the point being accessed indicating the shortest path, back pathTo collection, For example,pathTo(A) = B, where B is the nearest adjacent point from A to the source point (known from greedy algorithm),pathTo(B) = C, where C is the nearest adjacent point from B to the source point, repeated operations until pathTo(X) = the source point. You get the shortest path

Two. Algorithm implementation

package com.example.Dijkstra;

import java.util.*;

public class Dijkstra {
    // <1, [2, 3]> indicates that the parent node of node 1 is node 2 and the distance from the source point is 3
    private Map<Integer, int[]> disTo;
    / * * *@paramThe distance between one node and other nodes * [[0, 1, 1], [1, 2, 2]] indicates that the distance from point 0 to point 1 is 1, and the distance from point 1 to point 2 is 2 *@paramN Number of all nodes 1<= N <= 1000 *@paramK Source node 1< k <n */
    public Map<Integer, int[]> Dijkstra(int[][] edges, int n, int k) {
        // Generates a directed graph from the array of edges
        //<0, <{1,2}, {2,3}>> indicates that node 0 has 1,2 adjacent nodes with a distance of 2 and 3 respectively
        Map<Integer, List<int[]>> graph = new HashMap<>();
        for (int[] edge : edges) {
            if(! graph.containsKey(edge[0]))
                graph.put(edge[0].new ArrayList<>());
            graph.get(edge[0]).add(new int[]{edge[1], edge[2]});
        }
        // Initialize disTo
        disTo = new HashMap<>();
        for(int i = 0; i<n; i++){
            if(i==k)
                disTo.put(i, new int[] {0.0});
            else disTo.put(i, new int[] {-1, Integer.MAX_VALUE});
        }
        //Dijkstra
        // Omits the minimum priority queue and replaces it with an isSeen array assisted disTo
        boolean[] isSeen = new boolean[n];
        while(true) {// Get the nearest point
            int candiNode = -1;
            int candiDistance = Integer.MAX_VALUE;
            for(int i=0; i<n; i++){int[] temp = disTo.get(i);
                if(! isSeen[i] && temp[1]<candiDistance){
                    candiNode = i;
                    candiDistance = temp[1]; }}if(candiNode == -1) break;
            isSeen[candiNode] = true;
            if(graph.containsKey(candiNode))
                for(int[] edge : graph.get(candiNode)){
                    if(disTo.get(edge[0[])1]> candiDistance + edge[1]) {// Scale the adjacent points of this point
                        disTo.get(edge[0[])1] = candiDistance + edge[1];
                        // Update the parent node
                        disTo.get(edge[0[])0] = candiNode; }}}return disTo;
    }

    /** * Output result *@param disTo
     * @param end
     */
    public void printPath(Map<Integer, int[]> disTo,int pathTo){
        int distance = disTo.get(pathTo)[1];
        List<Integer> path = new ArrayList<>();
        int temp = pathTo;
        path.add(temp);
        while(temp! =0&& temp! = -1){
            temp = disTo.get(temp)[0];
            path.add(temp);
        }
        System.out.print("From initial node to node"+end+"The shortest distance is
        				+distance+"\n"+"The shortest path is: \n"+path.get(0));
        for(int i=1; i<path.size(); i++){ System.out.print("<--"+path.get(i)); }}}Copy the code

1. The test

Input:

Expected output: Shortest distance: 30 Path: 0–>1–>5–>4

Environment: Windows10, Java11

Results 2.

Knowing Dijkstra, not knowing DFS is even worse, helping you arrange recursive implementation and stack implementation of DFS