</b> each vertex <i>v in Adj[u]</i>
      <b>if</b> (<i>w(u,v) + d[u] < d[v]</i>)
        <i>d[v] := w(u,v) + d[u]</i>
        <i>p[v] := u</i> 
        DECREASE-KEY(<i>Q</i>, <i>v</i>)
      <b>else</b>
      	...
      <b>if</b> (<i>d[v]</i> was originally infinity) 
        INSERT(<i>Q</i>, <i>v</i>)   
    <b>end for</b>
  <b>end while</b>
  return (<i>d</i>, <i>p</i>)
</pre>
</td>
<td valign="top">
<pre>


discover vertex <i>s</i>

examine vertex <i>u</i>
examine edge <i>(u,v)</i>

edge <i>(u,v)</i> re