directed or bidirected in relation to mssp (Multiple source shortest path)

Question

Firstly I wanted to ask. If I have a undirected graph and split all the edges into two directed edges is it still called directed or does it become bi-directed?

The main question is i have a graph with n sources all in the same graph until now I thought I could use the mssp method provided by Klein in this paper but it says that the graph must be a directed graph. Yet if I have an undirected graph and split each edges into two components with same weight I don't think it will be able to solve the problem or it does not matter?

Due the bidirection of the graph, will it have the first source visit each and every node without the other sources implying that I can't adapt the graph such that I can have a Shortest path tree as if I ran a dijkstra on the other sources does it?

Also I wanted to make sure does this method gets all the shortest path trees? because i was getting confused.

Klein algorithm is able to compute all the shortest path trees for specific starting nodes found on a single face (lets agree on that). Its secret is that it will do adaptations of specific darts found in the dual graph. if it is an undirected graph turning it into directed graph will become a bi directed graph by the following: can you still state that such graph is directed and also bi directed?

A directed graph is called bi-directed if the there is a mapping reversal() that maps each edge e=(v,w) to a reversal edge (denoted as reversal(e)) such that the following holds:

reversal(e)=(w,v), that is, the reversal edge of e indeed is reversely directed, so reversal() deserves its name.

reversal(reversal(e))=e, that is, also in the presence of multiedges always two edges correspond to one another.

e is different from reversal(e), that is, also in the presence of self-loops each self-loop edge has a different self-loop edge as its reversal edge. (don't have self loops)

Each edge e occurs as the reversal edge reversal(e') of a different edge e', that is, the mapping is bijective.

would you still be able to state that a I directed graph is also a directed graph?

Answer 1

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.