Prev: Simhydraulics
Next: parallel quicksort
From: Khalid Rumman on 7 Apr 2010 20:35
hi
I'm a beginner at MATLAB, and i need to write a MATLAB code that is a part of my project to implement a parallel sort algorithm using "Johnson's sequential single-source shortest paths algorithm".
Johnson's algorithm uses a priority queue Q to store the value l[v] for each vertex v (V - VT). The priority queue is constructed so that the vertex with the smallest value in l is always at the front of the queue. A common way to implement a priority queue is as a binary min-heap. A binary min-heap allows us to update the value l[v] for each vertex v in time O (log n).
This is the Johnson's algorithm:
procedure JOHNSON_SINGLE_SOURCE_SP(V, E, s)
2. begin
3. Q := V ;
4. for all v Q do
5. l[v] := ;
6. l[s] := 0;
7. while Q 0 do
8. begin
9. u := extract min( Q);
10. for each v Adj [u] do
11. if v Q and l[u] + w(u, v) < l[v] then
12. l[v] := l[u] + w(u, v);
13. endwhile
14. end JOHNSON_SINGLE_SOURCE_SP

Initially, for each vertex v other than the source, it inserts l[v] = in the priority queue. For the source vertex s it inserts l[s] = 0. At each step of the algorithm, the vertex u (V - VT) with the minimum value in l is removed from the priority queue. The adjacency list for u is traversed, and for each edge (u, v) the distance l[v] to vertex v is updated in the heap. Updating vertices in the heap dominates the overall run time of the algorithm. The total number of updates is equal to the number of edges


Pleas can any one help me to implement this algorithm in MATLAB to do PARALLEL SORT, or at least the algorithm it self.
thanks
From: Walter Roberson on 7 Apr 2010 20:50
Khalid Rumman wrote:

> This is the Johnson's algorithm:
> procedure JOHNSON_SINGLE_SOURCE_SP(V, E, s) 2. begin 3. Q := V ;
> 4. for all v Q do 5. l[v] := ; 6. l[s] := 0; 7.
> while Q 0 do 8. begin 9. u := extract min( Q); 10.
> for each v Adj [u] do 11. if v Q and l[u] + w(u, v) < l[v]
> then 12. l[v] := l[u] + w(u, v); 13. endwhile 14. end
> JOHNSON_SINGLE_SOURCE_SP

I do not recognize the source language. It looks sort of like Pascal, but
Pascal would have required declaring local variables such as Q.

Your copy of the source appears to be missing some characters, such as in line
4, "for all v Q do" appears to be missing an operator between v and Q. Also,
the operations "extract" and Adj do not have an obvious definition... indeed,
Adj looks to be more like an array, but it would have to be a global array
since it is not passed in and it is not calculated in the routine.
From: Khalid Rumman on 7 Apr 2010 21:09
Walter Roberson wrote
> I do not recognize the source language. It looks sort of like Pascal, but
> Pascal would have required declaring local variables such as Q.

The above is the pseudo code of Johnson&#8217;s algorithm
From: Walter Roberson on 7 Apr 2010 21:55
Khalid Rumman wrote:
> Walter Roberson wrote
>> I do not recognize the source language. It looks sort of like Pascal,
>> but Pascal would have required declaring local variables such as Q.
>
> The above is the pseudo code of Johnson&#8217;s algorithm

No it wasn't. The pseudo code can be found at
http://parallelcomp.atw.hu/ch10lev1sec7.html

Notice that the pseudo code includes characters such as the stylized e
("element of" symbol) and the crossed-out equal sign (which usually means "not
equal", but since it is applied in relationship to Q, which is a queue,
comparing Q to a specific number does not make sense. so the intention is
probably to check whether the queue is empty.)


I would recommend that if in future, someone points out apparent missing
characters in text that you have copied from elsewhere, that you go back and
check whether what made it into your posting is really _exactly_ the same as
the original text, instead of just *asserting* that it is the same. You might
well have copied and pasted, but that doesn't mean that all the characters
necessarily made it from the source to the posting.
From: Khalid Rumman on 8 Apr 2010 10:42
Walter Roberson <roberson(a)hushmail.com> wrote in message
> No it wasn't. The pseudo code can be found at
> http://parallelcomp.atw.hu/ch10lev1sec7.html

Thanks for your effort, but can i use this algorithm to do parallel sort ?
It wold be great if any one can give an example.
 | 
Pages: 1
Prev: Simhydraulics
Next: parallel quicksort