1
$\begingroup$

Given a connected graph $G$ with weighted edges (weights can be assumed as edge lengths and are non-negative). We need to identify the vertex such that the sum of the distances from other vertices to it is a minimum - to locate some facility on that node.

An $\theta$($n^3$) algorithm where $n$ is the number of vertices can be found by (a) running Floyd-Warshall algorithm and finding lengths of shortest paths between every pair of vertices with all pairs of path lengths written as a matrix in $\theta$($n^3$) and (b) finding that row of the matrix with least sum of elements.

Question: How much can the above $\theta$($n^3$) be improved?

Note: As has been pointed out in the comments below by Jukka Kohonen and Peter Taylor, all pairs shortest paths (APSP) problem has more efficient algorithms than F-W. So, there certainly are better methods than $\theta$($n^3$). It is also conceivable that there could be approaches to above question that do not go via APSP.

Further question: If we need to locate $k$ instances of the facility - that is, identify $k$ 'facility nodes' such that if all other nodes are distributed in $k$ buckets one for each facility node, the sum over all other nodes of the distance to its facility node is a minimum, what can be done (as an improvement to examining rows of the above mentioned path length matrix)?

Improve this question
$\endgroup$
8
  • 1
    $\begingroup$ For a sparse graph, you can simply compute the all-pairs shortest-paths by something else than Floyd-Warshall. A simple breadth-first search, started from each of the $n$ vertices separately, would take $O(n(n+m))$ where $m$ is the number of edges in $G$. Are you looking for something that does not require all-pairs shortest-paths? $\endgroup$
    – Jukka Kohonen
    Commented Sep 12, 2023 at 12:23
  • $\begingroup$ Thank you. I understand that BFS can compute shortest paths on graphs without weights on edges. I had meant G to be a graph with weights. Editing the question to clarify that. Sorry for the confusion. $\endgroup$
    – Nandakumar R
    Commented Sep 12, 2023 at 14:46
  • 2
    $\begingroup$ You've completely missed the point of Jukka's comments. Your question is predicated on the assumption that Floyd-Warshall is the best way of doing APSP, but that assumption is wrong. Since the one-facility problem reduces to APSP + $O(n^2)$, Pettie's algorithm for APSP in $O(nm + n^2 \log \log n)$ or Chan's algorithm in $O(n^3 / \log n)$ give trivial answers to the question. Therefore what Jukka asks is whether those trivial answers are what you're looking for, or whether you want to refine the question to ask whether there are even better algorithms than APSP + $O(n^2)$. $\endgroup$
    – Peter Taylor
    Commented Sep 13, 2023 at 10:28
  • 1
    $\begingroup$ I wasn't aware of better methods than F-W for APSP. Thank you. Edited the question again incorporating your inputs. I gave the Theta(n^3) method only as a starting point. $\endgroup$
    – Nandakumar R
    Commented Sep 13, 2023 at 14:54
  • 1
    $\begingroup$ For your further question, search for $k$-median problem (aka $p$-median problem). $\endgroup$
    – RobPratt
    Commented Sep 23, 2023 at 15:00

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .