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 'Who is responsible for the software when AI takes over programming?'

I tried a web search "the loss of programming ", and found an article saying that all aspects of writing, developing, and testing software programs will one day all be handled through artificial intelligence. One must wonder then, who is responsible. WHO is responsible for any problems, bugs, deficiencies, or whatever malfunctions which the programs make their users endure? Things may work wrong however the "wrong" happens. AI needs to fix the problems for the users. Any way to...
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