Differences between Dijkastra and Prim

  • Thread starter Thread starter rootX
  • Start date Start date
AI Thread Summary
Dijkstra's algorithm and Prim's algorithm serve different purposes in graph theory, leading to potential discrepancies in their results. Dijkstra's algorithm finds the shortest path between two nodes, while Prim's algorithm constructs a minimum spanning tree (MST) that connects all nodes with the minimum total edge weight. In scenarios where multiple paths exist between two nodes, the paths identified by the two algorithms can differ. For instance, in a given undirected graph with edges A-B, B-C, C-D, and A-D, the shortest path from A to D is a direct edge with a cost of 4, while the MST formed by Prim's algorithm would include edges A-B, B-C, and C-D, resulting in a total weight of 6. This illustrates that the minimum spanning tree does not necessarily provide the shortest path between two specific nodes, confirming that the results from Dijkstra and Prim can indeed differ.
rootX
Messages
478
Reaction score
4
I understand both algorithms. But, I was wondering would there be a case where results between Dijkstra and Prim are different? I haven't found an example where this happens.
i.e. Would the path between A and B provided by the minimum spanning tree be always equal to the minimum distance between A and B from Dijkstra?
 
Technology news on Phys.org
If there are two minimum paths, the results could be different using the two different methods. Obviously, if there is only one minimum path with no alternative having the same total weight, they would be identical paths.
 
Nop, the Prim's algorithm only gives the set with minimum weight of edges connecting all nodes.

Imagine this undirected graph:

A-B weight 2
B-C " 2
C-D " 2
A-D " 4

The shortest path from A to D is using the direct edge with cost 4, while the spawning tree uses the other edges (total sum 6)
 
Thread 'Is this public key encryption?'

Thread 'Is this public key encryption?'

I've tried to intuit public key encryption but never quite managed. But this seems to wrap it up in a bow. This seems to be a very elegant way of transmitting a message publicly that only the sender and receiver can decipher. Is this how PKE works? No, it cant be. In the above case, the requester knows the target's "secret" key - because they have his ID, and therefore knows his birthdate.
View full post »
Thread 'Project Documentation'

Thread 'Project Documentation'

Trying to package up a small bank account manager project that I have been tempering on for a while. One that is certainly worth something to me. Although I have created methods to whip up quick documents with all fields and properties. I would like something better to reference in order to express the mechanical functions. It is unclear to me about any standardized format for code documentation that exists. I have tried object orientated diagrams with shapes to try and express the...
View full post »

Similar threads

MHB Prim's algorithm-Minimum Spanning Tree
Replies
8
Views
2K
Challenge: Find the minimum amount of draws possible for a list of integers
Replies
9
Views
2K
Djikstra's algorithm with distance 1 between every node
Replies
4
Views
1K
How to calculate Tension for a series of connected points?
Replies
8
Views
2K
MHB Dynamic programming: which recurrence relation do we use?
Replies
2
Views
2K
MHB Applying Dijkstra Algorithm: Solving a Problem
Replies
6
Views
2K
Collisions Between Two Bodies Undergoing Multiple Transformations
Replies
21
Views
4K
MHB Representation of signed integers of base B
Replies
17
Views
2K
Difference between interpreted and compiled files....
Replies
29
Views
3K
MHB What is the difference between GET vs POST vs PUT? Mainly POST vs PUT?
Replies
1
Views
1K

Hot Threads

Recent Insights

Back
Top