The difference between Prima and Dijkstra's algorithms?

Question

What is the exact difference between Dijkstra and Prima algorithms? I know that Prim will give MST, but the tree created by Dijkstra will also be MST. Then what is the difference?

Answer 1

The Prim algorithm creates a minimal spanning tree for a graph, which is a tree that connects all nodes in a graph and has the lowest total cost among all trees connecting all nodes. However, the path length between any two nodes in the MST may not be the shortest path between these two nodes in the source graph. MSTs are useful, for example, if you want to physically connect nodes on a graph in order to provide them with electricity at least the total cost. It doesn’t matter that the path length between the two nodes may not be optimal, since all you care about is the fact that they are connected.

The Dijkstra algorithm creates the shortest tree of paths starting from some source node. The shortest path tree is a tree that connects all nodes in the graph to the source text of the node and has the property that the length of any path from the source of a node to any other node in the graph is minimized. This is useful, for example, if you want to build a road network that made it as efficient as possible for everyone to get to some important important landmark. However, the shortest path tree is not guaranteed as a minimum spanning tree, and the cost of constructing such a tree can be much more than the cost of MST.

Another important difference concerns the types of graphs on which the algorithms work. The Prim algorithm works only with undirected graphs, since the MST concept assumes that graphs are inherently non-oriented. (For directed graphs, there is something called a "minimal spanning arborescence", but the algorithms for finding them are much more complicated). Dijkstra's algorithm works fine on directed graphs, since the shortest paths of trees can really be directed. In addition, Dijkstra’s algorithm does not necessarily provide the correct solution in graphs containing negative boundary weights , while the Prim algorithm can handle this.

Hope this helps!

Answer 2

Dijkstra's algorithm does not create MST, it finds the shortest path.

Consider this chart

5 5 s *-----*-----* t \ / ------- 9 

The shortest path is 9, and the MST is another “path” at 10.

Answer 3

The algorithm of Prima and Dijkstra is almost the same, except for the "relaxation function".

In Prim:

 MST-PRIM (G, w, r) { for each key ∈ GV u.key = ∞ u.parent = NIL r.key = 0 Q = GV while (Q ≠ ø) u = Extract-Min(Q) for each v ∈ G.Adj[u] if (v ∈ Q) and w(u,v) < v.key v.parent = u v.key = w(u,v) <== relax function, Pay attention here } 

In Dijkstra:

 Dijkstra (G, w, r) { for each key ∈ GV u.key = ∞ u.parent = NIL r.key = 0 Q = GV while (Q ≠ ø) u = Extract-Min(Q) for each v ∈ G.Adj[u] if (v ∈ Q) and w(u,v) < v.key v.parent = u v.key = w(u,v) + u.key <== relax function, Pay attention here } 

The only difference is the last line of code, which is a relaxation function. Prim, who is looking for a minimal spanning tree, only cares that the minimum of all edges covers all the vertices. therefore, it looks like this: v.key = w (u, v) Dijkstra, which searches for the minimum path length, so it takes care of edge accumulation. It looks like this: v.key = w (u, v) + u.key

Answer 4

Dijkstra finds the shortest path between it, starting with node and all the other nodes. Therefore, in return, you get the minimum distance from the beginning of the node, that is, you can use any other node as efficiently as possible.

The Prims algorithm gives you MST for a given graph, that is, a tree that connects all nodes, while the sum of all costs is minimal.

To make the story short with a realistic example:

• Dijkstra wants to know the shortest route to each destination, saving travel time and fuel.
• Prim wants to know how to effectively deploy a train system, i.e. save material costs.

Answer 5

Directly from the Dijkstra Algorithm's Wikipedia article:

The process that underlies Dijkstra's algorithm is similar to the greedy process used in Prim's algorithm. Prim's goal is to find the smallest spanning tree that connects all nodes in the graph; Dijkstra deals with only two nodes. Prim does not evaluate the total weight of the path from the starting node, only a separate path.

Answer 6

The key difference between the main algorithms is their different edge selection criteria. Typically, they use a priority queue to select the following nodes, but have different criteria for selecting neighboring nodes of the current processing nodes: Prim Algorithm requires that the following neighboring nodes are also in the queue, and Dijkstra Algorithm:

 def dijkstra(g, s): q <- make_priority_queue(VERTEX.distance) for each vertex v in g.vertex: v.distance <- infinite v.predecessor ~> nil q.add(v) s.distance <- 0 while not q.is_empty: u <- q.extract_min() for each adjacent vertex v of u: ... def prim(g, s): q <- make_priority_queue(VERTEX.distance) for each vertex v in g.vertex: v.distance <- infinite v.predecessor ~> nil q.add(v) s.distance <- 0 while not q.is_empty: u <- q.extract_min() for each adjacent vertex v of u: if v in q and weight(u, v) < v.distance:// <-------selection-------- ... 

Computing vertex.distance is the second point.

Answer 7

@templatetypedef covers the difference between MST and the shortest path. I examined the difference in the algorithm for another answer , demonstrating that both options can be implemented using the same universal algorithm, which takes another parameter: function f(u,v) . The difference between the Prim and Dijkstra algorithm is that you use f(u,v) .

Answer 8

At the code level, another difference is the API.

You initialize Prim with the original vertex s, i.e. Prim.new(s) ; s can be any vertex, and regardless of s, the end result, which is the edges of a minimal spanning tree (MST), is the same. To get the edges of the MST, we call the edges() method.

You initialize Dijkstra with the original vertex s, i.e. Dijkstra.new(s) that you want to get the shortest path / distance to all other peaks. The final results, which are the shortest path / distance from s to all other vertices; vary with s. To get the shortest paths / distances from s to any vertex v, we will call the methods distanceTo(v) and pathTo(v) respectively.

Answer 9

The first difference is that the Dijkstrass algorithm solves a different problem than Kruskal and Prim. Dijkstra solves the shortest path problem (from the specified node), while Kruskal and Prim find the minimum cost. The following is a modified form of the description that I wrote on this page: Graphic Algorithms.

For any graph, a spanning tree is a set of edges sufficient to provide exactly one path between each pair of vertices. This limitation means that there can be no chains formed by selected edges.

A minimum cost tree is one that has the smallest total weight possible (where weight is cost or distance). There may be more than one such tree, but Prim and Kruskal are guaranteed to find one of them.

For the indicated vertex (for example, X), the shortest path tree is a spanning tree, so the path from X to any other vertex is as short as possible (i.e., has the minimum possible weight).

Prim and Dijkstra "grow" a tree from the starting peak. In other words, they have a "local" focus; at each step, we consider only those faces that are adjacent to the previously selected vertices, choosing the cheapest option that satisfies our needs. Meanwhile, Kruskal is a "global" algorithm, which means that each edge (greedily) is selected from the entire graph. (In fact, Dijkstra can be seen as having some global aspect, as indicated below.)

To find a tree with the lowest cost:

Kruskal (global approach): at every step, select the cheapest available edge anywhere that does not violate the goal of creating a spanning tree. Prim (local approach): select the starting vertex. In each subsequent step, select the cheapest available edge attached to any previously selected vertex that does not violate the goal of creating a spanning tree. To find the shortest spanning tree:

Dijkstra: At each step, select the edge attached to any previously selected vertex (local aspect), which makes as little as possible the total distance from the initial vertex (global aspect) and does not violate the goal of creating a spanning tree.

Low cost trees and shortest path trees are easily confused, as are the Prim and Dijkstra algorithms that solve them. Both algorithms "grow" from the initial vertex, at each step, select an edge that connects the vertex Y, which is in the tree, to the vertex Z, which is not there. However, while Prim chooses the cheapest such edge, Dijkstra chooses an edge that leads to the shortest path from X to Z.

A simple illustration helps to understand the difference between these algorithms and the trees that they produce. In the graph below, starting at vertex A, both Prim and Dijkstra begin by selecting the edge AB, and then adding the edge BD. Two algorithms diverge here: Prim completes the tree by adding a DC edge, and Dijkstra adds AC or BC, because the AC and ABC paths (both with a total distance of 30) are shorter than the ABDC path (a total distance of 31).

Answer 10

Dijkstrass algorithm is used only to find the shortest path.

In the Minimum Spanning Tree (Prim or Kruskal algorithm) you get the minimum values ​​with the minimum edge value.

For example: - consider a situation where you will not create a huge network for which u will require a large number of wires, so this wire counting can be performed using the Minimum spanning tree (Prim or Kruskal algorithm) (i.e. it will give you the minimum number wires to create a huge wired network connection at minimal cost).

While the "Dijkstra's algorithm" will be used to get the shortest path between two nodes when connecting any nodes to each other.