dijkstra’s algorithm in detail

Dijkstra Algorithm

The Dijkstra (Dijkstra) algorithm is a typical single-source shortest path algorithm used to compute the shortest path from one node to all other nodes. The main feature is that it cascades outward from the start point until it expands to the end point. Note that the algorithm requires that no negatively weighted edges exist in the graph.

Set G=(V,E) is a weighted directed graph, the set of vertices V in the graph is divided into two groups, the first is the set of vertices for which the shortest paths have been found (denoted by S, initially there is only one source point in S, and then every shortest path will be added to the set S until all the vertices have been added to S. The algorithm is finished), and the second is the set of vertices for which the shortest paths have not been determined (denoted by S). The second group is the set of vertices (denoted by U) for the remaining undetermined shortest paths, and the vertices of the second group are added to the set S in increasing order of the length of the shortest paths. During the joining process, it is always maintained that the shortest path length from the source point v to each vertex in S is not greater than the shortest path length from the source point v to any vertex in U . In addition, each vertex corresponds to a distance, and the distance of a vertex in S is the shortest path length from v to this vertex, and the distance of a vertex in U is the current shortest path length from v to this vertex including only the vertices in S as intermediate vertices.

(1) Initially, S contains only the starting point D; U contains all vertices except D, and the distance of the vertices in U is “the distance from the starting point D to this vertex” (e.g., if the distance of the vertex A in U is the length of [D,A], and then D and A are not neighboring, the distance of A is āˆž)

p>(2) Select the “shortest vertex K” from U and add vertex K to S; at the same time, remove vertex K from U

(3) Update the distance from each vertex in U to the starting point D. The reason for updating the distances of the vertices in U is that the distance from each vertex is the length of [D,A]. The reason for updating the distances of the vertices in U is that in the previous step, K was identified as the vertex for which the shortest path was found, and thus K can be utilized to update the distances of the other vertices to the starting point D (e.g., the distance of [D,A] may be greater than the distance of [D,K]+[K,A])

(4) Repeat steps (2) and (3) until you have iterated through all the vertices

< p>https://blog.csdn.net/yalishadaa/article/details/55827681

What is the dijkstra algorithm?

Dijkstra’s algorithm was proposed by Dutch computer scientist Dijkstra in 1959, hence the name Dijkstra’s algorithm. It is a shortest path algorithm from one vertex to each of the remaining vertices, and solves the shortest path problem in directed graphs.

The basic principle is: each time a new expansion of a point with the shortest distance, update the distance to its neighboring points. When all edge weights are positive, the distance to this point will never be changed again since there will not be an unexpanded point with a shorter distance, thus ensuring the correctness of the algorithm.

But according to this principle, the graph of Dijkstra’s shortest path must not have negatively weighted edges, because expanding to negatively weighted edges creates shorter distances, potentially destroying the property that the distances of points that have already been updated will not change.

For example, if the vertices of a graph represent cities, and the weights on the edges represent driving distances between the cities, Dijkstra’s algorithm can be used to find the shortest path between the two cities.

The input to Dijkstra’s algorithm consists of a weighted directed graph G, and a source vertex S in G. We denote the set of all vertices in G by V. Each edge in the graph is an edge in the graph. Each edge in the graph is an ordered pair of elements formed by two vertices. (u,v) means that there is a path connected from vertex u to v. We take the set of all edges of E, and the weights of the edges are defined by the weight function w:Eā†’[0,āˆž].

Thus, w(u,v) is the non-negative cost value (cost) from vertex u to vertex v. The cost of an edge can be visualized as the distance between two vertices. The cost value of a path between any two points is the sum of the cost values of all edges on that path.

Knowing that there are vertices s and t in V, Dijkstra’s algorithm can find the lowest cost path (i.e. shortest path) from s to t. This algorithm can also find the shortest path from a vertex s to any other vertex in a graph.

What is the dijkstra algorithm?

The dijkstra’s algorithm is used to solve the shortest paths from vertex v0 to the remaining vertices, the algorithm produces so shortest paths in increasing order of shortest path length.

For a graph G=(V, E), the vertices in the graph are divided into two groups: the first group S: the set of endpoints of the shortest paths that have already been solved (starting at ļ½›v0}). The second group V-S: the set of endpoints of the shortest paths that have not yet been solved (starting at all nodes of V-{v0}).

Heap optimization

Thinking

The complexity of the algorithm is n^2, we can find that if the number of edges is much smaller than n^2, which can be considered to optimize the heap of such a data structure, to take out the shortest path of the complexity of the reduction of O(1); each time to adjust the complexity of the reduction of O(elogn); e is the number of edges of the point, so complexity drops to O((m+n)logn).

Implementation

1. Add the source point to the heap and adjust the heap.

2. The top element u (i.e., the element with the smallest cost) is selected, removed from the heap, and the heap is adjusted.

3. Process the vertices adjacent to u that have not been visited and satisfy the triangle inequality

1):If the point is in the heap, update the distance and adjust the position of the element in the heap.

2):If the point is not in the heap, join the heap and update the heap.

4. If the fetched u is the end point, end the algorithm; otherwise repeat steps 2 and 3.

Graph Traversal Algorithms for Shortest Paths Dijkstra’s Algorithm

The shortest path problem is a classical algorithmic problem in the study of graph theory, aiming to find the shortest paths between two nodes or a single node to other nodes in a graph. Depending on the problem, specific forms of algorithms include:

Commonly used shortest path algorithms include Dijkstra’s algorithm, A-algorithm, Bellman-Ford’s algorithm, SPFA algorithm (an improved version of Bellman-Ford’s algorithm), Floyd-Warshall’s algorithm, Johnson’s algorithm, and the Bi- directionBFS algorithm. In this paper, we will focus on the principle as well as the implementation of Dijkstra’s algorithm.

Dijkstra’s algorithm, which translates as Dijkstra’s algorithm or Dijkstra’s algorithm, was proposed in 1956 by the Dutch computer scientist Ezhel. Dijkstra was proposed in 1956 by the Dutch computer scientist Ezhel Dijkstra to solve the single-source shortest path problem for an empowered directed graph. The so-called single-source shortest path problem is to determine the starting point and find the shortest path from that node to any node in the graph, the algorithm can be used to find the shortest path in two cities or to solve the famous traveler’s problem.

Problem description: in an undirected graph, is the set of graph nodes, is the set of edges connecting the nodes. Find the shortest path from the vertex to each of the remaining nodes (single-source shortest path), assuming the weight of each edge.

For a weighted undirected graph, the vertices in the graph are divided into two groups, and the first group is the set of vertices for which the shortest path has been found (denoted by). Initially there are only source points, when a shortest path is found, new vertices are added until all vertices are added and the algorithm ends. The second group is the set of undetermined shortest path vertices (denoted by), which decreases as the mid vertices are added.

The workflow of Dijkstra’s algorithm is demonstrated in the following figure as an example (starting with a vertex):

Note:

01) is the set of vertices for which a shortest path has been computed;

02) is the set of vertices for which a shortest path has not been computed;

03) denotes a set of vertices with a shortest distance of 3 from the vertex to the vertex is 3

Step 1: Select vertices to add in

Step 2: Select vertices to add in, shortest distance of vertices in the update

p>Step 3: Select vertices to add in and update the shortest distance from the center vertex

Step 4: Select vertices to add in and update the shortest distance from the center vertex

Step 5: Select vertices to add in, update shortest distance from mid-vertex

Step 6: Select vertices to add in, update shortest distance from mid-vertex

Step 7: Select vertices to add in, update shortest distance from mid-vertex

Example: node numbers 1-7 stand for A,B,C,D,E,F,G

(s.paths<-shortest.paths(g,), etc.). algorithm=”dijkstra”)) Output:

(s.paths<-shortest.paths(g,4,algorithm=”dijkstra”)) Output:

Example:

Find the shortest path from D(4) to G(7):

[1]Wikipedia, Shortest path problem: https://zh.wikipedia.org/wiki/%E6%9C%80%E7%9F%AD%E8%B7%AF%E9%97%AE%E9%A2%98;

[2]CSDN, Principles of Dijkstra’s algorithm: https:/ /blog.csdn.net/yalishadaa/article/details/55827681;

[3]RDocumentation:https://www.rdocumentation.org/packages/RNeo4j/ versions/1.6.4/topics/dijkstra;

[4]RDocumentation:https://www.rdocumentation.org/packages/igraph/versions/0.1.1/topics/ shortest.paths;

[5]Pypi:https://pypi.org/project/Dijkstar/