Given all pairs shortest paths matrix, find graph with minimum total sum of edges

Question

I was looking at some problems about graphs, and I got stuck on this one. Namely, we have given matrix of size $N \cdot N$ representing the length of the shortest path in undirected graph between some pairs of nodes in the graph $(i,j)$.

We don't have the original graph, we instead only have the all pairs shortest paths matrix given. We need to find minimal number $x$ such that there is a way to build graph whose all pairs shortest path matrix will be the same as the given one and the sum of the edges in the graph will be exactly $x$.

Note that for some all pairs shortest paths there wont be way to build such graph, so we should also check if there can be any valid solution.

For example: for the matrix below we should output 6, if we link edges (2, 3) with cost 2 and edges (1, 3) with 4

0 6 4
6 0 2
4 2 0

I noticed that the cheapest edges will always exist, so I sorted all the numbers, then I tried using some data structure for checking if from the cheaper edges we have already covered the path from node i to node j, or we should also include new edge in the path.

However my approach doesn't give good results. Please share some advice in which direction the right solution should be.

Answer 1

Let $G=(V,E,w)$ be a weighted graph with $w$, a positive length (weight) function on $E$, i.e, the length of edge $(u,v)$ is $w(u, v)$. Let $d_{w,G}(u, v)$ denote the distance between vertex $u$ and $v$. $d_{w,G}$ will be written as $d_w$ or $d_G$ or $d$ if there is no ambiguity.

An edge $(x,y)\in E$ is essential if $w(x,y)=d_w(x,y)$ and each path from $x$ to $y$ other than the edge $(x,y)$ is longer than $w(x,y)$. Let $E'$ be the set of all essential edges of $G$. The essential subgraph of $G$ is $E(G)=(V, E', w)$, where we abuse $w$ to mean its restriction on $E'$ as well. A weighted graph is essential if it is an essential subgraph of itself, i.e., if all of its edges are essential.

Claim: $d_{E(G)}=d_{G}$.

Proof. Since $d_{E(G)}\ge d_G$, it is enough to show $d_{E(G)}\le d_G$. Let $(u,v)$ be a pair of vertices and $p = (u_0=u, u_1, u_2,\cdots, u_n=v)$ be one of the shortest paths from $u$ to $v$ in $G$.

Consider edge $(u_i, u_{i+1})$, which is an edge in that shortest path and, hence, $w(u_i,u_{i+1})= d_G(u_i,u_{i+1})$. If $(u_i, u_{i+1})$ is not essential, then we can find another shortest path from $u_i$ to $u_{i+1}$, which can replace the edge $(u_i, u_{i+1})$ in $p$.

Repeat the replacement above. Since each replacement increases the number of vertices in $p$ by at least 1, the replacements must end since $p$ can have at most all vertices and no two vertices in $p$ can be the same. In the end $p$ is the shortest path from $u$ to $v$ in $G$ that only has essential edges. Q.E.D.

Claim. $E(E(G))=E(G)$, i.e., $E(G)$ is essential.

Proof. It is immediate by definition.

Claim. Let $G_1=(V, E_1, w_1)$ and $G_2=(V, E_2, w_2) $ be two weighted essential graphs. If $d_{G_1}=d_{G_2}$, then $G_1=G_2$.

Proof. Suppose $e=(x,y)$ is in both $E_1$ and $E_2$. Then $w_1(e)=d_{w_1}(x,y)=d_{w_2}(x,y)=w_2(e)$.

Hence, there remains to prove that $E_1=E_2$.

For the sake of contradiction, let $c$ be the smallest length such that there is an edge $e$ such that

• either $e\in E_1$ with $w_1(e)=c$ but $e\not\in E_2$,
• or $e\in E_2$ with $w_2(e)=c$ but $e\not\in E_1$.

WLOG, let $e$ be an edge of the former case. Since $d_{w_2}(x,y)=d_{w_1}(x,y)=w_1(e)=c$, there is a path $p=(x_0=x, x_1, \cdots, x_n=y)$ in $G_2$ such that $w_2(p)=c$ and $n\gt1$. Since $w_1(p)\gt c$ as $e$ is an essential edge of $G_1$, there exists edge $e_i=(x_i, x_{i+1})$ for some $i$ such that $w_1(e_i)>w_2(e_i)$. So $e_i\in E_2$, $e_i\not\in E_1$ and $w_2(e_i)\lt w_2(p)=c$. This contradicts the assumption that $c$ is the smallest length of that property. Q.E.D.

Claim. Let $G_1=(V, E_1, w_1)$ and $G_2=(V, E_2, w_2) $ be two weighted graphs. If $d_{G_1}=d_{G_2}$, then $E(G_1)=E(G_2)$.

Proof. Note that $E(G_1)$ and $E(G_2)$ are essential graphs. Since $d_{E(G_1)}=d_{G_1}=d_{G_2}=d_{E(G_2)}$, this claim is implied by the previous claim. Q.E.D.

Claim. Let $G=(E,V)$ be a graph with known all-pairs distance given by $d_G$. Suppose that $d_G$ is induced by a positive weight function on $V$. Then $E(G)$ is independent of that weight function. Furthermore, $d_{E(G)}=d_G$.

Proof. This is just a restatement of previous claim.

The claim above shows that the question in the title is none other than finding $E(G)$ given its all-pairs distances.

Algorithm to find $E(G)$ given $G$ and the distance function $d_G$.

_{This algorithm is stated roughly in the question and clearly in Vince's answer. For completeness it is included here.}

Given $V=\{1,2,\cdots,n\}$ and $d(i,j)$ the distance between $i$ and $j$ for all $i$ and $j$, here is the algorithm to find $E(G)$ if $d$ is indeed induced by a length function on $V$ or return false if not.

1. Initialize a graph $H$ with nodes $V$ and no edges.
2. Iterate through $d(i,j)$ in increasing order.
   1. Compute $h(i,j)$, the distance between $i$ and $j$ in $H$ ($\infty$ if $i$ and $j$ are not connected by a path).
   2. Compare $h(i,j)$ and $d(i,j)$.
      • if $h(i,j) < d(i,j)$, return false and stop the algorithm.
      • if $h(i,j) > d(i,j)$, add edge $(i,j)$ with weight $d(i,j)$ to $H$.
3. return $H$.

Exercises

Exercise 1. (One minute or less) Verify that $E(G)$ is essential if $G$ is a weight graph.

Exercise 2. Show that if $d(i,j)$ is induced by a weight function on $V$, the algorithm above returns $E(G)$.

Answer 2

I think your approach works even if you did not give much details.

Let's call $A$ the matrix. First you sort all pairs ($i$, $j$) with $i < j$ and $A_{ij}$ increasing. You also have initially a graph $G$ with all nodes and no edges.

Then you process the pairs ($i$, $j$) one by one deciding whether to add an edge between nodes $i$ and $j$:

• compute $D$, the total weight of the shortest path existing in $G$ from $i$ to $j$ ($+\infty$ if no path).
  1. if $D < A_{ij}$, the problem has no solution,
  2. if $D = A_{ij}$, do nothing,
  3. if $D > A_{ij}$, add the edge between $i$ and $j$ of weight $A_{ij}$ to $G$.

If the shortest path from $i$ to $j$ is undirect, it necessarly has already been placed as you sorted your pairs increasing.