Dijkstra algorithm (Solving single-source shortest path problems with no negative edge weights)

(this article has public, address: mp.weixin.qq.com/s/Gzm00enOV…).

Cover:

E. W. Dijkstra (1930/05/11-2002/08/06), distinguished computer scientist, 1972 Turing Award winner.

The resources

• Algorithms (4th Edition) : This book gives the “index heap” (time complexity: O(Elog⁡V)O(E \log V)O(ElogV)), because the “index heap” is difficult to understand, so we use the “priority queue” (can be considered as “heap”) as the code implementation, and directly give the “heap optimization” version (time complexity: O (Elog ⁡ E) (E/O log E) O (ElogE));
• Section 24.3, Introduction to Algorithms: Dijkstra’s algorithm

Dijkstra’s algorithm is trying to solve

• Shortest path problem of weighted graph;
• Both directed and undirected;
• Premise: No negative edge weights.

Solve the problem of single source shortest path with no negative weight edge: namely, the shortest path from one vertex to other vertices.

Note: this example comes from liuyubobobo’s mooc algorithms and data structures – comprehensive enhancement C++ edition. This example is chosen because it is simple enough to clarify the idea of Dijkstra’s algorithm.

geometry

• To understand the source point, all of the examples we’ve shown here0Is the source point;
• Pull the source point up from the horizontal plane to form the figure below.

Note: These curved edges are eliminated by the “relaxation operation”.

Relaxation operation (emphasis on “no negative edge weights”)

• This path, 0 -> 2, is the shortest path from vertex 0 to vertex 2. There’s no negative edge weight, so there’s not going to be an edge, and we’re going to take a detour back to vertex two, and the sum of the paths is smaller.

In fact, from 0 to 1, we go through 2 to 1, the sum of the paths 2+1<52 +1<52 +1<5, that’s what relaxation is all about. Just like when we fly, sometimes there are stops and the fare may be lower.

To understand the relaxation operation again: 555 is greater than 222, and 555 plus a non-negative integer can’t be less than 222.

Dijkstra algorithm execution steps

So we start off with the shortest path from 0 to ourselves, the shortest path is 0, and we temporarily think of it as minus infinity to the other vertices.

Of all the sides that go from 0, the distance to 2 is the shortest, so we can say that the length of the side that goes from 0 minus greater than 2 is the shortest path from 0 to 2. It also updates the distance from 0 to its neighboring vertices.

Now let’s see if it’s possible that the distance from 2 to its neighboring vertices is even shorter.

Of the undetermined vertices at this point, the shortest distance is 1 (distance is 3), so the shortest distance from source 0 to vertex 1 is 3.

Now we update the vertex starting from 3, with only edges 3 -> 4 (length 2). Now the distance to 3 is 5, 5+2>45 +2>45 +2>4, so the distance to 4 is not updated. The relaxation operation did not find a better solution.

Now, of the vertices that are not defined, the shortest distance is 4, and there are no adjacent vertices from 4.

The last vertex is going to be 3, so in the end we’ve determined the distance of 3.

Now if we look at Dijkstra’s original idea, it’s easy to understand. The unselected edges of the relaxation operation, which are the curved edges of this legend, must not be the edges that make up the single-source shortest path.

Code implementation

We write directly a version based on priority queues, often called Dijkstra’s algorithm for heap optimization.

Reference Code 1:

• Our simplified graph construction uses an array to represent a directed edge: [start, end, weight][start, end, weight][start, end, weight];
• Use Boolean arraysvisitedWhich vertices have been accessed from the source, and the corresponding logic in the priority queue is; Take out the edge with the least weight of the vertex that has not been visited, and do a relaxation operation;
• The code of relaxation operation may be difficult to understand at the beginning of learning, so I hope to practice more and deepen my experience.

Java code:

import java.util.Arrays;
import java.util.Comparator;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Set;

public class Dijkstra {

    public int[] shortestPath(int[][] edges, int V, int source) {
        // key: node number (output degree) value: [node number (pointed vertex), weight]
        Set<int[]>[] adj = new HashSet[V];
        for (int i = 0; i < V; i++) {
            adj[i] = new HashSet<>();
        }
        // Initialize the adjacency list
        for (int[] time : edges) {
            adj[time[0]].add(new int[]{time[1], time[2]});
        }

        // Initialize the Distance array and visited array
        int[] distance = new int[V + 1];
        Arrays.fill(distance, 0x7fffffff);
        boolean[] visited = new boolean[V + 1];

        // The starting distance is 0
        distance[source] = 0;
        // Note: 0 is meaningless, so it needs to be initialized to 0
        distance[0] = 0;

        // Note: there is a mapping
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(Comparator.comparingInt(o -> distance[o]));
        minHeap.offer(source);

        // The main idea is to consider edge relaxation
        while(! minHeap.isEmpty()) {// Dijkstra algorithm step 1: select the edge with the shortest weight so far from the edge where the vertex of the shortest path is not determined
            Integer v = minHeap.poll();
            if (visited[v]) {
                continue;
            }

            // Dijkstra algorithm step 2: mark access, indicating that this vertex can currently determine the shortest path from the source point to it
            visited[v] = true;

            // Dijkstra algorithm step 3: start from the identified vertices, perform relaxation on these edges
            Set<int[]> successors = adj[v];
            for (int[] edge : successors) {
                int next = edge[0];
                if (visited[next]) {
                    continue;
                }

                // The core of Dijkstra: relaxation operation
                distance[next] = Math.min(distance[next], distance[v] + edge[1]); minHeap.offer(next); }}return distance;
    }

    public static void main(String[] args) {
        int[][] times = {
                {0.1.5},
                {0.2.2},
                {0.3.6},
                {1.4.1},
                {2.1.1},
                {2.4.5},
                {2.3.3},
                {3.4.2}};
        int N = 5;
        int K = 0;
        Dijkstra dijkstra = new Dijkstra();
        int[] distance = dijkstra.shortestPath(times, N, K); System.out.println(Arrays.toString(distance)); }}Copy the code

Complexity analysis:

• Time complexity: O(Elog⁡E)O(E \log E)O(ElogE), where EEE is the number of edges in the graph. In the worst case, each edge will enter the priority queue, and the edge with the minimum weight of the vertices that have not been traversed is selected from the priority queue. The complexity is O(log⁡E)O(\log E)O(logE);
• Space complexity: O(E+V)O(E +V)O(E +V)O(E +V), the length of the shortest path array is VVV, where VVV is the number of vertices in the graph, and the length of the priority queue is EEE.

(Complexity analysis is my weakness, if you have any questions, please point out.)

The code given above, with minor modifications, can be run directly in question 743 of “Force button” : network latency.

I have negative edge weights

Bellman-ford Algorithm has a queue-based optimization Algorithm called Shortest Path Faster Algorithm (SPFA), which is introduced in Algorithm (4th Edition).

We’ll have a chance to do a summary later.

Stage Summary of Graph Theory knowledge System (not comprehensive)

Minimum spanning tree algorithm

Shortest path algorithm

Note: negative weight cycle is meaningless to solve the single source shortest path problem.