I have a directed weighted graph $G = (V, E, W)$. There is always an edge from a vertex $i$ to another one $j$, the weight $w(i,j)$ could be positive infinity, and there does not exist any negative cycle.

An execution of some algorithms will find the lengths (summed weights) of the shortest paths between all pairs of vertices though it does not return details of the paths themselves. For instance, Floyd–Warshall algorithm is straightforward, and it works. Let us denote the result by $G' = (V, E, W')$.

In $G'$, it is possible that for an edge from $i$ to $j$, $w'(i,j) = w'(i, k_0) + w'(k_0, k_1) + \dots + w'(k_n, j)$. Let us make from $G'$ another graph $G''$ whose any element is same as $G'$ except $w''(i,j) = \infty \neq w'(i,j)$. Therefore we know that an execution of a shortest paths algorithm on $G''$ will give $G'$.

So given a $G'$, I would like to find all the graphs like $G''$, such that for all $i$ and $j$, $w''(i,j) \in \{ w'(i,j), \infty\}$, and $G''$ can be reduced to $G'$ via a shortest paths algorithm.

Hope my question is clear... I do not know if an algorithm for this exists already, does anyone have any idea?

  • 1
    $\begingroup$ I don't understand what you are getting at here. What is $G'$, the graph consisting of the shortest paths? Or a graph with edges from $i$ to $j$ with the weight of the shortest path from $i$ to $j$ in $G$? $\endgroup$ – Raphael Jun 27 '12 at 13:04
  • $\begingroup$ @Raphael, G' is your second case (shortest path graph), but I don't know what is G"? $\endgroup$ – user742 Jun 27 '12 at 19:25
  • 1
    $\begingroup$ Ah, I believe I start to see the question: Given a tree $T$, enumerate all graphs whose shortest-path tree is $T$. Is this correct? I am still a little confused by the restrictions on the $G''$ you define. If my interpretation is correct, note this: there are infinitely many such graphs. $\endgroup$ – Raphael Jun 28 '12 at 12:33
  • $\begingroup$ Do you mean: every $G''$ is obtained by removing one or more edges from $G$, subject to the criterion that the distances between all vertices remain the same? Or may edges be added as well? $\endgroup$ – reinierpost Nov 24 '14 at 17:05

Nearest neighbor, nearest insertion, farthest insertion, and cheapest insertion are just some heuristics to get you started. You can also model the problem as a maximum flow integer program.


| cite | improve this answer | |
  • $\begingroup$ Would you describe it more? $\endgroup$ – user742 May 26 '12 at 7:56
  • $\begingroup$ your answer is very vague, can you elaborate more on it? $\endgroup$ – rizwanhudda Jul 27 '12 at 18:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.