Dijkstra's algorithm and our perishable world
I was always pleased to notice the usual physical phenomena in several abstract things, such as algorithms and other mathematics. In this article we will look at one of the possible ways for a lightning to search for its optimal path.
To begin with, we recall many well-known SleepSort. This is a sorting algorithm for numbers, but it is very different from “traditional” sorts, such as QuickSort or MergeSort. The algorithm works like this: let's set a proportional delay to each number, then we will start a thread for each number that will wait for the allotted time, and then output its own number. It is easy to understand that the numbers will be sorted in ascending order. I am very amused by this sorting, since it uses time as a comparator, moving only forward (in our model, in any case).
And let's remember the Dijkstra algorithm. Many people know what it is, but still: it is an algorithm for finding minimal paths in a graph with positive edge weights. Let A be the set of vertices from which we want to search for a distance. The result of the algorithm will be the minimum distance from this set to each vertex and an indication of the ancestor in the minimum way.
The algorithm is simple:
It is easy to prove that the answers constructed in this way will be correct.
')
And what will happen if we look for the nearest top to the beginning with the help of SleepSort? You can imagine it this way: let's put in "water spreading along a graph" such that it passes an edge in time proportional to its weight. We will “spill” it from the set A. Then the time from “launching water” to reaching a certain vertex (from among the set of sortable vertices, but only it can reach them) will be just the sum of the time to reach the previous one and the edge passage time - this is the characteristic by which we want to sort the vertices at the Dijkstra algorithm step (this is SleepSort: "water reached" this is “sleep (prev + edge); water reach;”).
Obviously, the "water going further" will perform the next iteration of the algorithm: it again searches for the nearest vertex from the neighborhood of already filled vertices. And the path found to any vertex will be formally found using the Dijkstra algorithm.
Thus, it becomes clear that Dijkstra’s algorithm is "physical to the bone".
In my humble opinion, such things as discharge (lightning) look for their way in exactly this way, that is, by the Dijkstra + forward time algorithm.
I hope this thought seemed interesting to knowledgeable people, and for beginners it helped to more clearly present the work of the algorithm.
To begin with, we recall many well-known SleepSort. This is a sorting algorithm for numbers, but it is very different from “traditional” sorts, such as QuickSort or MergeSort. The algorithm works like this: let's set a proportional delay to each number, then we will start a thread for each number that will wait for the allotted time, and then output its own number. It is easy to understand that the numbers will be sorted in ascending order. I am very amused by this sorting, since it uses time as a comparator, moving only forward (in our model, in any case).
And let's remember the Dijkstra algorithm. Many people know what it is, but still: it is an algorithm for finding minimal paths in a graph with positive edge weights. Let A be the set of vertices from which we want to search for a distance. The result of the algorithm will be the minimum distance from this set to each vertex and an indication of the ancestor in the minimum way.
The algorithm is simple:
- for set A, the answer is clear (it is zero, for obvious reasons);
- getting an answer for one more vertex: let's look for the vertex nearest to the beginning from the vertices adjacent to the set, the answer for which is clear, and remember the answer for it. For them, the distance is easy to find: it is the sum of the value of the genitive vertex and the weight of the connecting edge. This is implemented simply by keeping the minimum relevant for each iteration.
It is easy to prove that the answers constructed in this way will be correct.
')
And what will happen if we look for the nearest top to the beginning with the help of SleepSort? You can imagine it this way: let's put in "water spreading along a graph" such that it passes an edge in time proportional to its weight. We will “spill” it from the set A. Then the time from “launching water” to reaching a certain vertex (from among the set of sortable vertices, but only it can reach them) will be just the sum of the time to reach the previous one and the edge passage time - this is the characteristic by which we want to sort the vertices at the Dijkstra algorithm step (this is SleepSort: "water reached" this is “sleep (prev + edge); water reach;”).
Obviously, the "water going further" will perform the next iteration of the algorithm: it again searches for the nearest vertex from the neighborhood of already filled vertices. And the path found to any vertex will be formally found using the Dijkstra algorithm.
Thus, it becomes clear that Dijkstra’s algorithm is "physical to the bone".
In my humble opinion, such things as discharge (lightning) look for their way in exactly this way, that is, by the Dijkstra + forward time algorithm.
Some explanation of why lightning travels the path of least resistance.
Maybe someone can fix it, but I understand it this way: the leading charges will spread as in a normal inhomogeneous conductor, which means that the “current” of the leading charges along the path of minimum resistance will be maximum (if you imagine how very large number of parallel wires are in the vicinity of each point, this result is displayed from the course of school physics), and therefore will not be zero, which means that further on this place will be discharge.
I hope this thought seemed interesting to knowledgeable people, and for beginners it helped to more clearly present the work of the algorithm.
Source: https://habr.com/ru/post/265443/
All Articles