Network Security Internet Technology Development Database Servers Mobile Phone Android Software Apple Software Computer Software News IT Information

In addition to Weibo, there is also WeChat

Please pay attention

WeChat public account

Shulou

What is the difference between Dijkstra algorithm and Prim algorithm

2025-01-18 Update From: SLTechnology News&Howtos shulou NAV: SLTechnology News&Howtos > Development >

Share

Shulou(Shulou.com)06/03 Report--

This article is to share with you about the difference between Dijkstra algorithm and Prim algorithm. The editor thinks it is very practical, so share it with you as a reference and follow the editor to have a look.

Brief introduction of Dijkstra

The Dijkstra algorithm is used to construct the shortest path tree (MST) of a single source-that is, the distance from one point in the tree to any other point is the shortest. For example, when building a map application, find the shortest distance from your coordinates to a landmark. Can be used for directed graphs, but there can be no negative weights (Bellman-Ford can handle negative weights).

Pseudo code

Dijkstra () {for each u in u.parent V {/ / initialize here, assign a key value + ∞ to each node u, and set empty parent node u.key = + ∞ u.parent = NULL} / / choose the initial point rMagneQ is the weight priority queue of all vertices in the undirected graph G. Key can be regarded as the distance from the source point to u r.key = 0 Q = G V while (Q! = ∅) {/ / take out the vertex u = extractMin (Q) / / all nodes connected by vertex u (i.e. the u th linked list in the adjacency list of undirected graph G) for each v ∈ G.Adj [u] {if (v ∈ Q) and (w (u) V) < key) {/ / if the node is still in Q and the weight w (w < v) is less than its original weight Then relax! Brief introduction of v.parent = u v.key = w (u, v) + u.key}} Prim

The Prim algorithm is used to build a minimum spanning tree, that is, the minimum sum of the weights of all edges in the tree. For example, build a circuit board to minimize all edges and costs. Can only be used for undirected graphs.

Pseudo code

/ / undirected graph G, weight w, starting point rMST (G, w, r) {for each u in GForce V {/ / initialize here, assign a key value + ∞ to each node u, and set empty parent node u.key = + ∞ u.parent = NULL} / / choose the initial point rQuery Q is the weight priority queue of all points in the undirected graph G. Key can be regarded as the distance from u to the next node v r.key = 0 Q = G V while (Q! = ∅) {/ / take out the vertex u = extractMin (Q) / / all nodes connected by vertex u (i.e. the u th linked list in the adjacency list of undirected graph G) for each v ∈ G.Adj [u] {if (v ∈ Q) and (w (u) V) < key) {/ / if the node is still in Q and the weight w (w < v) is less than its original weight Then relax! V.parent = u v.key = w (u, v)}} different

The distance between any two points of AB in MST is not shorter than that of AB in the original graph, that is, there may be an edge E (AMagi B) in the original graph that is smaller than that in * * MST.

Note that the only difference between the two pseudo-algorithms is the relaxation operation in the final loop.

The minimum spanning tree only cares about the sum of all edges, so there is v.key = w (u, v), that is, the minimum value of each point directly connected to other points (only the sum of weights between two nodes at most).

The shortest path tree only searches for the least weight, so there is v.key = w (u, v) + u.key, that is, the minimum value from each point to the other (at least the sum of weights between two nodes).

To sum up, the relaxation operation of Dijkstra adds the distance to the starting point, while Prim has only the weights of neighboring nodes.

The same thought

Greed and linear programming are used, and each step is to choose the edge with the least weight / cost.

Greed: a local optimal solution and a global optimal solution

Linear programming: the main problem contains n sub-problems, and there are overlapping sub-problems.

Dijkstra algorithm caches the solution of the optimal subpath through linear programming, and each step uses greedy algorithm to select the smallest edge.

Prim algorithm selects the smallest edge through greed, and each subtree of Prim is the minimum spanning tree, which satisfies two conditions of linear programming.

Time complexity

Time = θ (V * T1 + E * T2)

Where T1 is the time to take out the minimum key value, and T2 is the time to reduce the key value, depending on the data structure.

Array

T1 = O (V), T2 = O (1), TIME = O (V * V + E) = O (V * V)

Binary reactor

T1 = O (lgV), T2 = O (lgV), TIME = O (V * lgV + E * lgV)

Fibonacci reactor

T1 = O (lgV), T2 = O (1), TIME = O (V * lgV + E) = O (V * lgV)

For sparse graphs, E is much less than V, so binary heap is better.

For dense graphs, E=V*V, so arrays are better.

The Fibonacci pile is the best-case scenario.

Dijkstra special case

When the weights of edges are all 1, DFS (breadth-first search) can be used to optimize the time complexity.

Using FIFO (first in first out) queue instead of priority queue, the operation of lowering key T2 is optimized to O (1).

The relax operation is changed to

If d [v] = + ∞ {d [v] = d [u] + 1 enqueue (Q, v)}

The time of taking out the minimum point of key value T1 = O (1) is optimized.

Total time complexity

TIME = V + E Thank you for your reading! This is the end of this article on "what's the difference between Dijkstra algorithm and Prim algorithm". I hope the above content can be of some help to you, so that you can learn more knowledge. if you think the article is good, you can share it out for more people to see!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.

Views: 205

*The comments in the above article only represent the author's personal views and do not represent the views and positions of this website. If you have more insights, please feel free to contribute and share.

Share To

Development

Wechat

© 2024 shulou.com SLNews company. All rights reserved.

12
Report