Plouj

a) algorithm EdgeOnSomeShorestP ath(< u, v >, s, t)
    preâ&#136;&#146;cond : The < u, v > is an edge on G, s and t are vertices
       on G
    postâ&#136;&#146;cond : The output is a boolean which is true when <
       u, v > is on some shortest path from s to t in G.
   begin
        Find the shortest path SPst from s to t using Dijkstraâ&#128;&#153;s algorithm.
        Find the shortest path SPsu from s to u using Dijkstraâ&#128;&#153;s algorithm.
        Find the shortest path SPvt from v to t using Dijkstraâ&#128;&#153;s algorithm.
        If (length(SPst ) = length(SPsu ) + weight(u, v) + length(SPvt )) then
              return true
        else
              Find the shortest path SPsv from s to v using Dijkstraâ&#128;&#153;s algorithm.
              Find the shortest path SPut from u to t using Dijkstraâ&#128;&#153;s algorithm.
              If (length(SPst ) = length(SPsv ) + weight(u, v) + length(SPut )) then
                    return true
        return false % return false in all other cases
   end algorithm