preface

In graph theory, besides Dijkstra algorithm, Floyd algorithm is also very classical in path finding shortest path. However, there are differences between the two algorithms. Floyd mainly calculates multi-source shortest path.

In the single-source positive weight shortest path, we will use Dijkstra algorithm to find the shortest path, and the idea of the algorithm is very simple — greedy algorithm: determine a point of the shortest path each time and then maintain (update) the distance of the points around the point into the pre-selection queue, waiting for the next throw determination. But while the idea is simple, the implementation is very complicated. We need adjacency matrices (tables) to store lengths, and priority queues (or comparisons each time) to maintain a set of preselected points. Also use a Boolean array to mark whether it has been determined and ———

In short, Dijkstra’s algorithm is easy to accept in idea, but very difficult to implement. But single-source shortest paths are no better. Also order n2.

In the n node multi-source shortest path, from the perspective of Dijkstra algorithm, we only need to encapsulate Dijkstra and execute Dijkstra algorithm n times, with the complexity of O(N3). But this feels very bloated, the code is huge, takes up a lot of space memory. Is there a way to spice things up a little bit?

The answer is yes, this is the easy to write but slightly tricky Floyd algorithm. A multivariate shortest path algorithm.

Algorithm is introduced

Take a look at baidu Baike’s definition:

Floyd algorithm, also known as interpolation method, is an algorithm that uses the idea of dynamic programming to find the shortest path between multiple source points in a given weighted graph, similar to Dijkstra algorithm. The algorithm is named after one of its founders, Robert Floyd, a 1978 Turing Award winner and professor of computer science at Stanford University.

Simply speaking, the main idea of the algorithm is dynamic programming (DP), and the shortest path needs continuous relaxation (those familiar with SPFA algorithm may be familiar with relaxation).

The specific idea of the algorithm is as follows:

  1. Adjacency matrix distStore the path, and the final state represents the shortest path of the dot. Default to a large value if no two points are directly connected (do not overflow)! And its length is 0.
  2. fromThe first to the NTHPoints are added to the graph in turn. Each point joins to proceedtemptationCheck whether the path length is changed.
  3. The specific test method mentioned above is to traverse every point in the graph (I, J double cycle) and judge whether the distance between each point pair changes at the minimum due to the points added. If it changes, then the distance between the two points (I,j) changes.
  4. Repeat until the final insertion is complete.

The state transition equation of the third step is:

  • dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j])Among themdp[x][y]The shortest path from x to y. sodp[i][k]It can be understood thatShortest path from I to kdp[k][j]It can be understood thatShortest path from k to j.

Let’s illustrate an example:

  • Joins the first node1As you can see, it’s not connected because of the addition of 12, 3Point to and2, 4The dot pairs become connected and add oneThe distance is currently the minimum. (you can intuitively add 2,4 after 5, shorter but not yet added). In order to better describe the fact that there are two more direct connection points. (2,3) and (2,4). We’re in dpIt doesn’t matter that the result came through the previous stepsBut in this state, the shortest distance between these two points is this!
  • At the same time you can find join1Which also makes3,1,4It’s connected, but3,1,4It’s 9 for unicom, far more than it would have been(3, 4)Is 2, so no update is made.
  • Let’s go ahead and add the second node. The initial state of addition is:
  • Traverse the insert to see if the node is updated

    There are actually more lines in the picture at this point. Of course, these connections are all representativeCurrent shortest path.And that also fits in with what we want, what we want is the shortest path to all the nodes.Each node should end up with six edges pointing to different nodes!Represents the final result of the adjacency matrix.

I’ve already told you about the two cores of the algorithm, and you can do the rest.

Program implementation

For a program, the insertion process is fairly simple. The core code is only four lines! The following code

public class floyd {
	static int max = 66666;// intege. Max is negative when the two are added together
	public static void main(String[] args) {
		int dist[][] = {
				{ 0.2.3.6, max, max }, 
				{ 2.0, max, max,4.6 }, 
				{ 3, max, 0.2, max, max },
				{ 6, max, 2.0.1.3 }, 
				{ max, 4, max, 1.0, max }, 
				{ max, 6, max, 3, max, 0}};/ / map
		/ / 6
		for (int k = 0; k < 6; k++)// add k nodes
		{
			for (int i = 0; i < 6; i++)// Relax I rows
			{
				for (int j = 0; j < 6; j++)// Relax the I column{ dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]); }}}/ / output
		for (int i = 0; i < 6; i++) {
			System.out.print("Node"+(i+1) +"Shortest path");
			for (int j = 0; j < 6; j++) {
				System.out.print(dist[i][j]+""); } System.out.println(); }}}Copy the code

The result is:

The figure is the same as Dijkstra in the previous article

Of course, as you learn, you can print the result of the adjacency matrix after each node is inserted to see if the first two nodes are the same as the author’s. If they are, it is correct!

You may still have doubts, so we will use a local to demonstrate the change of AB in the shortest distance. Wish you understand:

Ok, Floyd algorithm is introduced here, if it helps you, please move your hands and point a thumbs-up! Crab crab. Hope to make progress together with you! Welcome to pay attention to the author’s public account: Bigsai!