hello everyone,

i am looking here for some answers related to algorithms on graph traversals ......
my first question would be

what differentiates Dijkstra's algorithm from prim's algorithm .
i know that prim is for undirected graph and dijkstra for directed but is the time complexity of prim lesser than dijkstra?
and another point would be if I start finding the Minimum Spanning tree using Dijkstra's algorithm from different vertices will i still get the same minimum spanning tree??? because it is for directed graph.

Question 2 would be does anybody know what is DHEA algorithm I tried searching for it online but could not find it . any links or text you can suggest to me .

Question 3 there is another algorithm which is called as Prim-Dijkstra's algorithm which is a kind of mix of both the algorithms . can you explain me how the parallelized version of this algorithm works .
yoo and deo tried to parallelize it and said that it needs synchroniztion and contention between the processes to select the next non tree vertex .
it would be nice if somebody can explain me the mechanism by reading these lines.

"Each processor updates the distance of 1/pth of the nontree vertices , then contends with the other members for the access to a global variable which contains the nearest nontree vertex. "
research paper was ...."algorithms for finding the minimum spanning tree " by n.deo and y.b yoo

regards
smith

Dijkstra's algorithm and Prim's (or Prim-Jarnik's) algorithm doesnt even solve the same kind of problem. Prim's finds a MST for an undirected graph and Dijkstra's find the shortest path tree for a graph with nonnegative edges, which also is a spanning tree but not (likely) the minimum one.

There are algorithms for finding MST for directed graphs. Google it!

Finally, implementation wise Dijkstra's and Prim's are very much alike and therefore have the same time complexity.

This post has been edited by LaFayette: 19 Aug, 2009 - 01:31 AM

http://www.informaworld.com/smpp/content~d...tent=a713711909

I think this includes the DHEA algorithm you were asking about. I personally have never heard of it but it seems to be some sort of Parallel Algorithm for solving MST problems with DFS (Depth First Search) methods


EDIT: I apologize because that link up there will take you to a site where you have to register and pay for articles...unfortunately I have only found sites that require you to buy the article in order to read it. But from what I can gather it is a Parallel Algorithm for solving MST problems with undirected graphs. Specifically it was used in an article [cited below] to approximate the Prize Collecting Steiner Tree Problem a known NP-Complete problem


[citation from earlier] I. Ljubi´c, R. Weiskircher, U. Pferschy, G. Klau, P. Mutzel, and M. Fischetti.
An algorithmic framework for the exact solution of the prize-collecting Steiner tree problem.
Mathematical Programming, Series B, 105(2-3):427-449, 2006.


If you google that, it's another article you have to pay for... :\ if you're in school, i'd suggest going to your schools library and looking it up, or heck, if youre at school, why not ask your CS prof. If he/she knows about it, it'd probably impress the hell out of them that you're asking about it

This post has been edited by mattman059: 19 Aug, 2009 - 04:29 AM

Dijkstra-Prim

That link has a snippet from a book that contains a pseudocode version of Dijkstra-Prim's Parallel algorithm...Unfortunately every article I find must be purchased...which is why i suggested going to your library...However, seeing as this seems to be a popular topic, you could get a subscription to the ACM and become a student(or professional) member and get access to the ACM library...I've seen a lot of articles about this topic in there. But like i said before, you have to either be a member or pay for each article (~$35 USD)