preface
In this article, I will introduce three classical algorithms for solving shortest paths — Dijkstra, Bellman-Ford and Floyd-Warshall.
Dijkstra algorithm
The shortest path
The shortest path problem is a classical algorithm problem in graph theory, which aims to find the shortest path between two nodes in graph.
For example, the figure above is an undirected graph. The shortest path from node 0 to node 3 is:
0 -> 2 -> 1 -> 3
Copy the codeThe path length is 5.
What is the significance of studying the shortest path algorithm? Or what problems can the shortest path algorithm solve?
As we all know, subway is one of our important means of transportation in life. When we input the starting point and destination in the subway ticket office or software, the mobile phone software will give us the best travel plan with the minimum cost or the shortest time. The realization of navigation software is actually a specific application of the shortest path algorithm.
The study of shortest path algorithm aims at solving travel problems, tourism problems, engineering costs and other problems, which is of great significance in computer science, operations research and geographic information science.
Dijkstra algorithm
Dijkstra algorithm is one of the classical algorithms for solving single source shortest circuit. It was invented by Dutch computer scientist Dijkstra in 1956.
The prerequisite for using Dijkstra’s algorithm is that there are no negative weighted edges in the graph. So once I’ve explained the idea of Dijkstra, I think you can see why it’s a prerequisite for Dijkstra to not have a negative edge weight in a graph. However, this precondition does not affect most of the problems we solve. For example, take the subway line with the minimum solving cost above as an example. If the weight of each edge in the figure represents the amount spent from one node to another, then the amount must be greater than 0. Therefore, even if Dijkstra algorithm cannot deal with graphs with negative weights, it can still solve most problems in the research field of shortest path.
Next, let’s look at the specific idea of Dijkstra’s algorithm:
In the figure above, the source point is 0, and table DIS represents the shortest path from the source point to each point. Since we don’t know what the shortest path from the source point to each point is at the beginning, the initial value is infinity infinity infinity, and the shortest path from the source point to the source point is already determined, which is 0.
We start with the source point and find the nodes adjacent to the source point (1, 2), edge 0-1 has weight 4, edge 0-2 has weight 2, because their values are smaller than the value in the current DIS array, so we update the DIS array,dis[1] is updated to 4,dis[2] is updated to 2, The weights of the remaining nodes remain infinity infinity infinity. At this point, we can determine that the shortest path from the source to this point is the shortest path of the current undetermined shortest path.
It may be confusing to say so, but let’s visualize the process through the diagram:
First, find the node that has been determined to be the most short-circuited, which is node 0 marked in yellow in the figure. Then update all nodes that have not been determined to be the most short-circuited. The blue nodes represent the nodes THAT I have updated.
Finally, the shortest path among the undetermined shortest nodes is the shortest path from the source point to that point.
As shown in the figure above, dis[2] has the smallest value, so we can determine that the shortest path from source point 0 to node 2 is dis[2].
How can this argument be proved?
Dijkstra’s algorithm is greedy and requires a rigorous mathematical induction, which I’m not going to do here, so you can search for it yourself. Proof of correctness.
We demonstrate this idea in a way that is easy to understand. In the figure above, the weight of the edge from source point SSS to node AAA is denoted as dis[a]dis[a]dis[a]. Similarly, the weight of the edge from source point SSS to node BBB and CCC is denoted as dis[b]dis[b] and dis[c]dis[c]dis[c].
Dis [a]>dis[b]dis[a] >dis[b]dis[a] >dis[b]dis[a] >dis[b], dis[a]>dis[c]dis[a] >dis[c] Dis [a]dis[a]dis[a] is the shortest path from the source SSS to node AAA.
So, we can be sure that Dijkstra’s idea is correct, and we have indirectly shown why the precondition for Dijkstra’s algorithm is that there can be no negative edge weights in the graph.
Then we continued with this idea and continued to simulate the process:
First, we update the DIS array with the node that has been determined to be the shortest. Here, we can see that dis[1] is updated to 3, which is also known as Relaxation or Relaxation. Relaxation can be understood as we choose to use a long “distance” as the shortest path between two nodes. As can be seen, The shortest path between node 0 and node 1 is not the edge between the two nodes, but the 0-2-1 path.
We determine the node with the smallest value from the current nodes with the most undetermined short-circuit:
Repeating the above process, we can get the shortest path from source point 0 to all nodes in the graph:
Dijkstra algorithm code implementation
The Java code for Dijkstra’s algorithm is shown below, but I won’t explain it all because I’ve annotated the code in detail. In addition, due to the limited space in this article, I will provide links to the test code at the end of the article, and the test cases and code will not be covered here.
Dijkstra
import java.util.Arrays;
public class Dijkstra {
private WeightedGraph G;
private int s;
private int[] dis;
private boolean[] visited;
public Dijkstra(WeightedGraph G, int s) {
this.G = G;
// Determine the validity of the source point s
if (s < 0 || s >= G.V())
throw new IllegalArgumentException("vertex" + s + "is invalid");
this.s = s;
// Initialize the dis array
dis = new int[G.V()];
Arrays.fill(dis, Integer.MAX_VALUE);
dis[s] = 0;
visited = new boolean[G.V()];
// Dijkstra algorithm flow
// 1. Find the shortest node that is not currently accessed
// 2. Verify that the shortest path of this node is the current size
// 3. According to the shortest path size of this node, find the nodes adjacent to this node and update the path length of other nodes
while (true) {
int curdis = Integer.MAX_VALUE;
int cur = -1;
// 1. Find the smallest node that is not accessed
for (int v = 0; v < G.V(); v++)
if(! visited[v] && dis[v] < curdis) { curdis = dis[v]; cur = v; }// if cur == -1, all processes end
if (cur == -1) break;
// 2. Confirm that the shortest circuit of this node is the current size, and update visited
visited[cur] = true;
// 3. According to the shortest path size of this node, find the nodes adjacent to this node and update the path length of other nodes
for (int w : G.adj(cur))
if (!visited[w] && dis[cur] + G.getWeight(cur, w) < dis[w])
dis[w] = dis[cur] + G.getWeight(cur, w);
}
}
public boolean isConnected(int v) {
if (v < 0 || v >= G.V())
throw new IllegalArgumentException("vertex" + s + "is invalid");
return visited[v];
}
public int dis(int v) {
if (v < 0 || v >= G.V())
throw new IllegalArgumentException("vertex" + s + "is invalid");
returndis[v]; }}Copy the codeLet’s analyze the time complexity of this algorithm. The outer layer of the algorithm is a while loop, and the inner layer traverses every vertex in the graph. The termination condition of the while loop is that the shortest path of each node is determined, so the time complexity of the algorithm is O(V2)O(V^2)O(V2), where VVV is the number of vertices in the graph.
So if you think about it, is there room for optimization in Dijkstra? In fact, it is not difficult to find that in our algorithm class, the operation of finding the smallest unvisited node in the graph must traverse all nodes of the graph every time, which can be optimized. Usually, in greedy problems, the optimization strategy is to use priority queues.
Priority queues and Pair classes
A Priority Queue is a special Queue in which each element has its own Priority. The element with the highest Priority gets service first. Elements of the same priority are served in the order they are placed in the priority queue. Priority queues are often implemented using heap data structures.
In the Java language, the default implementation of a priority queue is the minimum heap, and we can use a custom comparator to specify the priority of each element of the priority queue.
In our Dijkstra algorithm class, the elements in the priority queue should maintain cur and CURdis information, and the priority queue should be sorted in order of curdis from smallest to largest.
It was natural to want to customize a class that maintains two variables, cur and curdis; We then let the class implement the Comparable interface and define our comparison logic in the compareTo method.
I recommend using the Pair class in the com.sun.tools.javac.util package that comes with the JDK.
Pair
public class Pair<A.B> {
public final A fst;
public final B snd;
public Pair(A var1, B var2) {
this.fst = var1;
this.snd = var2;
}
public String toString(a) {
return "Pair[" + this.fst + "," + this.snd + "]";
}
public boolean equals(Object var1) {
return var1 instanceof Pair && Objects.equals(this.fst, ((Pair)var1).fst) && Objects.equals(this.snd, ((Pair)var1).snd);
}
public int hashCode(a) {
if (this.fst == null) {
return this.snd == null ? 0 : this.snd.hashCode() + 1;
} else {
return this.snd == null ? this.fst.hashCode() + 2 : this.fst.hashCode() * 17 + this.snd.hashCode(); }}public static <A, B> Pair<A, B> of(A var0, B var1) {
return newPair(var0, var1); }}Copy the codeWe used pair-fst to store information about cur and pair-snd to store information about CURdis. The simplified Dijkstra algorithm class using priority queues is as follows:
Dijkstra_2
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
public class Dijkstra_2 {
private WeightedGraph G;
private int s;
private int[] dis;
private boolean[] visited;
public Dijkstra_2(WeightedGraph G, int s) {
this.G = G;
// Determine the validity of the source point s
if (s < 0 || s >= G.V())
throw new IllegalArgumentException("vertex" + s + "is invalid");
this.s = s;
// Initialize the dis array
dis = new int[G.V()];
Arrays.fill(dis, Integer.MAX_VALUE);
dis[s] = 0;
visited = new boolean[G.V()];
// Dijkstra algorithm flow
// 1. Find the shortest node that is not currently accessed
// 2. Verify that the shortest path of this node is the current size
// 3. According to the shortest path size of this node, find the nodes adjacent to this node and update the path length of other nodes
PriorityQueue<Pair<Integer, Integer>> pq = new PriorityQueue<>(Comparator.comparingInt(o -> o.snd));
pq.offer(new Pair<>(s, 0));
while(! pq.isEmpty()) {int cur = pq.poll().fst;
if (visited[cur]) continue;
visited[cur] = true;
for (int w : G.adj(cur))
if(! visited[w] && dis[cur] + G.getWeight(cur, w) < dis[w]) { dis[w] = dis[cur] + G.getWeight(cur, w); pq.offer(newPair<>(w, dis[w])); }}}public boolean isConnected(int v) {
if (v < 0 || v >= G.V())
throw new IllegalArgumentException("vertex" + s + "is invalid");
return visited[v];
}
public int dis(int v) {
if (v < 0 || v >= G.V())
throw new IllegalArgumentException("vertex" + s + "is invalid");
returndis[v]; }}Copy the codeWhat is the complexity of the optimized Dijkstra algorithm?
The upper bound of the number of elements inserted into the priority queue is the number of edges in the graph EEE, and the complexity of the operation to queue out and queue in the priority queue is log(E)log(E)log(E), so the time complexity of our optimized Dijkstra algorithm is O(ElogE)O(ElogE)O(ElogE) O(ElogE).
Well, that’s it for Dijkstra. As we can see, the flow of Dijkstra’s algorithm is not difficult to understand, the idea is a greedy strategy, but our code is a little bit more complicated to write. If you find the code difficult to understand, you can try to write your own code first, and then you can better understand the meaning of each sentence in the sample code
Bellman – Ford algorithm
In the previous chapter, we introduced Dijkstra. Dijkstra mainly deals with single-source shortest path problems with no negative weight edges.
So how to solve the shortest path problem for graphs with negative edge weights?
Negative QuanHuan
Let’s take a look at this graph:
The graph is an undirected weighted graph that requests the shortest path from node A to node C.
You might say that a -> b -> C is the shortest path from node A to node C, which has a value of -2. . Wait, that doesn’t seem to be the case.
For the above undirected graph, if there are negative weighted edges, then there seems to be no shortest path! Because I could start at node A and go around the loop indefinitely, I would never get to the shortest path — in fact, there was no need to go around and waste time at all, and once we got to node B, we repeatedly “swiped steps” on the b-C side :-).
Therefore, for an undirected graph, there must be no shortest path if there are negative weighted edges. The reason for this is that the negative weighted edge of an undirected graph is itself a negative weighted ring. For directed graphs, there is no shortest path if there is a negative weight cycle, as shown in the following figure:
This graph is a directed graph, but there is a negative weight cycle, we can not find the shortest path.
Say a digression, the author wrote here remembered a small story ~
The Kings of A and B quarreled. King A became angry and decided that 100 yuan of country B could only be exchanged for 90 yuan of country A. After hearing this, king B also made A regulation: 100 yuan of country A can only be exchanged for 90 yuan of country B. In Country A, there was A clever guy who took advantage of this rule and made A windfall. Do you know what he did? (Why do YOU feel so retarded after writing it?)
Back to the gossip.
For a graph with negative edge weights, we need to detect whether there is a negative weight cycle in the graph. If there is a negative weight cycle, then the graph must not have a shortest path. The detection of negative weight cycle is very simple in the implementation of the algorithm. Let’s first look at a classical algorithm for solving the shortest path with negative weight edge — Bellman-Ford algorithm.
Bellman – Ford algorithm
The bellman-Ford algorithm is based on relaxation.
Suppose that dis[v]dis[v]dis[v] is the shortest distance from source point SSS to node VVV passing by KKK.
If dis[a]+ab
Therefore, we find the shortest distance from source point SSS to node BBB that the number of edges passing through does not exceed K +1k+1k+1.
Similarly, if dis[b]+ba
In this way, we find the shortest distance from source point SSS to node AAA that does not exceed k+1k+1k+1.
According to the above theory, our Bellman-Ford algorithm flow is as follows:
- Initialize dis array,
dis[s] = 0, the remaining values are set to
- A relaxation operation is performed on all edges to find the shortest path with at most one edge to all points
- A further relaxation of all edges gives the shortest path with at most two edges to all points
- . .
- V-1 relaxation of all edges is performed to find the shortest path with at most V-1 edges to all points
There are only V vertices in our graph. If there is no negative weight cycle, there are no more than V-1 edges from one vertex to another. Therefore, after v-1 relaxation operation on all edges, we find the shortest circuit from the source point to all points, and bellman-Ford algorithm supports the existence of negative weight edges.
Next, let’s simulate the execution process of Bellman-Ford algorithm through an example. I believe that through this simulation process, you will have a deeper understanding of Bellman-Ford algorithm š
The figure above is a directed weighted graph. We specify node 0 as the source point, and the initial value of the shortest circuit from the source point to the source point is 0. The remaining nodes are represented by infinity infinity.
First, we perform a relaxation on all edges. Suppose we relax 0-1, 0-2, and 2-1. After the first relaxation, our DIS array is updated as follows:
After the first relaxation, we’ve actually figured out the shortest path from the source to the vertices.
It looks like we don’t need v-1 relaxation, right? Is that right? In fact, v-1 relaxation is an upper bound, and it’s entirely possible to get it after less than V-1 relaxation, but in the worst case, we only need V-1 relaxation.
In the example above, we relaxed from the 0-1 edge. If we thought about it differently, what would happen if we relaxed from the 2-1 edge?
Suppose we relax the edge 2-1, then the edge 0-1, and finally the edge 0-2. After the first relaxation, our DIS array is updated as follows:
Note that when we relax the 2 minus 1 edge, we use infinity minus 6 infinity minus 6 infinity minus 6 infinity, which is still infinity infinity.
After the second relaxation, our DIS array is updated as follows:
And we see that after twice relaxing all the edges, we also have the right solution.
So how do you detect the negative weight cycle?
In fact, it is very simple. According to Bellman-Ford algorithm, if there is no negative weight cycle in our graph, we can get the shortest path from the source point to each node after V-1 relaxation operation. If we relax all edges after V-1 relaxation operation, the DIS value of each point will not change. However, if there is a negative weight ring in the graph, after v-1 round relaxation operation, then relaxation operation, each value of dis array will still change.
Therefore, in the design of the algorithm, we only need to perform another relaxation operation after v-1 relaxation operation to determine whether the DIS array has changed. If it has changed, it indicates that there is a negative weight ring in the figure, that is, the shortest path cannot be obtained.
Next, let’s look at a concrete implementation of the Bellman-Ford algorithm.
Bellman-ford algorithm code implementation
The Java code for bellman-Ford is as follows, with detailed comments that I won’t explain š
Again, links to the test code will be provided at the end of the article, so the test section will not be covered in this article.
Bellman-Ford
import java.util.Arrays;
public class BellmanFord {
private WeightedGraph G;
private int s;
private int[] dis;
public boolean hasNegativeCycle = false;
public BellmanFord(WeightedGraph G, int s) {
this.G = G;
if (s < 0 || s >= G.V())
throw new IllegalArgumentException("vertex" + s + "is invalid");
this.s = s;
dis = new int[G.V()];
Arrays.fill(dis, Integer.MAX_VALUE);
dis[s] = 0;
// V-1 round relaxation operation
for (int pass = 1; pass < G.V(); pass++) {
for (int v = 0; v < G.V(); v++)
for (int w : G.adj(v))
if(dis[v] ! = Integer.MAX_VALUE && dis[v] + G.getWeight(v, w) < dis[w]) dis[w] = dis[v] + G.getWeight(v, w); }// Perform the relaxation (relaxation) operation again to determine the negative weight ring
for (int v = 0; v < G.V(); v++)
for (int w : G.adj(v))
if(dis[v] ! = Integer.MAX_VALUE && dis[v] + G.getWeight(v, w) < dis[w]) hasNegativeCycle =true;
}
public boolean isConnected(int v) {
if (v < 0 || v >= G.V())
throw new IllegalArgumentException("vertex" + v + "is invalid");
returndis[v] ! = Integer.MAX_VALUE; }public int dis(int v) {
if (v < 0 || v >= G.V())
throw new IllegalArgumentException("vertex" + v + "is invalid");
if (hasNegativeCycle) throw new RuntimeException("Exist negative cycle");
returndis[v]; }}Copy the codeWhat is the time complexity of Bellman-Ford? We need to carry out v-1 round relaxation operation, each relaxation operation will traverse all edges in the graph, so the time complexity of Bellman-Ford algorithm is O(VE)O(VE)O(VE). It can be seen that although Bellman-Ford algorithm can solve the negative-weighted edge, its overall complexity is worse than Dijkstra algorithm.
That’s all for bellman-Ford algorithm. Next, let’s look at the last algorithm introduced in this article — Floyd-Warshall algorithm.
Floyd – Warshall algorithm
We introduced Dijkstra and Bellman-Ford algorithms for solving single-source shortest paths earlier, while floyd-Warshall algorithm introduced in this chapter is an algorithm for solving the shortest paths of all point pairs (any two points).
What does solving for all the points mean for shortest paths?
If we know the shortest path of any two points in the graph, we can get the maximum shortest path of any two points in the graph, and this term is called the diameter of the graph.
For example, if our graph represents an Internet network system, and the edge between nodes represents the transmission delay of two intermediate stations, how to evaluate the performance of this network system? At this point, solving the diameter of the graph is of great significance. Solving the diameter of the graph requires solving the shortest paths of all point pairs.
For Dijkstra algorithm, the complexity of solving the single-source shortest path is O(ElogE)O(ElogE)O(ElogE). If all the point-pair shortest paths are solved, the single-source path problem needs to be solved once for each vertex in the graph. Therefore, Its complexity is O(VElogE)O(VElogE)O(VElogE); Bellman-ford algorithm is used to analyze and solve the shortest path of all point pairs in the same way, and its time complexity is O(V2E)O(V^2E)O(V2E).
For Floyd-Warshall algorithm, the time complexity of solving the shortest path of all point pairs is O(V3)O(V^3)O(V3), and it can solve the negative weight edge. Next, let’s look at the specific ideas of Floyd-Warshall algorithm.
Because floyd-Warshall does not have the concept of a source node, or it can be thought of as a source node for each node, we use a disdisdis array, Dis [v][w]dis[v][w]dis[v][v][w] represents the shortest path from vertex VVV to vertex WWW.
Dis [v][v]dis[v][v]dis[v][v] dis[v][v]dis[v][v]dis[v][w]dis[v][w]dis[v] The initial value of dis[v][w]dis[v][w]dis[v][w] is the weight of the node VVV and the node WWW, VWVWVW, and the rest is expressed as āā.
The pseudo-codes of Floyd-Warshall algorithm are as follows:
for(int t = 0; t < V; t++)
for(int v = 0; v < V; v++)
for(int w = 0; w < V; w++)
if(dis[v][t] + dis[t][w] < dis[v][w])
dis[v][w] = dis[v][t] + dis[t][w]
Copy the codeWhat process is this pseudocode describing?
If there is a node TTT between node VVV and node WWW, And dis [v] [t] + dis [t] [w] < dis [v] [w] dis [v] [t] + dis [t] [w] < dis [v] [w] dis [v] [t] + dis [t] [w] < dis [v] [w], Then update dis[v][w] dis[v][w] dis[v][w] dis[v][w] dis[v][w] dis[v][w] So how do we understand what TTT means?
TTT is the shortest path that passes through [0…t][0…t][0…t] in each cycle.
- To assign the initial value, we only consider the distance between vertex VVV and vertex WWW without passing through any vertices;
- When t=0t =0t =0, we consider whether the current shortest path is updated after the vertex between VVV and WWW passes through 0;
- When t=1t =1t =1, we consider whether the current shortest path is updated if the vertex VVV and vertex WWW pass through the vertices in [0,1][0,1][0,1].
- When t=Vā1t = V-1t=Vā1, we consider whether the current shortest path is updated if the vertex VVV and vertex WWW pass between the vertices in [0…Vā1][0…V-1][0…Vā1].
The principle of floyd-Warshall algorithm detecting negative weight cycles is actually the same as that of Bellman-Ford algorithm. After the algorithm, we only need to traverse all the vertices of the graph once. Dis [v]dis[v] dis[v] dis[v] dis[v] dis[v] dis[v] dis[v] dis[v] dis[v] dis[v]
Ok, so that’s the floyd-Warshall algorithm flow, let’s look at the specific code implementation.
Floyd-warshall algorithm code implementation
Floyd-Warshall
import java.util.Arrays;
public class FloydWarshall {
private WeightedGraph G;
private int[][] dis;
public boolean hasNegativeCycle = false;
public FloydWarshall(WeightedGraph G) {
this.G = G;
dis = new int[G.V()][G.V()];
for (int i = 0; i < G.V(); i++)
Arrays.fill(dis[i], Integer.MAX_VALUE);
for (int v = 0; v < G.V(); v++) {
dis[v][v] = 0;
for (int w : G.adj(v))
dis[v][w] = G.getWeight(v, w);
}
for (int t = 0; t < G.V(); t++)
for (int v = 0; v < G.V(); v++)
for (int w = 0; w < G.V(); w++)
if(dis[v][t] ! = Integer.MAX_VALUE && dis[t][w] ! = Integer.MAX_VALUE && dis[v][t] + dis[t][w] < dis[v][w]) dis[v][w] = dis[v][t] + dis[t][w];for (int v = 0; v < G.V(); v++)
if (dis[v][v] < 0) hasNegativeCycle = true;
}
public boolean isConnected(int v, int w) {
if (v < 0 || v >= G.V())
throw new IllegalArgumentException("vertex" + v + "is invalid");
if (w < 0 || w >= G.V())
throw new IllegalArgumentException("vertex" + w + "is invalid");
returndis[v][w] ! = Integer.MAX_VALUE; }public int dis(int v, int w) {
if (v < 0 || v >= G.V())
throw new IllegalArgumentException("vertex" + v + "is invalid");
if (w < 0 || w >= G.V())
throw new IllegalArgumentException("vertex" + w + "is invalid");
returndis[v][w]; }}Copy the codeAs can be seen, Floyd-Warshall algorithm is an easy-to-read algorithm. We can quickly see that the complexity of Floyd-Warshall algorithm is O(V3)O(V^3)O(V3). Although this complexity is not better than Dijkstra algorithm, Floyd-warshall algorithm can detect negative weight cycles, which is used in graphs with negative weight edges, and its complexity is better than bellman-Ford algorithm to solve the shortest paths of all point pairs.
However, the biggest advantage of Floyd-Warshall algorithm is its simplicity and beauty, which is integrated with the art of DP algorithm.
conclusion
In this article, I introduce to you three shortest path algorithms, which are Dijkstra algorithm, Bellman-Ford algorithm and Floyd-Warshall algorithm.
Dijkstra algorithm is a classical algorithm for solving the single-source shortest path. Although it cannot solve the graph with negative weight edges, Dijkstra algorithm is still a very meaningful algorithm. After all, a large part of the shortest path problems we solve are those without negative weight edges.
If we encounter the shortest path problem with negative weight edges, we can choose Bellman-Ford algorithm or Floyd-Warshall algorithm. The former is used to solve the shortest path problem of single source, while the latter can solve the shortest path problem of all point pairs.
Well, so far, this article is here ~ welcome to pay attention to my public number, here I hope you can harvest more knowledge, we see you in the next issue!