directed or bidirected in relation to mssp (Multiple source shortest path)
First, let's be completely clear about the definition of the multiple-source shortest path problem.  The input consists of the following:


a directed planar graph $G = (V,E)$ with $n$ vertices;
a non-negative weight $w(e)$ for every directed edge $e$;
an embedding of $G$ into the plane; and
a distinguished face $f$ of this planar embedding (the "outer" face).


Klein's algorithm computes a compressed representation of all shortest-path trees rooted at vertices of the designated face $f$, in $O(n\log n)$ time and space.  This representation allows us to retrieve the shortest-path distance from any vertex on $f$ to any other vertex in $O(\log n)$ time.

An explicit representation of these shortest-path trees would require $\Theta(kn)$ space, where $k$ is the number of vertices in $f$; in the worst case, this space bound is $\Theta(n^2)$.  Klein's observation, at least intuitively, is that the shortest-path trees for two adjacent source vertices are nearly identical; his data structure stores only the differences between adjacent trees.

Klein's algorithm works just fine for bidirected and undirected graphs.  For purposes of the algorithm, a bidirected graph is just a directed graph where the reversal of every arc is another arc, and an undirected graph is jut a bidirected graph where every arc has the same weight as its reversal.  In other words, a bidirected graph is a directed graph whose adjacency matrix is symmetric, and (in this context) an undirected graph is just a directed graph whose weighted adjacency matrix is symmetric.  Klein's algorithm requires no modifications whatsoever to handle these special cases.

Klein's algorithm does not compute shortest-path distances between arbitrary pairs of vertices; in every pair, the source vertex must lie on the designated face.  For a solution to the more general problem, see Sergio Cabello's paper "Many distances in planar graphs" [SODA 2006 and Algorithmica 2012].

You might also check out my upcoming journal paper with Sergio Cabello and Erin Chambers, which describes a different multiple-source shortest-path algorithm, which also works for higher-genus graphs.