What is the output polytree after aplying the Ramex algorithm to this graph?
Here's my interpretation of the algorithm, not sure it is completely right but that could help you:


Initialize S: null (a is added after that)
Enter in first loop on vertices (assume we start with a)
Select the edge with highest weight connected to a: a -&gt; c, and add it
Same with updated S (a or c) c -&gt; d, and add it
Same with updated S: d -&gt; e
Same with updated S: e -&gt; h
Same with updated S: e -&gt; g
Same with updated S: this is where forward and forward &amp; backward algorithms diverge. Forward algorithm only looks at weights for edges starting from S (this is a -&gt; b), while forward and backward algorithm also screens backward links, so the selected link is b -&gt; d which has a higher weight (396) than a -&gt; b (335)
Last update of S with e -&gt; f


This is what seems right to explain the figure, and works to build a polytree. I am a bit confused because it does not exactly correspond to what is written in Algorithm 3, but it is not so rare that pseudo-code algorithm make no actual sense, and would yield wrong results if written directly in any programming language.