[Math] The shortest path connecting three points

calculusgeometrygraph theorylagrange multipliermultivariable-calculus

I have 3 points X,Y,Z, lets call them buildings.

I need to find the shortest amount of path that connects the 3 buildings, these buildings can be in any sort of shape and any distance from each other, lets call the distance between each building xy, xz, yz.

I know that the paths need to converge at a point, but I am unsure how to get there given the information I have.

If they formed an equilateral triangle it would look like (or at least I think):

But they can be in any shape and that's only one of them, I need help finding the equation(s) that will give the shortest path connecting all 3 of the buildings.

I was thinking of using the Pythagorean Theorem but am not 100% sure, I was also thinking about using Lagrange Multipliers but with the information given am not sure how to implement them.

I'm just looking for a push in the right direction, I don't need the full solution (it would help but not needed.) If you need any more information about the problem I can try my best but this is about all I have.

Best Answer

I believe that Napoleon (himself!) was interested in this problem.

Distinguish between two cases.

If the given triangle has an angle that exceeds ${2\pi}\over 3$, then that particular vertex itself is the point you seek. In this case, the sought-after minimum total distance is comprised of the two shortest sides.
OTHERWISE, the point can be constructed as follows: On each of the three sides, construct an outward-pointing equilateral triangle. Connect each outward point with the opposing vertex of the original triangle. The three connecting lines are concurrent, and their common point (the Fermat point, or the first isogonal center of the triangle) is the point you seek. Lines drawn from this point to the three original vertices are the paths whose total length constitutes the sought-after minimum total distance.

Related Solutions

Graph Theory – Infinite Shortest Paths in Graphs

To expand on my comment: It's clear that if an infinite path is defined as a map from $\mathbb N$ to the edge set such that consecutive edges share a vertex, then any vertices connected by such an infinite path are in fact connected by a finite section of the path. To make sense of the question nevertheless, one might ask whether it is possible to use a different ordinal than $\omega$, say, $\omega\cdot2$, to define an infinite path. But that doesn't make sense either, since there's no way (at least I don't see one) to make the two parts of such a path have anything to do with each other -- at each limit ordinal, the path can start wherever it wants, since there's no predecessor for applying the condition that consecutive edges share a vertex.

Note that the situation is different in infinite trees, which can perfectly well contain infinite paths connecting the root to a node. This is because the definition of a path in an infinite tree is different; it explicitly attaches the nodes on levels corresponding to limit ordinals to entire sequences of nodes, not to individual nodes; such a concept doesn't exist in graphs.

[Math] Graph Theory Shortest Path Problem via Matrix Operations in MatLab

You could use the fact that $A^i(s,t)$ gives the number of different walks from $s$ to $t$ of exactly $i$ many steps. Thus, you could just compute $A^0, A^1, A^2, A^3, ...$ and keep the minimum exponent $i$ for which it is $A^i(s,t) > 0$, since such $i$ matches the distance. Here is an example that uses this fact:

% let B(s,t) keep the minimum power i with A^i(s,t) > 0
B=zeros(n,n);
for i=1:n
    B=B+(B<=0).*(A^i>0).*i;
end

% set main diagonal to zero (optional, otherwise get the 'return time')
B(eye(size(B))~=0)=0;

Some comments on the above code: for a connected graph, you can also break the loop after $diam(G)$ many steps, i.e., when B contains no zeros. Further, one could avoid computing $A^i$ in each step and use something like $Apow = Apow * A$ within the loop. Also note that here the main diagonal is manually set to zeros in the end, since starting the loop at $i=0$ does not work without further modifications (one would also have to flag unset entries within $B$ by another number than $0$ then, e.g., by $-1$).

However, note that this is just an example of how one could compute the shortest paths in Matlab with a single loop and matrix operations only. Its computational effort (including the above optimizations) is something like $\mathcal{O}(diam(G)*M(n))$ with $M(n)$ the effort of a matrix multiplication, thus, something like $\mathcal{O}(diam(G)*n^3)$. This is far from optimal, and especially bad for large sparse graphs. I do not believe that there is an efficient pure-matrix-operative solution to this problem. For example, the dynamic programming approach of Dijkstra, cannot efficiently be expressed in matrix form.

Unfortunately, Matlab again and again tells the user to avoid for-loops, since they are so 'slow'. But this tale does only hold for Matlab's horrible implementation of for-loops! In a real programming language, for-loops are much much faster than in Matlab, and they are even the most efficient way to access the memory in an arbitrary order that does not follow the access pattern of a matrix operation.

Best Answer

Related Solutions

Graph Theory – Infinite Shortest Paths in Graphs

[Math] Graph Theory Shortest Path Problem via Matrix Operations in MatLab

Related Question