A small order

Recently, I was reading the book “Algorithm Diagram”, and I had a lot of feelings about the chapter “Dikstra algorithm”.

Dikstra algorithm is a very famous algorithm, which is one of the top ten algorithms to change the world. It is used to solve the single source shortest path problem of [weighting] [directed acyclic graph].

Without this algorithm, the Internet would not be as efficient as it is today. This algorithm can be used to find the shortest distance between two nodes in the graph for any problem that can be represented by the graph model. The stability of Dikstra’s algorithm cannot be replaced.

Note: The original version of Dikstra’s algorithm was only suitable for finding the shortest path between two vertices; later, more common variants fix a vertex as the source node and then find the shortest path from that vertex to all other nodes in the graph, producing a shortest path tree (a tree is a graph without a loop). This article deals with the latter.

define

If you find it difficult to understand the meaning of the sentence marked bold in red in the preface? Let’s break them down, and you’ll see. Optionally skip this section if you know the concept.

What is a figure

  • The graph is composed of nodes and edges to simulate the connection between different things.

FIG. 1-1

We find that too many of our realistic scenes are related to structures like diagrams. The relationships between people, places and places, topologies, etc. Specific scenarios will be presented later.

What is a directed acyclic graph

What is direction?

FIG. 1-1 is an undirected graph, while FIG. 1-2 is a directed graph. The difference is that the latter marks the direction of the association between points.

Figure 1-2

What is acyclic?

A directed acyclic graph is a directed acyclic graph if it starts from any vertex and cannot go through several edges to return to the point.

  • Q&A

Q: Is FIG. 1-2 directed acyclic?

A: No, because A goes through C and then goes back to A.

Figure 1-3

Is figure 1-3 directed acyclic?

A: Yes, to learn more about directed acyclic graphs at zh.wikipedia.org/wiki/.

What is empowerment

Here, “weight” refers to “weight”, and “weight” refers to the weight value given to the edges of the graph.

Figure 1-4

For example, as shown in Figure 1-4, it takes 10 steps to go from point 1 to point 2, and 100 steps to go from point 1 to point 5. Here, 10 and 100 are the “weight value”.

Special note: Dijkstra algorithm edge weight is non-negative.

What is a single source shortest path

The shortest path is the path that calculates the shortest (minimum weight) between two given nodes. If the starting point is determined, it is called the single-source shortest path.

Shortest paths have many real-world applications: many maps that offer navigation use the shortest path algorithm or its variants. When we look at someone’s profile on a lot of social platforms, they show you how many friends you have in common and list the relationships, and it’s based on this algorithm.

We are now looking back at this definition:

Dikstra algorithm is used to solve the single source shortest path problem of weighted directed acyclic graphs.

Do you understand? Only three key words, “empowerment”, “directed acyclic graph” and “single-source shortest path”, are needed. To be very crude, this algorithm is designed to find the shortest distance between two points.

implementation

So the point is, how does the Dikstra algorithm work?

Go back to algorithm Diagrams for the most intuitive example.

Figure 2-1

In Figure 2-1, what is the shortest path from the beginning to the end?

If you used breadth-first search (BFS), the answer would be 7 (implementation, press no table), but this is clearly not the optimal solution. We can see with our human eyes that the correct answer is 6, from the beginning — to point B — to point A — to the end.

If you use a computer, how does the correct answer come out? It’s our hero, the Dikstra algorithm.

Four steps

The Dikstra algorithm includes four steps:

  1. Find out the “cheapest” node, the node that can be reached in the shortest time.
  2. The cost of updating this node’s neighbors, the meaning of which is described later.
  3. Repeat this process until you have done this for each node in the diagram.
  4. Calculate the final path.
  • Step 1: Find the “cheapest” node

Let’s look at the first step, you start, you have two ways to go, 6 steps to A, 2 steps to B, forget about the other nodes, point B is the cheapest node to record the following set. This is very important.

Figure 2-2Figure 2-3

  • Step 2: Calculate the time it takes to travel through node B to each neighbor.

It takes 5 steps from the starting point to point B to A, 7 steps from the starting point to point B to the end. In the previous set, it takes 6 steps from the starting point to point A, and positive infinity to the end point. Now there is A better solution, it needs to update the overhead set, and figure 2-4 is obtained.

Figure 2-3Figure 2-4

  • Step 3: Repeat!!

How to repeat? We have already done the update based on point B, and we need to do the same for the remaining nodes. In Table 2-4, besides B, point A has the least overhead, so we need to operate on point A. Update the cost of all neighbors on node A.

It takes 1 step from the starting point to the end point through A, 5 + 1 = 6, which is less than the required cost of the end point in Figure 2-4, 7. We should update the cost set.

Figure 2-5

We use the Dikstra algorithm for each node (no need to do this for the endpoint), so Figure 2-5 is the final set of overhead and the final optimal solution. From start to finish in at least 6 steps!

  • The fourth step?

Careful friends may find, said good four steps? Why are there only three steps up here? Here the author left a “scheming”, in fact, the above example only calculated the value of the minimum cost, did not get the final path to achieve the minimum cost, that is, the lack of a backtracking process.

How to calculate the final path? Here’s another example, and it’s a little more complicated. However, Bengua believes that the core of Dikstra’s algorithm lies in the second step and the third step (the update of the overhead array), and the fourth step is only to add a parent-child relationship for backtracking.

Figure 2-6

Figure 2-6. Q: What is the shortest path from the score to the piano?

The answer is: sheet music – record – drum set – piano, do you know the specific updating process of the overhead set? I think some of you have met this question in an interview. To learn more

Start from the point [music], next to the two points [record] and [poster], and put them in the overhead array with the values 0 and 5, respectively. 0 is less than 5, so based on [poster], proceed to step 2 and get [score] through [poster] to its adjacent points, which are [guitar] 30 and [Drum] 35. At this point, there are four values in the overhead array:

The name of the overhead
posters 0 (adjacent values have been traversed)
The record 5
The guitar 30
drums 35
. .

5<30<35, repeat the operation, based on [record], get [score] to its adjacent point value. For [guitar] 20, [drum] 25, both less than the cost array value, update. The overhead array is:

The name of the overhead
posters 0 (adjacent values have been traversed)
The record 5 (adjacent values have been traversed)
The guitar 20
drums 25
. .

Continue to iterate, 20 < 25, this time should be based on [guitar], [guitar] connected to the piano, [sheet music] through [record] to [guitar] to piano, 40, update the array. 25 < 40, based on the drum kit traversal, the drum kit is also only connected to the piano, music, — record, — drum, — piano, value 35,35 is less than 40, update. Finally, only the piano point is not traversed, and the piano is the end point, then the execution is over. In the end is:

The name of the overhead
posters 0 (adjacent values have been traversed)
The record 5 (adjacent values have been traversed)
The guitar 20 (adjacent values traversed)
drums 25 (adjacent values traversed)
The piano 35 (End point, no traversal)

If you can easily go through it, the idea of the algorithm is fine

In fact, the shortest path does not have to be physical distance, but can also be translated into other measures, such as money, time, and so on. Abstract the scene in life into this kind of algorithm problem, my mother no longer need to worry about me detour ~

Dickstra! Cattle!

To the author of this algorithm, Edsger Wybe Dijkstra, who won the Turing Award in 1972.

code

Algorithmic ideas are important, but TALK IS CHEAP!! I’m going to do py here. Finding the Shortest Path in Javascript: Dijkstra’s Algorithm / (ㄒ o ㄒ) / ~ ~

Node = find_lowest_cost_node(costs) // Find the least expensive node among the unworked nodes while node is not None: Cost = costs[node] Neighbors = graph[node] for n in neighbors.keys(): New_cost = cost + neighbors[n] if costs[n] > new_cost: // If the current node is closer to the neighbor, Costs [n] = new_cost parents[n] = node // Set the parent of the neighbor to the current node. append(node) // Mark the current node as processed node = Def find_lowest_cost_node(costs) def find_lowest_cost_node(costs): lowest_cost = float("inf") lowest_cost_node = None for node in costs: Cost = costs[node] if cost < lowest_cost and node not in processed:// If the current node is less expensive and unprocessed, Lowest_cost = cost // Treats it as the node with the lowest cost. Lowest_cost_node = node return lowest_cost_nodeCopy the code

The costs array is called the cost array, and you can get the minimum cost, the shortest path.

Interested in Peking University professor Qu Wanling’s video – “single source shortest path problem and algorithm”, very clear.

myth

A beautiful mind

The Dikstra algorithm is actually a greedy algorithm. Because the algorithm always tries to access the next node closest to the starting point in each step of the loop first.

Bengua was recently watching a movie, a Beautiful Mind, which deepened his understanding of the Nash equilibrium.

In game theory, the Nash equilibrium ( Nash equilibrium refers to a non-cooperative game involving two or more players in which each player is assumed to know the equilibrium strategy of the other player. A conceptual solution where no participant can benefit himself by changing his strategy. “– Wikipedia

In the course of a game, no matter how the other party chooses the strategy, one party will choose a certain strategy, then this strategy is called the dominant strategy. The combination is defined as a Nash equilibrium if any player chooses the optimal strategy when the strategies of all other players are determined. — Baidu Encyclopedia

The combination of the two leads to a puzzle:

In this Dikstra algorithm, every move we make is a game. If each step of the game to different people to do, have reached their own optimal solution, then the final solution must be optimal…… ? It involves the stability of the algorithm, right? Or is it confusing, or is it a little philosophical? Anyway, this is an interesting thing. Algorithms, game theory, optimal solutions……

Concept of finishing

  • Graph algorithm

“The graph algorithm is probably the most useful algorithm I know.” — Aditya Bhargava, author of Algorithm Diagram

Graph algorithm has three kinds of core: path search, centrality computing and community discovery.

Graph algorithm also has the most basic two traversal algorithm:

  1. Breadth First Search (BFS)
  2. Depth first Search (DFS)

Have learned “data structure” should not be unfamiliar. At the same time, BFS can be compared with dikstra algorithm, which can be used to find the shortest path in unweighted graphs, and the latter in weighted graphs. Also, if the weight of the graph is negative, use the behrman-Ford algorithm. Interested in expanding ⑧.

tool

  • Dijkstra’s Algorithm Solver (drawing) : mdahshan. Making the IO/Dijkstra

The above

Writing is not easy and needs encouragement. Young people, talk about some martial arts ~ like on the thumbs up, dislike on the three. Thank you ~

I’m Carmelo Anthony of the Nuggets, a continuous output of personal webmaster ~