Yahoo Answers is shutting down on May 4th, 2021 (Eastern Time) and beginning April 20th, 2021 (Eastern Time) the Yahoo Answers website will be in read-only mode. There will be no changes to other Yahoo properties or services, or your Yahoo account. You can find more information about the Yahoo Answers shutdown and how to download your data on this help page.
Prim's Algorithm VS Dijkstra's Algorithm?
Hi, I am doing an assignment on different types of pathfinding. Can I use Prim's algorithm and Dijkstra's algorithm on the same graph? I have used Dijkstra's algorithm to go from the start point to the end point, but if i also want to use the prim's algorithm on the same question, how can i adjust my question? I have 7 nodes in total. Thank you so much!
- oyubirLv 61 month agoFavorite Answer
I must slightly correct husoski (whose answer is globally correct).
1a. Dijkstra algorithm DOES give shortest path from a start point to ANY other point of the graph. Not just the shortest point between 2 given points.
I know it is written otherwise on many webpage. I fail to see why.
But that is simply false. Dijkstra starts from a node S, and ends when shortest path from S to X has been computed ∀ node X.
(unless, of course, you already know what end node E you are interested in, in which case you can end the algorithm before the end, and the you, roughly, know the shortest path from S to "only" half of the nodes, on average (those closer from S than E. But that is optimization for a specific usage. And strictly speaking, is not even part of the algorithm published by Dijkstra).
1b. Btw, strictly speaking, Dijkstra algorithm does not give any path at all. Only the length of the shortest path. But with the simple addition of a pred[A]=B (that everybody add) it gives the shortest paths.
So conclusion of 1: Dijkstra and Prim, contrarily to what is indeed said on many pages, both build a tree. It is only because most people are not interested by the tree in Dijkstra case, and not interested by individual path in Prim's case, that people, wrongly claim "Dijkstra produces a path between 2 given nodes, Prim produces a tree".
Result of both is a tree.
Anyway, just look at the algorithms. They are almost exactly the same.
while ∃T, yet undealt node whose λ[T] is minimum:
for all successor U of T:
if λ[U] > f(λ[T], value of arc (T,U)):
λ[U]=f(λ[T], value of arc (T,U))
the only difference is that in Dijkstra case f(λ,v)=λ+v, while in Prim's case f(λ,v)=v
So, it is really the same kind of algorithm, with the same kind of result. But not exactly the same result, because criterion is not exactly the same.
Dijkstra produces a tree of path that are all the shortest possible path from S to X, ∀X.
Prim produces a tree of path that are not necessarily the shortest possible path from S to X. But that minimize globally the total weight of the tree.
So, conclusion is the same: Dijkstra is the answer when you are trying to find shortest path in an existing network. Prim is the answer when you are trying to build the cheapest network.
So, for example, if your problem is:
Let N₁, N₂, ..., Nₙ, n towns
Let a set of (Nᵢ, Nⱼ) be direct roads between pairs of towns.
Let v(Nᵢ, Nⱼ) the cost (length, time, need for fuel, whatever) of each road.
Find the shortest (shortest, fastest, cheapest, whatever) path from a starting town S to any arrival town X,
then Dijkstra is what you need. It gives you a tree, whose root is S, and branches are all the shortest path from S to any other town.
If your problem is:
Let N₁, N₂, ..., Nₙ, n towns, which are not connected by any roads
Let a set of (Nᵢ, Nⱼ) be estimated possible direct road, established by a study.
Let v(Nᵢ, Nⱼ) the estimated cost of the direct road between Nᵢ, Nⱼ
Find the cheapest set of roads that allows to reach any town from a starting point S.
then, Prim is what you need. It also gives you a tree. Whose root is S, and branches are path from S to any other town. But those path are not necessarily minimal. What is minimal is the cost of the tree, globally.
So, obviously, you can use Dijkstra and Prim on the same graph. Both use the exact same paradigms (nodes, edges, cost of edges), and give the same kind of result (a tree of paths from a starting point S).
But I fail to see any reason why it would be pertinent to do so.
Both algorithm have the same complexity (it is only the criterion, that I've called f above, that changes). So, it is not like one was less good but faster. Both are optimal. So it is not like one was best under a given condition and the other best under another.
It is just that they don't answer the same question.
(Note that there are some limitation, that are different. Dijkstra doesn't work with negatives valued edges. Prim does - understand by that that Dijkstra's guarantee of shortest path is no longer valid if there is negative valued edge. Dijkstra can work with oriented graph. Prim doesn't. Understand by that that Prim's guarantee to find the minimal tree is no longer valid in an oriented graph. But, please, do not conclude "then Dijkstra is for oriented graph with positive valued edge, and Prim is for unoriented graph with any value". It is not at all the criterion. Again, they don't even address the same question. Alternative to Dijkstra when there are negative valued edges is Ford -- which cost more, but will provides an optimal answer when there is one, and will be able to tell so when there is no optimal answer)
- husoskiLv 71 month ago
Those algorithms do different things. Dijkstra's algorithm finds a single path between two vertices in a connected graph. The result is only guaranteed to contain those two vertices. That will be the case when the path is "one hop".
Prim's algorithm finds a minimum spanning tree for a connected graph. That's a subgraph guaranteed to contain all vertices of the original graph (and to have the smallest possible sum of edge costs.)
You can use them on the same graph, but they answer different questions. In practical terms, Prim is more likely to be useful when building or modifying a network while Dijkstra is more likely to be useful when sending messages over an existing network. I don't see a simple question about the original network where both algorithms would be involved in finding an answer.